text: 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.
  @cite_18: 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.
  @cite_33: 
  @cite_8: 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 .
  @cite_41: This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our attention to trees of higher degree. We consider both cardinal trees (or k-ary tries), where each node has k slots, labelled 1,...,k , each of which may have a reference to a child, and ordinal trees, where the children of each node are simply ordered. Our representations use a number of bits close to the information theoretic lower bound and support operations in constant time. For ordinal trees we support the operations of finding the degree, parent, ith child, and subtree size. For cardinal trees the structure also supports finding the child labelled i of a given node apart from the ordinal tree operations. These representations also provide a mapping from the n nodes of the tree onto the integers 1, ..., n , giving unique labels to the nodes of the tree. This labelling can be used to store satellite information with the nodes efficiently.
  @cite_21: 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).
  @cite_19: We consider the implementation of abstract data types for the static objects: binary tree, rooted ordered tree and balanced parenthesis expression. Our representations use an amount of space within a lower order term of the information theoretic minimum and support, in constant time, a richer set of navigational operations than has previously been considered in similar work. In the case of binary trees, for instance, we can move from a node to its left or right child or to the parent in constant time while retaining knowledge of the size of the subtree at which we are positioned. The approach is applied to produce succinct representation of planar graphs in which one can test adjacency in constant time.
  @cite_10: We introduce new data structures for compressed suffix trees whose size are linear in the text size. The size is measured in bits; thus they occupy only O(n log|A|) bits for a text of length n on an alphabet A. This is a remarkable improvement on current suffix trees which require O(n log n) bits. Though some components of suffix trees have been compressed, there is no linear-size data structure for suffix trees with full functionality such as computing suffix links, string-depths and lowest common ancestors. The data structure proposed in this paper is the first one that has linear size and supports all operations efficiently. Any algorithm running on a suffix tree can also be executed on our compressed suffix trees with a slight slowdown of a factor of polylog(n).
summary: 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.