suffix-array - 目前最先进的后缀数组构造算法是什么？

Question

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

我找到了taxonomy of various suffix array construction algorithms ，但它已经过时了。我听说过SA-IS , qsufsort ，和 BPR ，但我真的不知道它们如何相互比较，也不知道是否有更好的算法。考虑到后缀数组领域现在似乎有多热门，我预计其他一些算法自发布以来已经取代了它们。我似乎记得曾经看过一篇论文，描述了一种名为“split”的快速算法，但我现在怎么也找不到它。

那么，目前的技术水平如何？理想情况下，我想要一份当前最佳算法的简短列表(如果可能的话，带有链接)并快速概述它们的相对优点和缺点。

Answer 1

目前，已知最好的后缀数组构造函数是 Yuta Mori 的 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

该基准测试还列出了许多其他有值(value)的 SACA 实现。尽管如此，出于许可和效率的原因，我建议其中使用 libdivsufsort。

编辑:显然，MSufsort 据说很快就会走向版本 4，并且应该比 Divsufsort 更快。如果这是正确的，它将成为新的SACA冠军。但我们还没有确定发布日期，这将是 alpha 版本。因此，如果您现在需要经过验证的实现，libdivsufsort 仍然是最佳选择。

还要注意，这些“最佳 SACA 实现”并不使用“一种构造算法”，而是结合了多种优化技巧，这使得它们难以总结。