We show how to build several data structures of central importance to string processing, taking as input the Burrows-Wheeler transform (BWT) and using small extra working space. Let @math be the text length and @math be the alphabet size. We first provide two algorithms that enumerate all LCP values and suffix tree intervals in @math time using just @math bits of working space on top of the input BWT. Using these algorithms as building blocks, for any parameter @math we show how to build the PLCP bitvector and the balanced parentheses representation of the suffix tree topology in @math time using at most @math bits of working space on top of the input BWT and the output. In particular, this implies that we can build a compressed suffix tree from the BWT using just succinct working space (i.e. @math bits) and any time in @math . This improves the previous most space-efficient algorithms, which worked in @math bits and @math time. We also consider the problem of merging BWTs of string collections, and provide a solution running in @math time and using just @math bits of working space. An efficient implementation of our LCP construction and BWT merge algorithms use (in RAM) as few as @math bits on top of a packed representation of the input output and process data as fast as @math megabases per second.
The remaining component required to build a compressed suffix tree (in the version described by Sadakane @cite_10 ) is the suffix tree topology, represented either in BPS @cite_19 (balanced parentheses) or DFUDS @cite_41 (depth first unary degree sequence), using @math bits. As far as the BPS representation is concerned, @cite_8 show how to build it from a CSA in @math time and compact space for any constant @math . Belazzougui @cite_21 improves this running time to the optimal @math , still working within compact space. V " a lim " a @cite_18 describe a linear-time algorithm that improves the space to @math bits on top of the LCP array (which however needs to be represented in plain form), while @cite_33 show how to build the DFUDS representation of the suffix tree topology in @math time using @math bits of working space on top of a structure supporting access to LCP array values in @math time.
@cite_18 @cite_33 @cite_8 @cite_41 @cite_21 @cite_19 @cite_10
2522621913 1988110322 2105633925 2146346985
The field of succinct data structures has flourished over the last 16 years. Starting from the compressed suffix array (CSA) by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing. We report the following advances in string indexing and analysis. We show that the BWT of a string @math can be built in deterministic @math time using just @math bits of space, where @math . Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of @math . Many fundamental string analysis problems can be mapped to such enumeration, and can thus be solved in deterministic @math time and in @math bits of space from the input string. We also show how to build many of the existing indexes based on the BWT, such as the CSA, the compressed suffix tree (CST), and the bidirectional BWT index, in randomized @math time and in @math bits of space. The previously fastest construction algorithms for BWT, CSA and CST, which used @math bits of space, took @math time for the first two structures, and @math time for the third, where @math is any positive constant. Contrary to the state of the art, our bidirectional BWT index supports every operation in constant time per element in its output. We show that the compressed suffix array and the compressed suffix tree for a string of length n over an integer alphabet of size σ ≤ n can both be built in O(n) (randomized) time using only O(n log σ) bits of working space. The previously fastest construction algorithms that used O(n log σ) bits of space took times O(n log log σ) and O(n loge n) respectively (where e is any positive constant smaller than 1). Suffix trees and suffix arrays are the most prominent full-text indices, and their construction algorithms are well studied. In the literature, the fastest algorithm runs in @math time, while it requires @math -bit working space, where @math denotes the length of the text. On the other hand, the most space-efficient algorithm requires @math -bit working space while it runs in @math time. It was open whether these indices can be constructed in both @math time and @math -bit working space. This paper breaks the above time-and-space barrier under the unit-cost word RAM. We give an algorithm for constructing the suffix array, which takes @math time and @math -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 @math time and @math -bit working space for any @math . 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 @math is not constant. Our algorithm can construct a suffix array and a suffix tree using optimal @math -bit working space while running in @math time and @math time, respectively. These are the first algorithms that achieve @math time with optimal working space. Moreover, for the special case where @math , we can speed up our suffix array construction algorithm to the optimal @math . Suffix tree is one of the most important data structures in string algorithms and biological sequence analysis. Unfortunately, when it comes to implementing those algorithms and applying them to real genomic sequences, often the main memory size becomes the bottleneck. This is easily explained by the fact that while a DNA sequence of length n from alphabet Σ e A,C,G,T can be stored in n log vΣv e 2n bits, its suffix tree occupiesO(n log n) bits. In practice, the size difference easily reaches factor 50. We report on an implementation of the compressed suffix tree very recently proposed by Sadakane (2007). The compressed suffix tree occupies space proportional to the text size, that is, O(n log vΣv) bits, and supports all typical suffix tree operations with at most log n factor slowdown. Our experiments show that, for example, on a 10 MB DNA sequence, the compressed suffix tree takes 10p of the space of the normal suffix tree. At the same time, a representative algorithm is slowed down by factor 30. Our implementation follows the original proposal in spirit, but some internal parts are tailored toward practical implementation. Our construction algorithm has time requirement O(n log n log vΣv) and uses closely the same space as the final structure while constructing it: on the 10MB DNA sequence, the maximum space usage during construction is only 1.5 times the final product size. As by-products, we develop a method to create Succinct Suffix Array directly from Burrows-Wheeler transform and a space-efficient version of the suffixes-insertion algorithm to build balanced parentheses representation of suffix tree from LCP information.