Grammar compressed sequences with rank/select support
From MaRDI portal
Publication:2397151
DOI10.1016/J.JDA.2016.10.001zbMath1407.68156arXiv1911.09077OpenAlexW3105449307MaRDI QIDQ2397151
Gonzalo Navarro, Alberto Ordóñez, Nieves R. Brisaboa
Publication date: 29 May 2017
Published in: Journal of Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1911.09077
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Data structures (68P05)
Related Items (4)
Block trees ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ Finger search in grammar-compressed strings ⋮ Faster Compressed Suffix Trees for Repetitive Collections
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Compact binary relation representations with rich functionality
- On compressing and indexing repetitive sequences
- On compressing permutations and adaptive sorting
- Efficient fully-compressed sequence representations
- Wavelet trees for all
- A fully linear-time approximation algorithm for grammar-based compression
- General Document Retrieval in Compact Space
- Indexing Highly Repetitive Collections
- Compressed representations of sequences and full-text indexes
- Succinct indexes for strings, binary relations and multilabeled trees
- Access, Rank, and Select in Grammar-compressed Strings
- Compressing and indexing labeled trees, with applications
- Position-Restricted Substring Searching
- Indexing compressed text
- The Smallest Grammar Problem
- Rank/select operations on large alphabets
- Optimal Trade-Offs for Succinct String Indexes
- On the Complexity of Finite Sequences
- A universal algorithm for sequential data compression
- New text indexing functionalities of the compressed suffix arrays
- Grammar-based codes: a new class of universal lossless source codes
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- A Succinct Grammar Compression
- Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
- Optimal Lower and Upper Bounds for Representing Sequences
- Dynamic entropy-compressed sequences and full-text indexes
- Spaces, Trees, and Colors
- Succinct Trees in Practice
- Random Access to Grammar-Compressed Strings and Trees
- LZ77-Based Self-indexing with Faster Pattern Matching
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- A Method for the Construction of Minimum-Redundancy Codes
This page was built for publication: Grammar compressed sequences with rank/select support
