Grammar compressed sequences with rank/select support

DOI10.1016/J.JDA.2016.10.001zbMATH Open1407.68156arXiv1911.09077OpenAlexW3105449307MaRDI QIDQ2397151FDOQ2397151

Gonzalo Navarro, Alberto Ordóñez, Nieves R. Brisaboa

Publication date: 29 May 2017

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

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.

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

Recommendations

• Access, rank, and select in grammar-compressed strings
• Self-indexed grammar-based compression
• Efficient fully-compressed sequence representations
• Grammar-compressed indexes with logarithmic search time
• Faster compressed suffix trees for repetitive collections

zbMATH Keywords

text indexinggrammar compressionrepetitive sequences

Mathematics Subject Classification ID

Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42)

Cites Work

• A fully linear-time approximation algorithm for grammar-based compression
• Compressed representations of sequences and full-text indexes
• Compressing and indexing labeled trees, with applications
• Indexing compressed text
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Title not available (Why is that?)
• Succinct Trees in Practice
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• Succinct indexes for strings, binary relations and multilabeled trees
• Efficient fully-compressed sequence representations
• On the Complexity of Finite Sequences
• A universal algorithm for sequential data compression
• Spaces, Trees, and Colors
• A Method for the Construction of Minimum-Redundancy Codes
• Wavelet trees for all
• Indexing Highly Repetitive Collections
• Rank/select operations on large alphabets
• On compressing and indexing repetitive sequences
• Title not available (Why is that?)
• Dynamic entropy-compressed sequences and full-text indexes
• Compact binary relation representations with rich functionality
• The Smallest Grammar Problem
• Position-Restricted Substring Searching
• Optimal Trade-Offs for Succinct String Indexes
• On compressing permutations and adaptive sorting
• New text indexing functionalities of the compressed suffix arrays
• Title not available (Why is that?)
• Grammar-based codes: a new class of universal lossless source codes
• A Succinct Grammar Compression
• Optimal Lower and Upper Bounds for Representing Sequences
• Random Access to Grammar-Compressed Strings and Trees
• LZ77-Based Self-indexing with Faster Pattern Matching
• Access, Rank, and Select in Grammar-compressed Strings
• Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
• General document retrieval in compact space

Cited In (5)

• Finger search in grammar-compressed strings
• Block trees
• Faster Compressed Suffix Trees for Repetitive Collections
• Optimal rank and select queries on dictionary-compressed text
• Practical Random Access to SLP-Compressed Texts

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)