A-A+

关于后缀树的一些理解

2008年11月25日 学习随笔 暂无评论 阅读 1 次

要理解suffix tree就首先要理解Trie
还好我在刚进雅虎的时候接触到了Double Array Trie的一个具体实现
对Trie有着比较深刻的了解。
Trie的优势就是他能在o(n)时间内搜索一个长度为n的字符串s是否在字典里。
关于Trie的资料,有下面几个链接可以参考
http://www.allisons.org/ll/AlgDS/Tree/Trie/
http://linux.thai.net/~thep/datrie/datrie.html

言归正传,简单点说,后缀树就是将一个给定字符串的所有后缀全部压入一个Trie
然后将只有单个叶子的节点压缩,从而形成的一棵树
关于后缀树如何构造,有很多资料进行介绍,就不多说了
例如:
http://www.allisons.org/ll/AlgDS/Tree/Suffix/
上面这个网页里有一个手动构造后缀树的例子,非常生动

我更关注的是后缀树的用途,总结起来大概有如下几种
1. 查找字符串o是否在字符串S中。
方案:用S构造后缀树,按在trie中搜索字串的方法搜索o即可。
原理:若o在S中,则o必然是S的某个后缀的前缀。
听起来有点拗口,举个例子。例如S: leconte,查找o: con是否在S中
则o(con)必然是S(leconte)的后缀之一conte的前缀
有了这个前提,采用trie搜索的方法就不难理解了。
2. 指定字符串T在字符串S中的重复次数。
方案:用S+’$'构造后缀树,搜索T节点下的叶节点数目即为重复次数
原理:如果T在S中重复了两次,则S应有两个后缀以T为前缀,重复次数就自然统计出来了。
3. 字符串S中的最长重复子串
方案:原理同2,具体做法就是找到最深的非叶节点。
这个深是指从root所经历过的字符个数,最深非叶节点所经历的字符串起来就是最长重复子串。
为什么要非叶节点呢?因为既然是要重复,当然叶节点个数要>=2。
4. 两个字符串S1,S2的最长公共部分
方案:将S1#S2$作为字符串压入后缀树,找到最深的非叶节点,且该节点的叶节点既有#也有$(无#)。
大体原理同3

上段文字可能表达不够准确,更准确的表达可以参考
http://www.allisons.org/ll/AlgDS/Tree/Suffix/
http://blog.csdn.net/g9yuayon/archive/2008/06/21/2574781.aspx
当然英文wiki和google也是很好的参考资料~

给我留言

Copyright © 浩然东方 保留所有权利.   Theme  Ality 07032740

用户登录