![](https://csdnimg.cn/release/download_crawler_static/19561720/bg4.jpg)
考察前缀"a",发现边a已经存在。于是顺着边a走到节点a。1.
考察剩下的字符串"dd"的前缀"d",发现从节点a出发,已经有边d存在。于是顺着边d走到节点ad2.
考察最后一个字符"d",这下从节点ad出发没有边d了,于是创建节点ad的子节点add,并把边ad->add标记为
d。
3.
1.5、Trie树的应用
除了本文引言处所述的问题能应用Trie树解决之外,Trie树还能解决下述问题(节选自此文:海量数据处理面试题
集锦与Bit-map详解):
3、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频
数最高的100个词。
9、1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实
现?
10、 一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出
时间复杂度分析。
13、寻找热门查询:
搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。
假设目前有一千万个记录,这些查询串的重复读比较高,虽然总数是1千万,但是如果去除重复和,不超过3
百万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要
求使用的内存不能超过1G。
(1) 请描述你解决这个问题的思路;
(2) 请给出主要的处理流程,算法,以及算法的复杂度。
有了Trie,后缀树就容易理解了。本文接下来的第二部分,介绍后缀树。
第二部分、后缀树
2.1、后缀树的定义
后缀树(Suffix tree)是一种数据结构,能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner 于1973
年提出,既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改进完善。
后缀,顾名思义,甚至通俗点来说,就是所谓后缀就是后面尾巴的意思。比如说给定一长度为n的字符串
S=S1S2..Si..Sn,和整数i,1 <= i <= n,子串SiSi+1...Sn便都是字符串S的后缀。
以字符串S=XMADAMYX为例,它的长度为8,所以S[1..8], S[2..8], ... , S[8..8]都算S的后缀,我们一般还把空
字串也算成后缀。这样,我们一共有如下后缀。对于后缀S[i..n],我们说这项后缀起始于i。
S[1..8], XMADAMYX, 也就是字符串本身,起始位置为1
S[2..8], MADAMYX,起始位置为2
S[3..8], ADAMYX,起始位置为3
S[4..8], DAMYX,起始位置为4
S[5..8], AMYX,起始位置为5
S[6..8], MYX,起始位置为6
S[7..8], YX,起始位置为7
S[8..8], X,起始位置为8
空字串,记为$。
而后缀树,就是包含一则字符串所有后缀的压缩Trie。把上面的后缀加入Trie后,我们得到下面的结构:
展开
TAOPP修订wiki
julymsn@live.cn
电子工程网专家VIP
博客园blog-成为推荐博客
ITpub-代码优化专家
04、我的驻点
01、GitHub
02、Harry
03、NoSQLFan
04、Team_Algorithms人人小组
05、老D之MongoDB源码分析
06、开源中国
07、视频编解码
08、老大blog
09、多媒体/流媒体开发问答
10、我的有鱼
11、TheItHome算法版块版主
12、code4app:iOS代码示例
13、TAOPP编程艺术讨论组
14、StackOverflow
15、北大朋友的挖掘乐园
16、跟Sophia_qing一起读硕士
17、面试问答社区
51nod
18、韩寒
19、36氪--关注互联网创业
20、德问--编程是一种艺术创作
文章存档
2012年09月(1)
2012年06月(1)
2012年05月(2)
2012年04月(1)
2012年03月(2)
从Trie树(字典树)谈到后缀树(10.28修订) - 结构之法 算法之道 ... http://blog.csdn.net/v_july_v/article/details/6897097
4 of 20 10/27/2012 8:10 P