Two Efficient Algorithms for Linear Time Suffix Array Construction
Two Efficient Algorithms for Linear Time Suffix Array Construction
复制标题
两种高效的线性时间后缀数组构建算法
DOI：
10.1109/tc.2010.188
复制
发表时间：
2011-10-01
影响因子：
3.7
通讯作者：
Chan, Wai Hong
中科院分区：
文献类型：
--
作者：
Nong, Ge;Zhang, Sen;Chan, Wai Hong
本文提出了两种构造线性时间后缀数组的有效算法。这两个算法使用分治和递归技术实现了它们的线性时间复杂度。与其他线性时间后缀数组构造算法（SACA）的区别在于，为简化问题而对变长最左S型（LMS）子串和定长d临界子串进行采样，以及对这些采样子串进行排序的简单算法：变长LMS子串的归纳排序算法和定长d临界子串的基数排序算法.非常简单的排序机制使我们的算法成为一个优雅的设计框架，反过来，令人惊讶的简洁实现。我们所提出的算法的全功能的示例实现只需要大约100行的C代码，这只是KA算法的实现的1/10，可与KS算法相媲美。实验结果表明，这两个新提出的算法产生最好的时间和空间效率在所有现有的线性时间SACA。
We present, in this paper, two efficient algorithms for linear time suffix array construction. These two algorithms achieve their linear time complexities, using the techniques of divide-and-conquer, and recursion. What distinguish the proposed algorithms from other linear time suffix array construction algorithms (SACAs) are the variable-length leftmost S-type (LMS) substrings and the fixed-length d-critical substrings sampled for problem reduction, and the simple algorithms for sorting these sampled substrings: the induced sorting algorithm for the variable-length LMS substrings and the radix sorting algorithm for the fixed-length d-critical substrings. The very simple sorting mechanisms render our algorithms an elegant design framework, and, in turn, the surprisingly succinct implementations. The fully functional sample implementations of our proposed algorithms require only around 100 lines of C code for each, which is only 1/10 of the implementation of the KA algorithm and comparable to that of the KS algorithm. The experimental results demonstrate that these two newly proposed algorithms yield the best time and space efficiencies among all the existing linear time SACAs.