Suffix trees are a fundamental data structure in stringology, but their space usage, though linear, is an important problem for its applications. We design and implement a new compressed suffix tree targeted to highly repetitive texts, such as large genomic collections of the same species. Our suffix tree tree builds on Block Trees, a recent Lempel-Ziv-bounded data structure that captures the repetitiveness of its input. We use Block Trees to compress the topology of the suffix tree, and augment the Block Tree nodes with data that speeds up suffix tree navigation. Our compressed suffix tree is slightly larger than previous repetition-aware suffix trees based on grammars, but outperforms them in time, often by orders of magnitude. The component that represents the tree topology achieves a speed comparable to that of general-purpose compressed trees, while using 2.3--10 times less space, and might be of interest in other scenarios.
The function @math is the length of the longest common prefix (lcp) of strings @math and @math . The LCP array @cite_23 , @math , is defined as @math and @math for all @math , that is, it stores the lengths of the longest common prefixes between lexicographically consecutive suffixes of @math .
@cite_23
2143469992 2082173153 2052067273 2951300344
The longest-common-prefix (LCP) array is an adjunct to the suffix array that allows many string processing problems to be solved in optimal time and space. Its construction is a bottleneck in practice, taking almost as long as suffix array construction. In this paper, we describe algorithms for constructing the permuted LCP (PLCP) array in which the values appear in position order rather than lexicographical order. Using the PLCP array, we can either construct or simulate the LCP array. We obtain a family of algorithms including the fastest known LCP construction algorithm and some extremely space efficient algorithms. We also prove a new combinatorial property of the LCP values. In this paper we study the problem of finding maximally sized subsets of binary strings (codes) of equal length that are immune to a given number @math of repetitions, in the sense that no two strings in the code can give rise to the same string after @math repetitions. We propose explicit number theoretic constructions of such subsets. In the case of @math repetition, the proposed construction is asymptotically optimal. For @math , the proposed construction is within a constant factor of the best known upper bound on the cardinality of a set of strings immune to @math repetitions. Inspired by these constructions, we then develop a prefixing method for correcting any prescribed number @math of repetition errors in an arbitrary binary linear block code. The proposed method constructs for each string in the given code a carefully chosen prefix such that the resulting strings are all of the same length and such that despite up to any @math repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. In this construction, the prefix length is made to scale logarithmically with the length of strings in the original code. As a result, the guaranteed immunity to repetition errors is achieved while the added redundancy is asymptotically negligible. We describe a new binary encoding for numbers termed lexicographic continued fraction (LCF) representation that provides a one-to-one order preserving finite bit string representation for every rational. Conversion either way between binary integer numerator-denominator pair representation and LCF representation is shown feasible in time linear with bit string length, given registers of length sufficient to hold the numerator and denominator. LCF bit string length is about 2 max log 2 p, log 2 q for the irreducible fraction p q. Realization of arithmetic (+, −, ×, ÷ on LCF bit string encoded operands is shown feasible. Some relations between the theory of best rational approximation and the values represented by truncated LCF bit strings are noted to assess the feasibility of a finite precision arithmetic based on LCF representation. Let @math @math be a given set of @math string documents of total length @math , our task is to index @math , such that the @math most relevant documents for an online query pattern @math of length @math can be retrieved efficiently. We propose an index of size @math bits and @math query time for the basic relevance metric , where @math is the size (in bits) of a compressed full text index of @math , with @math time for searching a pattern of length @math . We further reduce the space to @math bits, however the query time will be @math , where @math is the alphabet size and @math is any constant.