Alphabet-independent linear-time construction of compressed suffix arrays using o(n log n)-bit working space
The suffix array is a fundamental index data structure in string algorithms and bioinformatics, and the compressed suffix array (CSA) and the FM-index are its compressed versions. Many algorithms for constructing these index data structures have been developed. Recently, Hon et al. [W.K. Hon, K. Sadakane, W.K. Sung, Breaking a time-and-space barrier in constructing full-text indices, in: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003, pp. 251-260] proposed a construction algorithm using O(n log log vertical bar Sigma vertical bar) time and O(n log vertical bar Sigma vertical bar)-bit working space, which is the fastest algorithm using O(n log vertical bar Sigma vertical bar)-bit working space. In this paper we give an efficient algorithm to construct the index data structures. Our algorithm constructs the suffix array, the CSA, the FM-index, and Burrows-Wheeler transform using alphabet-independent O(n) time and O(n log vertical bar Sigma vertical bar log(vertical bar Sigma vertical bar)(alpha) n)-bit working space, where alpha = log(3) 2. Our algorithm takes less time and more space than Hon et al.'s algorithm. Our algorithm uses least working space among alphabet-independent linear-time algorithms. (c) 2007 Elsevier B.V. All rights reserved.
compressed suffix array index data structure fm-index burrows-wheeler transform