后缀树与后缀数组

本文系转载 :http://ycool.com/post/hj7cv6m

后缀树和后缀数组简直就是 ACM 选手必备的知识啊,我已经在两次比赛中碰到过相关的问题了。我甚至还写过一篇应用的文章,可是我真是井底之蛙啊,那时我还不知道这个叫后缀数组,还有更好的构造算法,还有很多的应用。最近终于好好在这方面扫了个盲,在此小小地总结一下。

假设有一个长度为 n 的字符串 T[0 … n);S(i) 表示 T 的从下标 i 开始的后缀,即 T[i … n)。那么 T 的后缀数组就是把 S(i) ~ S(n – 1) 这 n 个后缀按字典序排好序的一个数组。它对于查找 T 的子串之类的问题是很有用的。问题就在于怎样快速地把这些后缀排好序。

最简单的方法就是把所有 S(i) 快速排序。快速排序本身的时间是 O(n log n),但是由于排序的对象是一个个字符串,所以每次比较的时间在最差情况下都会变成线性的(也就是 O(n) 的),因此总的时间在最差情况下可能会升到 O(n2) 左右,这就很慢了。对此,我学到了三个更快的算法。

1. Ukkonen 算法

Ukkonen 算法先用 O(n) 的时间构造一棵后缀树,然后再用 O(n) 的时间从后缀树得到后缀数组。在这个网址,介绍了作者 Esko Ukkonen,并列出了他的一些论文;其中的一篇《On-line construction of suffix-trees》是可以下载的,里面就讲解了什么是后缀树,怎样在 O(n) 的时间内构造它,以及怎样从它得到后缀数组。

不过我一开始还没发现这篇论文,我是从 Dan Gusfield 的《Algorithms on Strings, Trees and Sequences – COMPUTER SCIENCE AND COMPUTATIONAL BIOLOGY》这本书里学到这个算法的。这本书在中国没的卖,想买的话,可以找代购网站去 Amazon 买。我是在 eMule 上搜到并下载的。这本书中的这节内容讲得还可以,虽然我觉得它示例比较少,但是花了点功夫还是看懂了。学会了之后,原作者的论文我就没有仔细看过了,所以没法评论。

Ukkonen 算法还是比较复杂的,代码比较长;而且后缀树这个结构本身也比较费空间。总而言之,虽然该算法在理论上是最快的,后缀树也是一个很优美的结构,但是在许多实际应用中不是很实惠。

然而,一开始我还不知道别的算法时,还是把它实现了出来(代码 1、代码 2)。(我写了两个版本,它们的不同点在于每个节点的子节点的存放方式。代码 1 是用数组,代码 2 是用链表。用数组的话,查找指定的子节点很快,只要 O(1);但是比较费空间。用链表的话,省空间,但是查找子节点比较慢,只能线性地查找,不过一般情况下问题不大。实际上,我在 PKU 3415 这道题中,用数组反而比用链表慢,可能前者分配空间所花的时间比较多吧。)

2. DC3 算法

我在 Google 上搜到了这篇论文,《Linear Work Suffix Array Construction》,其中介绍了一个可以在 O(3n) 的时间内构造出后缀数组的算法,叫作 DC3 (Difference Cover mod 3) 算法。

该算法的基本原理大致是这样的。针对所有后缀的前 3 个字符,做基数排序;对于不满 3 个字符的后缀,排序时在后面补 0(这里的 0 是结束符,在 T 中不能出现;0 的字典序最优先);排序时还要包括进从结束符(即 T[n])开始的后缀 S(n): “000”。如果所有后缀的前 3 个字符都不完全相同,那么这一次就排好了,最后去掉多余的 “000” 后缀(它一定排在第一个),就得到答案了,时间是 O(3n)。如果存在前 3 个字符相同的,则需要生成一个名次数组 R, R(i) 表示 S(i) 在排好序后位于第几名(名次从 1 开始计),接着再用上述方法递归地求 R[0 … n] 的后缀数组,其结果和 T 的后缀数组是完全对应的,也就是说 SR(i) 排在第几位,则 S(i) 也应该排在第几位。但问题是如果这样递归层数多了,时间也就大大增加了。

接下来,在上述算法的基础上,需要一个优化。首先,只对满足 i mod 3 = 1 或 i mod 3 = 2 的那些 S(i) 按照前 3 个字符进行基数排序;如果这其中有前 3 个字符相同的,同样也需要递归地求它们的名次数组的后缀数组。排好了 i mod 3 = 1、2 的后缀之后,就可以得到一个总的名次数组 R,其中那些 i mod 3 = 0 的后缀的名次还是未知的。接着对于所有 i mod 3 = 0 的 S(i),靠 T[i] 和 R(i + 1) 这两个关键字就可以对它们排序了。最后把排好序的 mod 3 = 1、2 和 mod 3 = 0 的后缀归并起来就是答案了。归并的时候,比较两个后缀 S(i) 和 S(j) 的方法也是看它们的前 3 个字符,如果都相同,那么比较 R(i + 1) 和 R(j + 1),若不可比(其中有一个是未知的)则再比较 R(i + 2) 和 R(j + 2)。

有了以上的优化,即使当中出现了需要递归的情况,每次递归求解的字符串长度也只有原来的 2 / 3,那么即使递归的层数再多,总的时间之和也是会收敛的。

以上我只是潦草地介绍一下,具体的还是自己看论文吧。论文写得还是蛮清楚的。尤其是最后有一个用 C++ 实现的代码,其中有很多细节实现地很巧妙,很值得学习。

3. 倍增算法

我是从 IOI 2004 国家集训队论文集中的一篇名为《后缀数组》的文章中学到这个算法的。该文章在 Google 上搜得到,讲得还是蛮清楚的。我在此就不多介绍了,请自己看文章。

倍增算法最大的优点是实现简单,速度也还可以,O(n log n)。如果程序的时间要求不是很紧的话,应该作为首选的算法。这里是我对倍增算法的实现。

4. 多个字符串的后缀数组

在很多问题中,都需要求多个字符串的后缀数组,也就是把多个字符串的所有后缀都放在一起排序。这个结构对于查找公共子串之类的问题是很有用的。后缀树是可以表示多个字符串的,但是 DC3 算法和倍增算法都只能求单个字符串的后缀数组。

其实多个字符串的后缀数组可以转化成单个字符串的后缀数组。比如要求 “abc” 和 “def” 这两个字符串的后缀数组,可以转化成求 “abc1def” 的后缀数组。其中 1 是字典顺仅次于结束符 0 的字符,它也不出现在任何字符串中。这样求出来的后缀数组和 “abc” 与 “def” 的后缀数组是等价的;只是多了一个以 1 开头的后缀,但它一定排序在最前面,很容易去掉。在倍增算法中,用 0 替代 1 好像也可以;在 DC3 算法中好像不能用 0 替代 1,但是我忘记怎么重现那个错误了,所以现在也不好说。但是用 1 肯定是没错的,这样符合 “结束符在字符串中不出现” 的原则。

这篇文章我写得比较潦草,因为我引用的几篇文章本身都写得很清楚了,我确实没有什么新发现。所以到此为止吧。

发表评论

电子邮件地址不会被公开。 必填项已用*标注