Trie树简介
在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。
Trie这个术语来自于retrieval。根据词源学,trie的发明者Edward Fredkin把它读作/ˈtriː/ "tree"。但是,其他作者把它读作/ˈtraɪ/ "try"。
在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。
Eg.一个保存了8个单词的字典树的结构如下图所示,8个单词分别是:“A”,“to”,“tea”,“ted”,“ten”,“i” ,“in”,“inn”。
另外,单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
Trie树性质
它有3个基本性质:
- 根节点不包含字符,除根节点外每一个节点都只包含一个字符;
- 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
- 每个节点的所有子节点包含的字符都不相同。
基本操作
其基本操作有:查找、插入和删除,当然删除操作比较少见。
实现方法
搜索字典项目的方法为:
- (1)从根结点开始一次搜索;
- (2) 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;
- (3) 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
- (4) 迭代过程……
- (5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。
其他操作类似处理
实现 Trie (前缀树)
关于Trie树实现,可以移步看下LeetCode208. 实现 Trie (前缀树)
输入 ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] 输出 [null, null, true, false, true, null, true] 解释 Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // 返回 True trie.search("app"); // 返回 False trie.startsWith("app"); // 返回 True trie.insert("app"); trie.search("app"); // 返回 True 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/implement-trie-prefix-tree
具体实现如下:
class TrieNode(object): def __init__(self): """ Initialize your data structure here. """ self.data = {} self.is_word = False class Trie: def __init__(self): """ Initialize your data structure here. """ self.root = TrieNode() def insert(self, word): """ Inserts a word into the trie. :type word: str :rtype: void """ node = self.root for chars in word: child = node.data.get(chars) if not child: node.data[chars] = TrieNode() node = node.data[chars] node.is_word = True def search(self, word): """ Returns if the word is in the trie. :type word: str :rtype: bool """ node = self.root for chars in word: node = node.data.get(chars) if not node: return False return node.is_word # 判断单词是否是完整的存在在trie树中 def startsWith(self, prefix): """ Returns if there is any word in the trie that starts with the given prefix. :type prefix: str :rtype: bool """ node = self.root for chars in prefix: node = node.data.get(chars) if not node: return False return True def get_start(self, prefix): """ Returns words started with prefix 返回以prefix开头的所有words 如果prefix是一个word,那么直接返回该prefix :param prefix: :return: words (list) """ def get_key(pre, pre_node): word_list = [] if pre_node.is_word: word_list.append(pre) for x in pre_node.data.keys(): word_list.extend(get_key(pre + str(x), pre_node.data.get(x))) return word_list words = [] if not self.startsWith(prefix): return words if self.search(prefix): words.append(prefix) return words node = self.root for chars in prefix: node = node.data.get(chars) return get_key(prefix, node) if __name__ == '__main__': trie = Trie() print('trie.insert("apple"):', trie.insert("apple")) print('trie.insert("appal"):', trie.insert("appal")) print('trie.insert("appear"):', trie.insert("appear")) print('trie.insert("apply"):', trie.insert("apply")) print('trie.insert("appulse"):', trie.insert("appulse")) print('trie.search("apple"):', trie.search("apple")) # 返回 True print('trie.search("app"):', trie.search("app")) # 返回 False print('trie.startsWith("app"):', trie.startsWith("app")) # 返回 True print('trie.insert("app"):', trie.insert("app")) print('trie.search("app"):', trie.search("app")) print('trie.search("app"):', trie.get_start("app")) print('trie.search("ap"):', trie.get_start('ap'))
结果输出如下:
F:\ProgramData\Anaconda3\python.exe F:/Projects/nlp-trie/main.py trie.insert("apple"): None trie.insert("appal"): None trie.insert("appear"): None trie.insert("apply"): None trie.insert("appulse"): None trie.search("apple"): True trie.search("app"): False trie.startsWith("app"): True trie.insert("app"): None trie.search("app"): True trie.search("app"): ['app'] trie.search("ap"): ['app', 'apple', 'apply', 'appal', 'appear', 'appulse'] Process finished with exit code 0
应用
- 输入框提示/自动补全:trie 常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。
- 字符串检索、模糊匹配
- 文本预测、自动完成,see also,拼写检查
- 在NLP中的应用,主要有基于字典树的文本分词、短语提取、实体提取等
优缺点
优点:
可以最大限度地减少无谓的字符串比较,故可以用于词频统计和大量字符串排序。
跟哈希表比较:
- 最坏情况时间复杂度比hash表好
- 没有冲突,除非一个key对应多个值(除key外的其他信息)
- 自带排序功能(类似Radix Sort),中序遍历trie可以得到排序。
缺点:
- 虽然不同单词共享前缀,但其实trie是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针。
- 如果数据存储在外部存储器等较慢位置,Trie会较hash速度慢(hash访问O(1)次外存,Trie访问O(树高))。
- 长的浮点数等会让链变得很长。可用bitwise trie改进。
时间复杂度
时间复杂度:创建时间复杂度为O(L),查询时间复杂度是O(logL),查询时间复杂度最坏情况下是O(L),L是字符串的长度。