PaperlayerView exact revision on arXiv

Source-linked AI summary

Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space

Travis Gagie, Gonzalo Navarro, Nicola Prezza

arXiv:1809.02792v2cs.DS

TL;DR

Repetitive-text indexes could count patterns in O(r) space but lacked efficient locating, while related self-indexes often required larger space. The paper extends run-length indexing and adds compressed text and suffix-tree structures, achieving optimal general and packed counting and locating within stated r-bounded spaces.

  • Problem

    The RLFM-index counts pattern occurrences in O(r) space but does not efficiently locate them, while locating and extraction in prior indexes require larger space.

  • Method

    The paper extends the RLFM-index and builds BWT-run-based structures for text extraction, suffix-array and LCP access, and compressed suffix-tree operations.

  • Results

    The resulting indexes support optimal general counting and locating in O(r log log_w(σ + n/r)) space, packed optimality with increased space, and competitive empirical locating performance.

  • Takeaways & Limitations

    BWT-run-bounded space suffices for efficient counting and locating, while O(r log(n/r)) space supports text replacement, direct array access, and full suffix-tree functionality.

  • Takeaways & Limitations

    Efficient random access to the text is provided with O(r log(n/r)) space, leaving open whether it is possible within O(r) space.

Abstract

from arXiv · show

Indexing highly repetitive texts - such as genomic databases, software repositories and versioned text collections - has become an important problem since the turn of the millennium. A relevant compressibility measure for repetitive texts is r, the number of runs in their Burrows-Wheeler Transforms (BWTs). One of the earliest indexes for repetitive collections, the Run-Length FM-index, used O(r) space and was able to efficiently count the number of occurrences of a pattern of length m in the text (in loglogarithmic time per pattern symbol, with current techniques). However, it was unable to locate the positions of those occurrences efficiently within a space bounded in terms of r. In this paper we close this long-standing problem, showing how to extend the Run-Length FM-index so that it can locate the occ occurrences efficiently within O(r) space (in loglogarithmic time each), and reaching optimal time, O(m + occ), within O(r log log w (σ + n/r)) space, for a text of length n over an alphabet of size σ on a RAM machine with words of w = Ω(log n) bits. Within that space, our index can also count in optimal time, O(m). Multiplying the space by O(w/ log σ), we support count and locate in O(dm log(σ)/we) and O(dm log(σ)/we + occ) time, which is optimal in the packed setting and had not been obtained before in compressed space. We also describe a structure using O(r log(n/r)) space that replaces the text and extracts any text substring of length ` in almost-optimal time O(log(n/r) + ` log(σ)/w). Within that space, we similarly provide direct access to suffix array, inverse suffix array, and longest common prefix array cells, and extend these capabilities to full suffix tree functionality, typically in O(log(n/r)) time per operation.

1 Introduction

Highly repetitive text collections create a need for indexes that exploit BWT-run compressibility while supporting counting, locating, extraction, and suffix-tree operations. This paper addresses limitations of prior repetitive-text indexes with new structures bounded by r.

  • Motivation: Highly repetitive collections arise in genomic databases, versioned documents, software repositories, and other growing sequence datasets.Such collections contain substantial repeated material despite rapidly increasing total size.
  • Motivation: Advanced access across versioned collections, including counting and locating pattern occurrences, remains more challenging than storing document edits.
  • Motivation: FM-indexes can represent sequences near statistical entropy, but that measure does not capture repetitiveness in massive genomic datasets.The cited discussion notes that current FM-index software uses at least 2 bits per base.
  • Related work: The RLFM-index uses O(r) words and counts pattern occurrences efficiently, but it does not efficiently locate their positions within O(r) space.Here, r denotes the number of equal-letter runs in the text's BWT.
  • Related work: Prior structures traded locating, extraction, and suffix-tree functionality against larger bounds based on z, g, e, or n/s rather than only BWT runs.The reported space measures include O(z), O(g), O(e), and Θ(n/s), with differing time guarantees.
  • Contributions: The paper extends run-based indexing to locate occurrences within O(r) space and provides optimal counting and locating with O(r log log_w(σ + n/r)) space.Its contributions also include compressed text replacement, substring extraction, array access, and suffix-tree functionality.

2 Basic Concepts

This section introduces strings, suffix-based indexes, the BWT, and FM-index backward search as foundations for compressed self-indexing. It also frames the limitations of existing compressed structures for locating, extracting, and suffix-tree operations.

  • Suffix-based structures: The suffix array stores suffix starting positions in lexicographic order, while the suffix tree compactly represents the same suffix set.The inverse suffix array gives each text position's suffix rank, and LCP stores adjacent suffixes' longest common-prefix lengths.
  • Self-index functionality: A self-index supports counting, locating, and extracting occurrences or substrings while potentially replacing the original text.Extraction is challenging when the self-index must use little space.
  • BWT and LF: The BWT reorders text symbols according to suffix-array order, and LF maps a BWT position to the suffix beginning one text position earlier.The relation is SA[LF(p)] = SA[p] −1.
  • FM-index search: FM-index backward search processes a pattern from right to left, maintaining the suffix-array interval of matching suffixes.The final interval [sp..ep] contains occ = ep −sp + 1 occurrences, and O(m) rank computations dominate counting.
  • Existing performance: An FM-index can count in O(m log log_w σ), locate each occurrence in O(s), and extract ℓ symbols in O(s + ℓ) using O(n/s) additional words.The space is measured on top of the empirical entropy of the text.
  • Run-bounded compression: The RLFM-index uses O(r) words and counts in O(m log log_w(σ + n/r)) time, but existing run-length approaches require larger space for locating and extraction.Prior suffix-tree approaches also lacked the desired O(r polylog(n)) space guarantee.

3 Locating Occurrences

The section turns an RLFM-index search interval into occurrence locations by identifying one suffix-array cell and extending from it to neighboring cells. This yields run-bounded locating with logarithmic predecessor-query time and a space-time tradeoff for faster reporting.

  • Sampling mechanism: The sampling scheme marks text characters at BWT run borders, enabling phrase-based predecessor structures to recover neighboring suffix-array positions.The proof follows three adjacent BWT cells through consecutive LF applications until reaching a sampled phrase position.
  • Finding a suffix-array foothold: O(r) words suffice to find a pattern's suffix-array interval and one known suffix-array cell in O(m log log_w(σ + n/r)) time.The construction augments an RLFM-index with predecessor structures over sampled BWT characters.
  • Maintaining the foothold: The method propagates a known cell through LF during backward search, preserving knowledge of one suffix-array value for the extended pattern interval.When the preceding BWT character differs, a predecessor query over sampled run-border characters recovers a suitable cell.
  • Extending the interval: A known suffix-array cell provides a toehold from which neighboring cells can be computed in O(log log_w(n/r)) time.The permutation φ and its inverse represent the preceding and following suffix-array values.
  • Locating bound: O(r) words support counting in O(m log log_w(σ + n/r)) time and reporting all occ locations in O(occ · log log_w(n/r)) total time.Predecessor searches over a combined universe match the per-symbol backward-search bound.
  • Space-time tradeoff: O(rs) words allow computing s′ neighboring suffix-array cells in O(log log_w(n/r) + s′) time for any s′ ≤ s.The same tradeoff extends to LCP entries, with the corresponding access bound.

4 Counting and Locating in Optimal Time

The section achieves optimal pattern counting and locating by processing overlapping length-s metasymbols while controlling the transformed BWT's run count. The resulting structures support unpacked and packed optimal-time operations within space bounded by r.

  • Metasymbol transformation: The transformed text T* preserves suffix order, while its BWT has O(rs) runs, keeping the mapped RLFM-index within O(rs) space.A compact trie maps existing length-s substrings to an effective alphabet of size O(rs).
  • Counting: O(rs) space supports counting in O(m + (m/s) log log_w(σ + n/r)) time, with O(r log log_w(σ + n/r)) space yielding O(m) counting.The construction maps length-s text substrings to a compact effective alphabet and simulates backward search on the transformed text.
  • Locating: O(rs) space supports locating occ pattern occurrences in O((1 + log log_w(n/r)/s) · occ) time after counting.The structure computes the suffix-array interval and returns one occurrence, then uses sampled information to report the remaining positions.
  • Unpacked optimal time: O(r log log_w(σ + n/r)) space supports counting in O(m) time and locating in O(m + occ) time.This instantiation sets s = log log_w(σ + n/r).
  • Packed optimal time: O(rw log σ log_w(σ + n/r)) words support packed counting in O(⌈m log(σ)/w⌉) time and locating in O(occ) time after counting.The packed structure increases the space to support chunked pattern processing at word-level speed.

5 Accessing the Text, the Suffix Array, and Related Structures

The paper replaces the text with an r-bounded hierarchical representation that supports near-optimal substring extraction and direct access to suffix-array-related structures. These capabilities enable compressed suffix-tree functionality.

  • Accessing the text: O(r log(n/r)) words support extracting any length-ℓ text substring in O(log(n/r) + ℓ log(σ)/w) time.The representation uses O(log(n/r)) levels and explicitly stores packed characters at the last level.
  • Accessing the text: The hierarchical extractor maps a query through primary occurrences across progressively smaller half-blocks until reaching explicitly stored characters.Blocks and half-blocks store coordinates of primary occurrences in the next level.
  • Accessing SA: BWT runs induce repeated substrings in the differential suffix array DSA, allowing analogous hierarchical access to suffix-array values.Any DSA substring has a copy covering positions associated with BWT run beginnings.
  • Accessing SA: O(r log(n/r)) words support retrieving any ℓ consecutive suffix-array values in O(log(n/r) + ℓ) time.The structure extracts logarithmic-size blocks of SA and combines them for longer queries.
  • Accessing ISA and LCP: O(r log(n/r)) words support retrieving any ℓ consecutive ISA values and LCP values in O(log(n/r) + ℓ) time.LCP access can be obtained without knowing the corresponding text positions.
  • Compressed search: Within O(r log(n/r)) words, counting takes O(m) time and locating occ occurrences takes O(occ) time after counting.The suffix-array access structure reports suffix-array cells in the pattern interval, yielding the occurrence positions.

6 A Run-Length Compressed Suffix Tree

The paper implements a compressed suffix tree using run-bounded space, supporting broad suffix-tree functionality through compressed suffix-array, LCP, and differential-LCP structures. The resulting representation uses O(r log(n/r)) words, with most navigation operations taking O(log(n/r)) time.

  • Compressed suffix-tree representation: Suffix-tree nodes are identified by the suffix-array intervals SA[vl..vr] they cover, avoiding explicit storage of the tree.The representation builds on primitives over suffix-array and LCP intervals.
  • Limitations: The approach cannot use the analogous differential-TDE solution within the desired space bounds because the required equivalent of Lemma 16 does not hold.This constrains the treatment of operations relying on TDE, including the discussed LAQT route.
  • Operation complexities: O(log(n/r)) time supports SA, ISA, LCP, RMQ, PSV, and NSV operations, while extended PSV′ and NSV′ take O(log(n/r) + log log_w r).The stated bounds combine the paper’s array-access and LCP-primitive structures.
  • Compressed suffix-tree representation: O(r log(n/r)) words represent a compressed suffix tree supporting the operation complexities listed in Table 4.The bound is stated for texts whose BWT contains r runs.
  • Differential-LCP representation: A run-length context-free grammar of size O(r log(n/r)) and height O(log(n/r)) represents the differential LCP array DLCP.The grammar supports the required RMQ, PSV, NSV, PSV′, and NSV′ primitives.
  • Operation complexities: Child(v, a) is implemented in O(log(n/r) log σ) time by binary searching among LCP minima and extracting the relevant letter.The method uses extended RMQ′ queries to locate minima and compares the extracted letter with a.

7 Experimental results

Experiments compare the O(r)-space r-index with indexes based on Lempel-Ziv parsing, grammars, BWT runs, and CDAWGs across repetitive datasets. The r-index achieves much faster locating while remaining compact, but its space advantage weakens as repetitiveness decreases.

  • Locate-time comparison: 100–300 nanoseconds per occurrence: r-index locating was 10–100 times faster than Lempel-Ziv- and grammar-based indexes on all datasets.The compared indexes used 45%–105% of r-index space, while remaining 7–100 times slower.
  • Locate-time comparison: 20–500 times slower: rlcsa matched r-index space but remained substantially slower; with 1.7–4.4 times more space, it was still 5–100 times slower.This comparison covers practical space-time tradeoffs for the r-based alternative.
  • Locate-time comparison: 60 times larger: cdawg was almost twice as fast as r-index but substantially larger, excluding it from competition among small indexes.The comparison highlights a speed-space trade-off rather than a universal speed advantage.
  • Space usage: 2–4 words per run: r-index used fewer words per structural unit than lzi and hyb per phrase and slp per grammar symbol.This reduced the practical space gap suggested by comparing r, z, and g.
  • Scalability: 0.88 bits per symbol: r-index space on the complete Influenza collection, versus 4.75 for the FM-index and 0.22–0.52 for the other compressed indexes.The r-index used 18% of the classic FM-index space while remaining 10–100 times faster than the other compressed indexes.
  • Scalability: After 8% of the Influenza collection: r-index crossed below 2 bits per symbol, whereas the other indexes did so after processing 3%.The collection was less repetitive than the earlier benchmark datasets, and r was more sensitive than g and z to decreasing repetitiveness.

8 Construction

The construction algorithms build the paper’s BWT-run-bounded structures with space and time governed by r, while allowing linear-time construction when O(n) workspace is available.

  • Basic structures: O(r) space builds the basic structures in O(n log r) time, and the text is no longer needed after constructing the run-length encoded BWT.The construction scans the text right to left and then builds predecessor structures supporting LF-steps and rank queries.
  • Extended locating structures: O(rs) space and O(n log r + n log log_w(n/r)) time build the extended structure supporting the locating machinery.The construction collects run-boundary information and nearby positions through an LF traversal.
  • Optimal counting and locating: With s = log log_w(σ + n/r), the construction takes O(n(log r + log log_w(n/r))) time and O(rs) space.This bound combines BWT construction with the structures needed for optimal counting and locating.
  • Construction with linear workspace: O(n) construction space enables linear-time construction of the structures, apart from the deterministic trie dictionaries requiring O(rs(log log σ)^2) time.In this setting, LF-steps use constant-time bitvector operations and suffix-array construction can be linear time.
  • Text and array access: O(n log log_w(σ + n/r)) time and O(r log(n/r)) working space build the text-extraction structure once the basic structure is available.The construction cost is stated after the basic structure of Lemma 1 has been built.
  • LCP access: The LCP-access structure combines suffix-array access with a PLCP extension using s = log(n/r).The construction can use O(n) time and space, while the PLCP component can also be built within O(r log(n/r)+rs) space after constructing SA, ISA, and extraction structures.

9 Conclusions

The paper closes the problem of efficient locating within BWT-run-bounded space and extends the same framework to compressed text, array, and suffix-tree functionality. It also identifies open questions about O(r)-space access and practical deployment.

  • Main conclusion: O(r log log_w(σ+n/r)) space supports counting in O(m) time and locating in O(occ) time, while O(r) space supports both operations with logarithmic-time penalties.The O(r)-space index counts in O(m log log_w(σ+n/r)) time and locates in O(occ log log_w(n/r)) time.
  • Main conclusion: O(rw log σ log_w(σ+n/r)) space supports packed counting in O(⌈m log(σ)/w⌉) time and locating in that time plus occ.These are the stated optimal packed-setting bounds.
  • Extended functionality: O(r log(n/r)) space supports consecutive access to the text, SA, ISA, and LCP, and typically supports full suffix-tree navigation in O(log(n/r)) time per operation.The same space bound provides direct access to the principal suffix-array-related structures.
  • Context: The BWT-run measure captures compressibility in highly repetitive collections, but the paper notes that the original run-length FM-index could not locate occurrences efficiently.This motivated later indexes based on Lempel-Ziv parses, grammars, and compact automata.
  • Subsequent research: The work also motivated run-length grammars and related bounds connecting BWT-run structure with other repetitiveness measures.The paper describes follow-up constructions based on locally consistent parsing and bidirectional macro schemes.
  • Open questions: Efficient random access to the text and arbitrary suffix-array cells still requires O(r log(n/r)) space in the presented results.Whether sublinear-time random access is possible within O(r) space remains open.
  • Practical scope: Practical deployment still requires algorithm engineering, including construction for very large datasets and improved behavior on collections with lower repetitiveness.The paper also describes ongoing work toward software integration and hybridization with the classical FM-index.
Loading 1809.02792v2…