A Space-Optimal Grammar Compression.

DOI10.4230/LIPIcs.ESA.2017.67zbMath1442.68051OpenAlexW2758220686MaRDI QIDQ5111756

Hiroshi Sakamoto, Yoshimasa Takabatake, Itagaki Tomohiro

Publication date: 27 May 2020

Full work available at URL: http://doi.org/10.4230/LIPIcs.ESA.2017.67

zbMATH Keywords

succinct data structuregrammar compressionfully-online algorithm

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) Data structures (68P05) Online algorithms; streaming algorithms (68W27)

Related Items

Grammar-compressed indexes with logarithmic search time, Compaction of Church numerals, Compressed range minimum queries

Uses Software

• siEDM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On compressing and indexing repetitive sequences
• Succinct representations of permutations and functions
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• A faster implementation of online run-length Burrows-Wheeler transform
• An online algorithm for lightweight grammar-based compression
• siEDM: an efficient string index and search algorithm for edit distance with moves
• Fast \(q\)-gram mining on SLP compressed strings
• ESP-index: a compressed index based on edit-sensitive parsing
• Detecting regularities on grammar-compressed strings
• Fully Functional Static and Dynamic Succinct Trees
• Faster Fully Compressed Pattern Matching by Recompression
• A Faster Grammar-Based Self-index
• Optimal Pattern Matching in LZW Compressed Strings
• LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding
• The string edit distance matching problem with moves
• Self-Indexed Grammar-Based Compression
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Optimal Succinctness for Range Minimum Queries
• Rank/select operations on large alphabets
• Compression of individual sequences via variable-rate coding
• Dynamic Perfect Hashing: Upper and Lower Bounds
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
• A Succinct Grammar Compression
• LZ-End Parsing in Linear Time
• Database Theory - ICDT 2005
• String Processing and Information Retrieval