Simple Linear Work Suffix Array Construction
Simple Linear Work Suffix Array Construction
复制标题
DOI：
10.1007/3-540-45061-0_73
复制
发表时间：
2003-06
期刊：
影响因子：
--
通讯作者：
Juha Kärkkäinen;P. Sanders
中科院分区：
文献类型：
--
作者：
Juha Kärkkäinen;P. Sanders
后缀数组以排序顺序表示字符串的后缀。作为后缀树的一种更简单、更紧凑的替代方法，它是全文索引和其他字符串处理任务的重要工具。本文介绍了一种在整数字母表上构造后缀数组的斜算法，该算法可以用整数排序作为唯一的非平凡子程序，在线性时间内实现：1.从位置simod 3 → 0开始递归地对后缀进行排序。2.利用第一步中得到的信息对剩余的后缀进行排序。3.合并第一步和第二步中得到的两个排序序列。该算法比以前的线性时间算法简单得多，因为以前的算法都是基于更复杂的后缀树数据结构。由于排序是一个很好的研究问题，我们获得了其他几种计算模型的最佳算法，例如，外部存储器与并行磁盘，高速缓存不经意，和并行。BSP和EREW-PRAM的适应性比以前已知的最好的算法渐近快。
A suffix array represents the suffixes of a string in sorted order. Being a simpler and more compact alternative to suffix trees, it is an important tool for full text indexing and other string processing tasks. We introduce theskew algorithmfor suffix array construction over integer alphabets that can be implemented to run in linear time using integer sorting as its only nontrivial subroutine:1.recursively sort suffixes beginning at positionsimod 3 ≠ 0.2.sort the remaining suffixes using the information obtained in step one.3.merge the two sorted sequences obtained in steps one and two.The algorithm is much simpler than previous linear time algorithms that are all based on the more complicated suffix tree data structure. Since sorting is a well studied problem, we obtain optimal algorithms for several other models of computation, e.g. external memory with parallel disks, cache oblivious, and parallel. The adaptations for BSP and EREW-PRAM are asymptotically faster than the best previously known algorithms.