从Trie树(字典树)谈到后缀树.docx

《从Trie树(字典树)谈到后缀树.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、从Trie树（字典树）谈到后缀树作者：v_JULY_v　来源：结构之法算法之道　2011-10-23分享到：新浪微博腾讯微博豆瓣网人人网开心网QQ空间搜狐微博更多0引言咱们先来看一道面试题：一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。之前在此文：海量数据处理面试题集锦与Bit-map详解中给出的参考答案：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平均长度），然后是找出出现最频繁的前10个词。也可以用堆来实现（具体的操

2、作可参考第三章、寻找最小的k个数），时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。本文第一部分，咱们就来了解了解这个Trie树，然后自然而然过渡到第二部分、后缀树，在此对这两种树权作此番阐述，以备不时之需，在需要的时候能手到擒来即可。ok，有任何问题，欢迎不吝指正或赐教。谢谢。第一部分、Trie树什么是Trie树Trie树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系

3、统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。它有3个基本性质：1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。3.每个节点的所有子节点包含的字符都不相同。举例举个在网上流传颇广的例子，如下：题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在

4、第几个位置。分析：这题当然可以用hash来解决，但是本文重点介绍的是trie树，因为在某些方面它的用途更大。比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在ab

5、cd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。好比假设有b，abc，abd，bcd，abcd，efg，hii这6个单词，我们构建的树就是如下图这样的：（图义：当时第一次看到这幅图的时候，便立马感到此树之不凡构造了。单单从上幅图便可窥知一二，好比大海搜人，立马就能确定东南西北中的到底哪个方位，如此迅速缩小查找的范围和提高查找的针对性，不失为一创举）对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这

6、个单词存在，否则不存在。那么，对于一个单词，我只要顺着他从跟走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。这样一来我们查询和插入可以一起完成（重点体会这个查询和插入是如何一起完成的，稍后，下文具体解释），所用时间仅仅为单词长度，在这一个样例，便是10。我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。小结ok，下面，咱们再总结一下上述问题：已知n个

7、由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法：1.最容易想到的：即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为O(n^2)。2.使用hash：我们用hash存下所有字符串的所有的前缀子串，建立存有子串hash的复杂度为O(n*len)，而查询的复杂度为O(n)*O(1)=O(n)。3.使用trie：因为当查询如字符串abc是否为某个字符串的前缀时，显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂

8、度为O(n*len)，而建立+查询在trie中是可以同时执行的，建立的过程也就可以成为查询的过程，hash就不能实现这个功能。所以总的复杂度为O(n*len)，实际查询的复杂度也只是O(len)。解释下上述方法3中所说的为什么hash不能将建立与查询同时执行，而Trie树却可以：·在hash中，例如有串：911，911456输入，如果要同时执行建立与查询，过