什么是当前最先进的后缀阵列构造算法？

Question

我正在寻找一种快速后缀阵列构造算法.我对实现的简易性和原始速度比渐近复杂度更感兴趣(我知道后缀数组可以在O(n)时间内通过后缀树构造,但是需要很多空间;显然其他算法都有糟糕的最糟糕的大O复杂性,但在实践中运行得相当快).我不介意生成LCP阵列作为副产品的算法,因为我无论如何都需要一个用于我自己的目的.

我找到了各种后缀数组构造算法的分类,但它已经过时了.我听说过SA-IS,qsufsort和BPR,但我真的不知道它们如何相互比较,也没有更好的算法.考虑到后缀阵列字段现在看起来有多热,我希望其他一些算法在发布之后已经取代了那些算法.我似乎回想起一篇描述一种叫做"分裂"的快速算法的论文,但我现在找不到它的生命.

那么,目前的艺术水平是什么？理想情况下,我想要一份当前最佳算法的简短列表(如果可能的话,还有链接)以及他们相对优势和劣势的快速概述.

Answer 1

目前,Yuta Mori提供的最好的Suffix-Array构造函数是LibDivSufSort:http: //code.google.com/p/libdivsufsort/

它使用诱导排序方法(基本上,在排序所有以"A*"开头的字符串后,您可以引出字符串"BA*""CA*""DA*"等的排序)

它的效率和对退化病例的良好处理在各地都受到称赞.它也是最快的,并使用最佳内存量(5N).许可证是不显眼的,因此该算法被集成到其他几个程序中,例如Ilya Grebnov的libbsc压缩库. http://libbsc.com/default.aspx

为了便于比较,您可以在此页面找到链接的后缀阵列压缩基准:http: //code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks 和此页面 http://homepage3.nifty.com/wpage/benchmark /index.html

该基准测试还列出了许多其他有价值的SACA实现.然而,出于许可和效率原因,我建议其中包括libdivsufsort.

编辑:显然,据说MSufsort即将推向版本4,并且应该比Divsufsort快得多.如果这是对的,它将成为新的SACA冠军.但是,我们还没有发布日期,这将是alpha内容.因此,如果您现在需要经过验证的实施,libdivsufsort仍然是最佳选择.

还要注意,这些"最佳SACA实现"不使用"一种构造算法",而是结合了几种优化技巧,这使得它们难以总结.

Answer 2

http://code.google.com/p/libdivsufsort/source/browse/wiki/SACA_Benchmarks.wiki提供了您想要的最快算法列表.

在上述基准测试中,kvark的实施是大多数情况下最快的.您可以在http://www.kvatom.com/archon上找到该代码.

libdivsufsort是IT算法和Induced Sorting后期处理的组合.选择后缀的子集就像诱导排序算法一样,但不是通过诱导排序递归地解决它,而是通过IT算法对它们进行排序.

libdivsufsort和kvark的实现都基于IT的算法.

KA的算法类似于IT的算法,它出现在99.它们都将后缀分为两类:S型或L型.如果第i个后缀小于第(i + 1)个后缀,则为类型S; 否则它是类型L.在对所有类型S后缀进行排序后,我们可以推导出所有类型L后缀的顺序,然后我们就完成了.

KA算法和IT算法之间的区别在于:KA使用递归对子字符串进行排序,而IT的算法则采用Multikey Quicksort/MSD /插入排序.