Composite Repetition-Aware Data Structures

DOI10.1007/978-3-319-19929-0_3zbMath1432.68082arXiv1502.05937OpenAlexW1878541814MaRDI QIDQ2942243

Djamal Belazzougui, Nicola Prezza, Fabio Cunial, Travis Gagie, Mathieu Raffinot

Publication date: 20 August 2015

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1502.05937

Mathematics Subject Classification ID

Data structures (68P05) Algorithms on strings (68W32)

Related Items (19)

Novel results on the number of runs of the Burrows-Wheeler-transform ⋮ Document listing on repetitive collections with guaranteed performance ⋮ Logarithmic equal-letter runs for BWT of purely morphic words ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Faster repetition-aware compressed suffix trees based on block trees ⋮ On Sensitivity of Compact Directed Acyclic Word Graphs ⋮ 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 ⋮ Fast Label Extraction in the CDAWG ⋮ Linear-Size CDAWG: New Repetition-Aware Indexing and Grammar Compression ⋮ Flexible indexing of repetitive collections ⋮ Unnamed Item ⋮ Unnamed Item ⋮ LZ77 computation based on the run-length encoded BWT ⋮ Dynamic index and LZ factorization in compressed space ⋮ Refining the \(r\)-index ⋮ Top tree compression of tries

Cites Work

• Unnamed Item
• On compressing and indexing repetitive sequences
• On the structure of compacted subword graphs of Thue-Morse words and their applications
• The structure of subword graphs and suffix trees of Fibonacci words
• On maximal repeats in strings
• Log-logarithmic worst-case range queries are possible in space theta(N)
• Stronger Lempel-Ziv based compressed text indexing
• Versatile Succinct Representations of the Bidirectional Burrows-Wheeler Transform
• Indexing compressed text
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Complete inverted files for efficient text retrieval and analysis
• Orthogonal range searching on the RAM, revisited
• LZ77-Based Self-indexing with Faster Pattern Matching
• Run-Length Compressed Indexes Are Superior for Highly Repetitive Sequence Collections
• Combinatorial Pattern Matching

This page was built for publication: Composite Repetition-Aware Data Structures