首页 > 基础算法 > 字符串处理 > 后缀树简介
2014
10-04

后缀树简介

模式匹配问题

给定一个文本text[0...n-1], 和一个模式串 pattern[0...m-1],写一个函数 search(char pattern[], char text[]), 打印出pattern在text中出现的所有位置(n > m)。

这个问题已经有两个经典的算法:KMP算法 ,有限自动机,前者是对模式串pattern做预处理,后者是对待查证文本text做预处理。在进行完预处理后,可以到达O(n)的时间复杂度,n是text的长度。

后缀树可以用对text进行预处理,构造一个text的后缀树,就可以在 O(m) 的时间内搜索任意一个pattern,m是模式串pattern的长度。

后缀字典树

想象一下,你刚成为一个DNA序列化项目中的程序员。研究人员正在对病毒的遗传物质进行切片和切块,以产生核苷酸序列的片段。他们把这些遗传物质序列片段送人你的服务器进行匹配,希望能够在基因组数据库中定位到这些序列。一个特定的病毒的基因组可能有数十万的核苷酸,并且在你的数据库中存储了成千上万的病毒的信息。希望你能够实现一个C/S结构的项目,来实时的为研究人员提供服务。怎么做才比较好呢?

因为数据库是不变的,所以对它进行预处理以使得搜索变得简单。一种预处理的方式是建立一个字典树(Trie树) ,该字典树中存放的是给定字符串的所有后缀,用这种方式生成的字典树,称为后缀字典树(suffix trie),后缀字典树只差一步就是我最终要引入的数据结构——后缀树。字典树是一种N叉树,其中N是字母表的大小。

对于字符串:“banana\0″ 的所有后缀为:

banana\0
anana\0
nana\0
ana\0
na\0
a\0
\0

其标准的后缀字典树结构是这样的:

suffixtrie

很显然,有了这样的一个树,我只需要4次字符比较就可以确定pattern:“nana”是否出现。当然仅仅有一个小问题会拖后腿儿,那就是创建字典树所耗费的时间。

但是,构造后缀字典树需要O(N2)时间和空间复杂度。这种平方级的性能使它不能在最需要用到它的地方使用,即不能在大数据量场合使用。

后缀树

Edward McCreight 在1976年提出了一个合理的解决方法摆脱了后缀字典树在应用上的困境,他发表的论文中提出了后缀树(suffix tree)

一个给定的文本text的后缀树就是一个压缩的后缀字典树。压缩至的是路径压缩,去除了只有一个子边的节点。例如对上上图中最左边的 banana\0  ,即为一个没有分叉的单边,可以进行压缩:

suffix-tree

上面这个图是靠是手动生成的,实际上这里还是有一些比较复杂的算法,后续再做讨论。节点数量的减少,使构造后缀树的时间和空间复杂度从O(N2)减少到了O(N)。在最坏的情况下,一个后缀树最多包含2N个节点,其中N是输入文本的长度。所以对输入文本的一次性投资,可以使我们的每次搜索都受益。

应用

(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$作为字符串压入后缀树,找到最深的非叶节点,且该节点的叶节点既有#也有$(无#)。

参考:http://blog.csdn.net/fanzitao/article/details/8042015

http://www.geeksforgeeks.org/pattern-searching-set-8-suffix-tree-introduction/


  1. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  4. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥