什么是当前最新的后缀数组构造algorithm？

我正在寻找一个快速的后缀数组构造algorithm。 我对易于实现和原始速度比渐近复杂性更感兴趣（我知道在O（n）时间后缀数组可以通过后缀树来构造，但是需要很多空间;显然其他algorithm有坏的最坏的情况下，大O的复杂性，但在实践中跑得相当快）。 我不介意产生LCP数组作为副产品的algorithm，因为我为了自己的目的需要一个algorithm。

我发现了各种后缀数组构造algorithm的分类 ，但已经过时了。 我听说过SA-IS ， qsufsort和BPR ，但是我不知道它们是如何相互比较的，也没有更好的algorithm。 考虑到后缀数组字段看起来有多热，我期望其他一些algorithm已经取代了自发布以来的algorithm。 我似乎记得遇到一篇论文，描述了一种叫做“split”的快速algorithm，但现在我无法在我的生活中find它。

那么，现在的艺术状况如何呢？ 理想情况下，我希望列出当前最好的algorithm（如有可能，请链接），并简要概述其优缺点。

Answer 1

目前，已知的最好的后缀数组构造函数是由Yuta Mori提供的LibDivSufSort： http : //code.google.com/p/libdivsufsort/

它使用诱导sorting方法（基本上，在sorting所有以“A *”开头的string之后，可以引起string“BA *”“CA *”“DA *”的sorting等）

它的效率和对退化病例的处理很好。 这也是最快的，并使用最佳的内存量（5N）。 该许可证是不显眼的，因此该algorithm被集成到其他几个程序中，例如由Ilya Grebnov编写的libbsc压缩库。 http://libbsc.com/default.aspx

为了便于比较，您可以在此页面find一个后缀数组压缩基准testing： http : //code.google.com/p/libdivsufsort/wiki/SACA_Benchmarks和此页面http://homepage3.nifty.com/wpage/benchmark /index.html

基准还列出了许多其他有价值的SACA实施。 不过，对于许可证和效率的原因，我会推荐其中的libdivsufsort。

编辑：显然，MSufsort据说即将推向版本4，并应该变得比Divsufsort相当快。 如果那是对的，它将成为新的SACA冠军。 但是，我们还没有发布date，这将是alpha的东西。 所以如果你现在需要一个经过validation的实现，libdivsufsort仍然是最好的select。

还要注意，这些“最好的SACA实现”并不使用“一个构造algorithm”，而是结合了几个优化技巧，这使得它们很难总结。

Answer 2

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

在上述基准中，kvark的实现是大多数情况下最快的。 您可以在http://www.kvatom.com/archon上find代码。;

libdivsufsort是ITalgorithm和诱导sorting后处理的组合。 后缀的子集就像引入的sortingalgorithm一样被挑选出来，而不是通过诱导sorting来recursion求解，而是通过ITalgorithm来sorting。

libdivsufsort和kvark的实现都是基于IT的algorithm。

KA的algorithm类似于ITalgorithm，它出现在99中。它们都将后缀分成两类：S类或L类。如果第i个后缀小于第（i + 1）个后缀，则它的typesS; 否则就是L型。sorting完所有S型后缀后，我们可以推导出所有L型后缀的顺序，然后我们就完成了。

KAalgorithm和ITalgorithm的不同之处在于：KA使用recursion对子串进行sorting，而ITalgorithm则使用Multikey Quicksort / MSD /插入sorting。

Answer 3

你可以看看：

对后缀数组和后缀压缩数组的快速浏览R Grossi – 理论计算机科学，2011年

可能新的后缀数组algorithm不再以您想象的速度发展。 为了避免出现问题，我build议查看与后缀数组一起使用的数据结构，并查看有关后缀数组相关math的论文：Schürmann，Munro，He等