我正在寻找一种快速的后缀数组构造算法。我对易于实现和原始速度比渐近复杂性更感兴趣（我知道可以在 O(n) 时间内通过后缀树构造后缀数组，但这需要很多空间；显然其他算法有糟糕的最坏情况大 O 复杂性，但在实践中运行得非常快）。我不介意生成 LCP 数组作为副产品的算法，因为无论如何我都需要一个用于我自己的目的。
我找到了各种后缀数组构造算法的分类，但它已经过时了。我听说过SA-IS、qsufsort和BPR，但我真的不知道它们之间的比较，也不知道是否有更好的算法。考虑到 suffix-array 领域现在看起来有多热，我希望其他一些算法在它们发布后已经取代了它们。我似乎记得曾经看过一篇描述一种名为“split”的快速算法的论文，但我现在一辈子都找不到它。
那么，目前最先进的技术是什么？理想情况下，我想要一份当前最佳算法的简短列表（如果可能，请附上链接）并快速概述它们的相对优势和劣势。
目前，已知最好的 Suffix-Array 构造函数是 LibDivSufSort，作者 Yuta Mori： 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 实现”不使用“一种构造算法”，而是结合了几种优化技巧，这使得它们难以总结。
https://github.com/y-256/libdivsufsort/blob/wiki/SACA_Benchmarks.md提供了您想要的最快算法列表。
在上述基准测试中，kvark 的实现在大多数情况下是最快的。您可以在https://github.com/kvark/dark-archon上找到代码。
libdivsufsort 是 Itoh-Tanaka 算法和 Induced Sorting 后处理的组合。后缀的一个子集就像诱导排序算法一样被挑选出来，但不是通过诱导排序递归地解决它，而是通过 IT 的算法对其进行排序。
libdivsufsort 和 kvark 的实现都是基于 IT 的算法。
Ko-Aluru 的算法和 IT 的算法类似，出现在 99 中。它们都将后缀分为 2 类：S 型或 L 型。如果第 i 个后缀小于第 (i+1) 个后缀，它是 S 型；否则就是L型。把所有S型后缀排序后，我们就可以推导出所有L型后缀的顺序，就大功告成了。
KA算法与IT算法的区别在于：KA使用递归对子串进行排序，而IT算法诉诸Multikey Quicksort/MSD/insertion sort。
你可以看看：
后缀数组和压缩后缀数组快速浏览 R Grossi - 理论计算机科学，2011
可能不再以您想象的速度开发新的后缀数组算法。为了走在最前沿，我建议查看与后缀数组一起使用的数据结构，并查看与后缀数组相关的数学论文：Schürmann、Munro、He 等