Trie 树

什么是 Trie 树

Trie 树，又称前缀树，字段典树，或单词查找树，是一种树形结构，也是哈希表的变种，它是一种专门处理字段串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题，主要被搜索引擎用来做文本词频的统计。

先看一下前辍树的图：

这棵前辍树根节点不存放数据，其他节点保存了 hello,her,hi,how,see,so 等关键词信息，如果查 he 前辍的单词可以很快返回 hello,her。

Trie 树的 Python 实现

一般来讲 trie 要实现这么几个方法

插入一个单词 insert (word: str) -> None
查找一个单词是否在 trie 中 search (word:str) -> bool
查找一个前缀是否在 trie 中 startsWith (prefix:str) -> bool

class Trie:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = {}
        self.end_of_word = '#'

    def insert(self, word: str) -> None:
        """
        Inserts a word into the trie.
        """
        node = self.root
        for char in word:
            node = node.setdefault(char, {})
        node[self.end_of_word] = self.end_of_word

    def search(self, word: str) -> bool:
        """
        Returns if the word is in the trie.
        """
        node = self.root
        for char in word:
            if char not in node:
                return False
            node = node[char]
        return self.end_of_word in node

    def startsWith(self, prefix: str) -> bool:
        """
        Returns if there is any word in the trie that starts with the given prefix.
        """
        node = self.root
        for char in prefix:
            if char not in node:
                return False
            node = node[char]
        return True
      
    def get_start(self,prefix):
        '''
        给出一个前辍，打印出所有匹配的字符串
        :param prefix:
        :return:
        '''
        def get_key(pre,pre_node):
            result = []
            if pre_node.get(self.end_of_word):
                result.append(pre)
            for key in pre_node.keys():
                if key != self.end_of_word:
                    result.extend(get_key(pre+key,pre_node.get(key)))
            return result


        if not self.startsWith(prefix):
            return []
        else:
            node = self.root
            for p in prefix:
                node = node.get(p)
            else:
                return get_key(prefix,node)

if __name__ == "__main__":
    trie = Trie()
    trie.insert("Python")
    trie.insert("Python 算法")
    trie.insert("Python web")
    trie.insert("Python web 开发")
    trie.insert("Python web 开发 视频教程")
    trie.insert("Python 算法 源码")
    trie.insert("Perl 算法 源码")
    print(trie.search("Perl"))
    print(trie.search("Perl 算法 源码"))
    print((trie.get_start('P')))
    print((trie.get_start('Python web')))
    print((trie.get_start('Python 算')))
    print((trie.get_start('P')))
    print((trie.get_start('Python web')))
    print((trie.get_start('Python 算')))

代码运行结果如下：

False
True
['Python', 'Python 算法', 'Python 算法 源码', 'Python web', 'Python web 开发', 'Python web 开发 视频教程', 'Perl 算法 源码']
['Python web', 'Python web 开发', 'Python web 开发 视频教程']
['Python 算法', 'Python 算法 源码']