Breaking a time-and-space barrier in constructing full-text indices
Breaking a time-and-space barrier in constructing full-text indices
复制标题
DOI：
10.1109/sfcs.2003.1238199
复制
发表时间：
2003-10
期刊：
影响因子：
--
通讯作者：
W. Hon;K. Sadakane;W. Sung
中科院分区：
文献类型：
--
作者：
W. Hon;K. Sadakane;W. Sung
后缀树和后缀数组是最重要的全文索引，它们的构造算法也得到了很好的研究。长期以来，这些索引是否可以在O（n log n）时间和O（n log n）位工作空间中构造，其中n表示文本的长度。在文献中，最快的算法运行在O（n）时间，而它需要O（n log n）位的工作空间。而最节省空间的算法需要O（n）位的工作空间，运行时间为O（n log n）。本文打破了单位成本字RAM下长期存在的时间和空间障碍。对于字母长度固定的文本，我们给出了一个O（n）时间和O（n）位工作空间的后缀数组的构造算法。注意，时间和空间边界都是最优的。对于构造后缀树，我们的算法需要O（n log/sup /spl epsi//n）的时间和O（n）位的工作空间，任何0 < /spl epsi/ < 1。除此之外，我们的算法还可以用于构建其他现有的全文索引，如压缩后缀树，压缩后缀数组和FM索引。我们还研究了字母表A的大小不是常数的一般情况。我们的算法可以构造一个后缀数组和一个后缀树，使用最优的O（nlog|一|时间复杂度为O（n）|一|）时间和O（n log/sup /spl epsi//n）时间。这些是第一个算法，实现0（n log n）的时间与最佳的工作空间，在一个合理的假设，日志|一|= o（log n）。
Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. It has been open for a long time whether these indices can be constructed in both O(n log n) time and O(n log n)-bit working space, where n denotes the length of the text. In the literature, the fastest algorithm runs in O(n) time, while it requires O(n log n)-bit working space. On the other hand, the most space-efficient algorithm requires O(n)-bit working space while it runs in O(n log n) time. This paper breaks the long-standing time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array which takes O(n) time and O(n)-bit working space, for texts with constant-size alphabets. Note that both the time and the space bounds are optimal. For constructing the suffix tree, our algorithm requires O(n log/sup /spl epsi//n) time and O(n)-bit working space for any 0 < /spl epsi/ < 1. Apart from that, our algorithm can also be adopted to build other existing full-text indices, such as Compressed Suffix Tree, Compressed Suffix Arrays and FM-index. We also study the general case where the size of the alphabet A is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal O(n log |A|)-bit working space while running in O(n log log |A|) time and O(n log/sup /spl epsi//n) time, respectively. These are the first algorithms that achieve 0(n log n) time with optimal working space, under a reasonable assumption that log |A| = o(log n).