Composite repetition-aware data structures
From MaRDI portal
Abstract: In highly repetitive strings, like collections of genomes from the same species, distinct measures of repetition all grow sublinearly in the length of the text, and indexes targeted to such strings typically depend only on one of these measures. We describe two data structures whose size depends on multiple measures of repetition at once, and that provide competitive tradeoffs between the time for counting and reporting all the exact occurrences of a pattern, and the space taken by the structure. The key component of our constructions is the run-length encoded BWT (RLBWT), which takes space proportional to the number of BWT runs: rather than augmenting RLBWT with suffix array samples, we combine it with data structures from LZ77 indexes, which take space proportional to the number of LZ77 factors, and with the compact directed acyclic word graph (CDAWG), which takes space proportional to the number of extensions of maximal repeats. The combination of CDAWG and RLBWT enables also a new representation of the suffix tree, whose size depends again on the number of extensions of maximal repeats, and that is powerful enough to support matching statistics and constant-space traversal.
Recommendations
Cites work
- A universal algorithm for sequential data compression
- Combinatorial Pattern Matching
- Complete inverted files for efficient text retrieval and analysis
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- Indexing compressed text
- Log-logarithmic worst-case range queries are possible in space theta(N)
- LZ77-based self-indexing with faster pattern matching
- On compressing and indexing repetitive sequences
- On maximal repeats in strings
- On the Complexity of Finite Sequences
- On the structure of compacted subword graphs of Thue-Morse words and their applications
- Orthogonal range searching on the RAM, revisited
- Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
- Stronger Lempel-Ziv based compressed text indexing
- The structure of subword graphs and suffix trees of Fibonacci words
- Versatile succinct representations of the bidirectional Burrows-Wheeler transform
Cited in
(24)- Time-space trade-offs for Lempel-Ziv compressed indexing
- FM-index of alignment with gaps
- A faster implementation of online RLBWT and its application to LZ77 parsing
- Universal compressed text indexing
- Flexible indexing of repetitive collections
- Top tree compression of tries
- Logarithmic equal-letter runs for BWT of purely morphic words
- Dynamic index and LZ factorization in compressed space
- Refining the \(r\)-index
- Fast algorithms for finding a minimum repetition representation of strings and trees
- Document listing on repetitive collections with guaranteed performance
- Grammar-compressed indexes with logarithmic search time
- Faster repetition-aware compressed suffix trees based on block trees
- scientific article; zbMATH DE number 7559178 (Why is no real title available?)
- On maximal repeats in compressed strings
- Fast label extraction in the CDAWG
- Linear-size CDAWG: new repetition-aware indexing and grammar compression
- On Sensitivity of Compact Directed Acyclic Word Graphs
- Optimally computing compressed indexing arrays based on the compact directed acyclic word graph
- Tight bounds for the sensitivity of CDAWGs with left-end edits
- LZ78 substring compression in compressed space
- LZ77 computation based on the run-length encoded BWT
- Space-efficient online computation of string net occurrences
- Novel results on the number of runs of the Burrows-Wheeler-transform
This page was built for publication: Composite repetition-aware data structures
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2942243)
