Grammar-compressed indexes with logarithmic search time
From MaRDI portal
Publication:2656171
DOI10.1016/j.jcss.2020.12.001zbMath1477.68104arXiv2004.01032OpenAlexW3114553168MaRDI QIDQ2656171
Gonzalo Navarro, Alejandro Pacheco, Francisco Claude
Publication date: 10 March 2021
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2004.01032
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)
Related Items (3)
An LMS-based grammar self-index with local consistency properties ⋮ Near-optimal search time in \(\delta \)-optimal space, and vice versa ⋮ Near-optimal search time in \(\delta \)-optimal space
Uses Software
Cites Work
- Unnamed Item
- Compact binary relation representations with rich functionality
- On compressing and indexing repetitive sequences
- Succinct representations of permutations and functions
- Approximation of grammar-based compression via recompression
- Representing trees of higher degree
- A \textit{really} simple approximation of smallest grammar
- Grammatical inference by hill climbing
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Time-space trade-offs for Lempel-Ziv compressed indexing
- Universal compressed text indexing
- The smallest grammar problem revisited
- Collage system: A unifying framework for compressed pattern matching.
- Towards a definitive measure of repetitiveness
- Block trees
- Compressed indexing with signature grammars
- Stronger Lempel-Ziv based compressed text indexing
- Wavelet trees for all
- Fast relative Lempel-Ziv self-index for similar sequences
- Fully Functional Static and Dynamic Succinct Trees
- Suffix Tree of Alignment: An Efficient Index for Similar Data
- Indexing Highly Repetitive Collections
- A Faster Grammar-Based Self-index
- Composite Repetition-Aware Data Structures
- Compressed representations of sequences and full-text indexes
- Self-Indexed Grammar-Based Compression
- Access, Rank, and Select in Grammar-compressed Strings
- Indexing compressed text
- The Smallest Grammar Problem
- Rank/select operations on large alphabets
- Data compression via textual substitution
- On the Complexity of Finite Sequences
- Compression of individual sequences via variable-rate coding
- Efficient Storage and Retrieval by Content and Address of Static Files
- Grammar-based codes: a new class of universal lossless source codes
- Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
- Optimal Lower and Upper Bounds for Representing Sequences
- Optimal-Time Dictionary-Compressed Indexes
- Longest Common Extensions with Recompression.
- A Space-Optimal Grammar Compression.
- Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
- Practical Entropy-Compressed Rank/Select Dictionary
- Random Access to Grammar-Compressed Strings and Trees
- Orthogonal range searching on the RAM, revisited
- LZ77-Based Self-indexing with Faster Pattern Matching
This page was built for publication: Grammar-compressed indexes with logarithmic search time
