Grammar compressed sequences with rank/select support
From MaRDI portal
Publication:2397151
Abstract: Sequence representations supporting not only direct access to their symbols, but also rank/select operations, are a fundamental building block in many compressed data structures. Several recent applications need to represent highly repetitive sequences, and classical statistical compression proves ineffective. We introduce, instead, grammar-based representations for repetitive sequences, which use up to 6% of the space needed by statistically compressed representations, and support direct access and rank/select operations within tens of microseconds. We demonstrate the impact of our structures in text indexing applications.
Recommendations
Cites work
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- scientific article; zbMATH DE number 756768 (Why is no real title available?)
- scientific article; zbMATH DE number 2230164 (Why is no real title available?)
- A Method for the Construction of Minimum-Redundancy Codes
- A fully linear-time approximation algorithm for grammar-based compression
- A succinct grammar compression
- A universal algorithm for sequential data compression
- Access, rank, and select in grammar-compressed strings
- Compact binary relation representations with rich functionality
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Compressed representations of sequences and full-text indexes
- Compressing and indexing labeled trees, with applications
- Data structure lower bounds on random access to grammar-compressed strings
- Dynamic entropy-compressed sequences and full-text indexes
- Efficient fully-compressed sequence representations
- General document retrieval in compact space
- Grammar-based codes: a new class of universal lossless source codes
- Indexing compressed text
- Indexing highly repetitive collections
- LZ77-based self-indexing with faster pattern matching
- New text indexing functionalities of the compressed suffix arrays
- On compressing and indexing repetitive sequences
- On compressing permutations and adaptive sorting
- On the Complexity of Finite Sequences
- Optimal lower and upper bounds for representing sequences
- Optimal trade-offs for succinct string indexes
- Position-Restricted Substring Searching
- Random access to grammar-compressed strings and trees
- Rank/select operations on large alphabets
- Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
- Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
- Succinct Trees in Practice
- Succinct indexes for strings, binary relations and multilabeled trees
- The Smallest Grammar Problem
- Wavelet trees for all
Cited in
(7)- Finger search in grammar-compressed strings
- Block trees
- Access, rank, and select in grammar-compressed strings
- Optimal rank and select queries on dictionary-compressed text
- Practical Random Access to SLP-Compressed Texts
- Faster compressed suffix trees for repetitive collections
- Rpair: rescaling RePair with Rsync
This page was built for publication: Grammar compressed sequences with rank/select support
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397151)
