[奇怪但有用的数据结构]Trie前缀树

想象一个这样的情景,有一个很大的字典包含了很多的单词,需要判断一个新单词是否在字典中,最直接也最快的办法就是使用哈希表了。现在添加一个条件,判断字典里是否存在单词以新单词为前缀,这时候哈希表就不合适了,因为存在单词在字典中但其前缀不在字典中的情况,例如[‘apple’, 'application','append']这个字典并不包含他们的公共前缀'app','ap'和‘a’。所以我们需要一种新的数据结构和算法来处理这类问题。

很显然如果我们知道哪些单词是以字母'a'开头的,就可以很方便的判断是否有单词是以'ap'为前缀的,从而不必理会以其他字母开头的单词。再进一步,我们可以从'ap'开头的单词中找是否有单词是以‘app’为前缀的,从'ab'开头的单词中找是否有单词一'aba'为前缀。于是这样的树形结构就构造出来了。

树形结构

我们可以很容易地看出来这棵树中包含四个单词abc, apple, bad和bat。也可以轻松判断出存在单词以'app'为前缀,而没有'ad'开头的单词。

Trie前缀树

这样的树形结构就是前缀树(Trie),也叫单词查找树,典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。它的基本性质如下:

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

构造前缀树

首先我们要定义一下节点的数据结构。每一个节点可以跟着若干个子节点,因为都是字符,所以可以用哈希表来保存子节点。并且要有一个标记来表示这个字符是不是一个单词的最后一个字符,不然以上图为例,无法知晓单词'app'是否在这个字典中。这是我设计的Node类(__repr__方法用于清晰的展示节点的结构)。

class Node:
    def __init__(self):
        self.is_last = False
        self.children = {}
    def __repr__(self):
        return 'Node({},[{}])'.format(self.is_last, 
            ','.join('{}:{}'.format(x, repr(self.children[x])) for x in self.children))

接下来就是构造前缀树了,很自然的会有一个Node类型的根节点root:

class Trie:
    def __init__(self):
        self.root = Node()

然后是在合适的位置插入新单词(去掉已有前缀的部分):

class Trie:
    def __init__(self):
        self.root = Node()
        
    def generate_node(self, word:str) -> Node:
        node = Node()
        if len(word) > 0:
            node.children[word[0]] = self.generate_node(word[1:])
        else:
            node.is_last = True
        return node
    

对于后续的操作(insert, search, startsWith)来说,寻找前缀是第一步,我这里使用的是一个get_node_rest方法,获得一个单词在前缀树中最长前缀的尾节点和剩余的字符。

class Trie:
    def __init__(self):
        self.root = Node()
        
    def generate_node(self, word:str) -> Node:
        #...
        
    
    def get_node_rest(self, root:Node, word:str)-> tuple:
        if not word:
            return root, ''
        elif word[0] in root.children:
            return self.get_node_rest(root.children[word[0]], word[1:])
        else:
            return root, word

获取了一个单词的node和rest,插入操作就是在node节点插入rest部分的字符,判断是否是前缀(startsWith)就是判断rest是否为空,如果node的is_last也同时为真的话就是存在这个单词了(search)。完整的代码如下:

#前缀树
class Node:
    def __init__(self):
        self.is_last = False
        self.children = {}
    def __repr__(self):
        return 'Node({},[{}])'.format(self.is_last,
            ','.join('{}:{}'.format(x, repr(self.children[x])) for x in self.children))

        

class Trie:
    def __init__(self):
        self.root = Node()
        
    def generate_node(self, word:str) -> Node:
        node = Node()
        if len(word) > 0:
            node.children[word[0]] = self.generate_node(word[1:])
        else:
            node.is_last = True
        return node
        
    def get_node_rest(self, root:Node, word:str)-> tuple:
        if not word:
            return root, ''
        elif word[0] in root.children:
            return self.get_node_rest(root.children[word[0]], word[1:])
        else:
            return root, word
    
    def insert(self, word):
        node, rest = self.get_node_rest(self.root, word)
        if rest:
            node.children[rest[0]] = self.generate_node(rest[1:])
        else:
            node.is_last = True
    
    def search(self, word):
        node, rest = self.get_node_rest(self.root, word)
        return rest == '' and node.is_last
    
    def startsWith(self, word):
        _, rest = self.get_node_rest(self.root, word)
        return len(rest) == 0

我们可以看一下Trie类的使用。

Trie类的使用

结语

本文简单介绍了前缀树的定义和用途,并用Python实现了一个简单的Trie类,希望能够给予大家一些启发和帮助。

最后祝大家享受生活,享受代码。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【专业技术】你必须注意的11个C++要点

下面的这些要点是对所有的C++程序员都适用的。我之所以说它们是最重要的,是因为这些要点中提到的是你通常在C++书中或网站上无法找到的。如:指向成员的指针,这是许...

2665
来自专栏java一日一条

Java LinkedHashMap工作原理及实现

在理解了#7 介绍的HashMap后,我们来学习LinkedHashMap的工作原理及实现。首先还是类似的,我们写一个简单的LinkedHashMap的程序:

341
来自专栏Vamei实验室

Java基础09 类数据与类方法

我们一直是为了产生对象而定义类(class)的。对象是具有功能的实体,而类是对象的类型分类。这是面向对象的一个基本概念。 在继承(inheritance)中,我...

1768
来自专栏kevindroid

JNI所需的C语言知识小结

1445
来自专栏女程序员的日常

值类型和引用类型的区别,struct和class的区别

C#值类型和引用类型 1、简单比较   值类型的变量直接存储数据,而引用类型的变量持有的是数据的引用,数据存储在数据堆中。   值类型(value type):...

2091
来自专栏java一日一条

Swift 中的内存管理详解

这篇文章是在阅读《The Swift Programming Language》Automatic Reference Counting(ARC,自动引用计数)...

531
来自专栏微信公众号:Java团长

Java基础09 类数据与类方法

我们一直是为了产生对象而定义类(class)的。对象是具有功能的实体,而类是对象的类型分类。这是面向对象的一个基本概念。

491
来自专栏余林丰

Java中的Object、T(泛型)、?区别

因为最近重新看了泛型,又看了些反射,导致我对Object、T(以下代指泛型)、?产生了疑惑。 我们先来试着理解一下Object类,学习Java的应该都知道Obj...

21510
来自专栏用户2442861的专栏

java final 关键字

http://blog.csdn.net/niguang09/article/details/6035813

552
来自专栏ImportSource

厕读:每日一题,面试无忧

4. 下列说法正确的有() A. class中的constructor不可省略 B. constructor必须与class同名,但方法不能与class同名 C...

2756

扫码关注云+社区