Access, Rank, and Select in Grammar-compressed Strings

DOI10.1007/978-3-662-48350-3_13zbMath1465.68119arXiv1408.3093OpenAlexW2187903286MaRDI QIDQ3452777

Yasuo Tabei, Djamal Belazzougui, Simon J. Puglisi, Patrick Hagge Cording

Publication date: 19 November 2015

Published in: Algorithms - ESA 2015 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Algorithms on strings (68W32)

Related Items (10)

Grammar compressed sequences with rank/select support ⋮ Grammar-compressed indexes with logarithmic search time ⋮ Random access in persistent strings and segment selection ⋮ Unnamed Item ⋮ Block trees ⋮ Universal compressed text indexing ⋮ On Two LZ78-style Grammars: Compression Bounds and Compressed-Space Computation ⋮ Optimal rank and select queries on dictionary-compressed text ⋮ Finger search in grammar-compressed strings ⋮ Balancing straight-line programs for strings and trees

Cites Work

• Unnamed Item
• Unnamed Item
• An efficient algorithm to test square-freeness of strings compressed by straight-line programs
• Faster Lyndon factorization algorithms for SLP and LZ78 compressed text
• Compressed subsequence matching and packed tree coloring
• A simple storage scheme for strings achieving entropy bounds
• Surpassing the information theoretic bound with fusion trees
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Fingerprints in compressed strings
• Indexes for Document Retrieval with Relevance
• Detecting Regularities on Grammar-Compressed Strings
• Indexing Highly Repetitive Collections
• FINDING CHARACTERISTIC SUBSTRINGS FROM COMPRESSED TEXTS
• Compressed representations of sequences and full-text indexes
• An analysis of the Burrows—Wheeler transform
• The Smallest Grammar Problem
• Rank/select operations on large alphabets
• Efficient randomized pattern-matching algorithms
• Reachability and Distance Queries via 2-Hop Labels
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings
• Spaces, Trees, and Colors
• Random Access to Grammar-Compressed Strings and Trees

This page was built for publication: Access, Rank, and Select in Grammar-compressed Strings