A space-optimal grammar compression
DOI10.4230/LIPICS.ESA.2017.67zbMATH Open1442.68051OpenAlexW2758220686MaRDI QIDQ5111756FDOQ5111756
Authors: Yoshimasa Takabatake, Itagaki Tomohiro, Hiroshi Sakamoto 
Publication date: 27 May 2020
Full work available at URL: http://doi.org/10.4230/LIPIcs.ESA.2017.67
Recommendations
Online algorithms; streaming algorithms (68W27) 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
- siEDM: an efficient string index and search algorithm for edit distance with moves
- Title not available (Why is that?)
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Fully functional static and dynamic succinct trees
- Faster Fully Compressed Pattern Matching by Recompression
- Optimal succinctness for range minimum queries
- Compression of individual sequences via variable-rate coding
- Dynamic Perfect Hashing: Upper and Lower Bounds
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Title not available (Why is that?)
- Rank/select operations on large alphabets
- On compressing and indexing repetitive sequences
- The string edit distance matching problem with moves
- Self-Indexed Grammar-Based Compression
- Succinct representations of permutations and functions
- Efficient algorithms to compute compressed longest common substrings and compressed palindromes
- Fast \(q\)-gram mining on SLP compressed strings
- Database Theory - ICDT 2005
- Title not available (Why is that?)
- A Succinct Grammar Compression
- Detecting regularities on grammar-compressed strings
- A Faster Grammar-Based Self-index
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- Fully Dynamic Data Structure for LCE Queries in Compressed Space
- Title not available (Why is that?)
- LZ-End Parsing in Linear Time
- A faster implementation of online run-length Burrows-Wheeler transform
- An online algorithm for lightweight grammar-based compression
- ESP-index: a compressed index based on edit-sensitive parsing
- Optimal Pattern Matching in LZW Compressed Strings
- LZD Factorization: Simple and Practical Online Grammar Compression with Variable-to-Fixed Encoding
- String Processing and Information Retrieval
Cited In (8)
- Compaction of Church numerals
- Grammar-compressed indexes with logarithmic search time
- Compressibility of Finite Languages by Grammars
- Space-efficient recognition of sparse self-reducible languages
- Grammar-Based Compression in a Streaming Model
- Rpair: rescaling RePair with Rsync
- Compressed range minimum queries
- Approximation of Grammar-Based Compression via Recompression
Uses Software
This page was built for publication: A space-optimal grammar compression
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111756)
