Skip to content

构造Suffix Array的DC3算法

Suffix Array这个东西的确非常有用,很多关于字符串处理的题目构造一个SA就能迎刃而解。最近在SPOJ上看到了题目SUBST1,一眼看出来是用SA解的,兴冲冲的写了个nlogn的算法,连测试数据都没有出就交上去,结果没有悬念的TLE了(按说n=50000时nlogn算法应该可以不TLE的,比如说给50000个数排序肯定就不会TLE,可见SA的常数之大)……于是没办法,只好开始学SA的线性算法。

找到了这篇论文,似乎就是大家所说的三分法的“Skew Algorithm”的原始出处。作者在文章里说这种算法的基本原理是“Difference Cover”原则,并且在采样(Sample)的时候以3为模,所以这个算法叫DC3(Difference Cover modulo 3)。在本文里这个算法的名字就以原始论文为准了。

DC3算法的基本过程是这样的:首先构造出来一个superstring,这个串的每个字母都是原串的字母拼接上后面的两个字母,但这个串仅包含原串中下标模3不为0的位置。(递归地)求出这个串的SA,设为SA12。显然SA12中串的排列顺序与最终结果SA的排列顺序是相同的,只是SA12包含的串只有原串的2/3。

然后利用这个SA12和原串在线性时间内求出没有包含在SA12中的1/3的串的SA(也就是下标模3为0的那些串),设为SA0。求SA0的方法是:串的初始顺序是它们后面那个串在SA12中的顺序,然后再依据第一个字母进行一次RadixSort就可以了。也就是说SA0中的顺序可以仅用两个关键字来确定:第一关键字是第一个字母,第二关键字是后面的那个串在SA12中的位置。

现在得到了SA0和SA12,只需要把它们合并就可以得到最终的SA了,要想在线性时间内完成合并,需要在常数时间内完成比较。其实也不太难:当模为0的一个串与模为1的一个串比较时,需要比较它们的第一个字母与它们后面的那个串(都在SA12中),当模为0的一个串与模为2的一个串比较时,需要比较它们的前两个字母与它们去掉前两个字母以后的那个串(显然也都在SA12中)。

具体实现有点麻烦,我目前的代码基本上是完全抄的论文后面给的C++程序。不过运行速度真的很理想。因为程序里有一个很强的优化:当superstring中所有的字符都不相同时,可以直接用一遍RadixSort得到SA12,不用递归。经过这样的优化,递归地层数非常少,对于完全随机生成的长度为50000的英文字符串,求一次SA平均只需进行4次调用。所以实际时间效率非常高,常数不算大。

目前我对这个算法的理解还远不够深刻,所以讲的可能不易理解。有能力的话就看上面给出的原始论文吧,只看前三节就可以,后面讲了如何以牺牲一定时间为代价优化空间使用,我们是完全用不着的。

实例代码见上面的论文的附录A吧,我写得跟那个一样。

7 Comments

  1. evalls wrote:

    大牛….
    SA倍增算法的常数真的太bt了。

    Thursday, July 5, 2007 at 07:01 | Permalink
  2. crazyb0y wrote:

    请楼上的(和作者)不要自己写的常数太大就说算法不好!!!

    SUBST1 我用O(nlogn)的算法:
    1 2007-06-18 15:23:00 Jin Bin accepted 0.22 4216 C++

    排第一,比O(n)的快多了。

    Tuesday, July 10, 2007 at 17:40 | Permalink
  3. wywcgs wrote:

    据我测试的结果是KS算法(也就是你所说的三分法)常数很大……
    他理论复杂度的常数就很大,虽说那个triple完全不同就不用递归的优化确实效果不错,但是总的运行时间还是不小的。
    呃……我的看法是:你所说的那个“优化”,并不是一个优化,而是算法的必要组成部分,也就是递归的终止条件。

    Monday, July 23, 2007 at 20:48 | Permalink
  4. tianyi wrote:

    @wywcgs
    我看到的有些实现里没有这个优化,而是将待求字符串的长度等于1作为递归的终止条件的。

    Monday, July 23, 2007 at 21:01 | Permalink
  5. kamel wrote:

    能不能帖一个完整的代码?
    我觉得论文里面的好像有问题。。

    我太菜了。。

    Thx

    Saturday, May 24, 2008 at 12:40 | Permalink
  6. tianyi wrote:

    @kamel
    论文里面的代码完全没有问题,我觉得你直接复制粘贴也能用。

    Saturday, May 24, 2008 at 21:57 | Permalink
  7. KuFaaa wrote:

    论文代码里的一团for,看得我蛋疼。

    Wednesday, July 25, 2012 at 16:51 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*