A space-optimal grammar compression

DOI10.4230/LIPICS.ESA.2017.67MaRDI QIDQ5111756zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

succinct data structuregrammar compressionfully-online algorithm

Mathematics Subject Classification ID

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)

Recommendations

• String Processing and Information Retrieval
• An online algorithm for lightweight grammar-based compression
• Approximation of grammar-based compression via recompression
• Approximation of Grammar-Based Compression via Recompression
• A succinct grammar compression

Cites work

• scientific article; zbMATH DE number 1670815 (Why is no real title available?)
• scientific article; zbMATH DE number 1045405 (Why is no real title available?)
• scientific article; zbMATH DE number 2119662 (Why is no real title available?)
• A faster grammar-based self-index
• A faster implementation of online run-length Burrows-Wheeler transform
• A succinct grammar compression
• A unified algorithm for accelerating edit-distance computation via text-compression
• An online algorithm for lightweight grammar-based compression
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximating LZ77 via Small-Space Multiple-Pattern Matching
• Compression of individual sequences via variable-rate coding
• Database Theory - ICDT 2005
• Detecting regularities on grammar-compressed strings
• Dynamic Perfect Hashing: Upper and Lower Bounds
• ESP-index: a compressed index based on edit-sensitive parsing
• Efficient algorithms to compute compressed longest common substrings and compressed palindromes
• Fast \(q\)-gram mining on SLP compressed strings
• Fully dynamic data structure for LCE queries in compressed space
• Fully functional static and dynamic succinct trees
• LZ-End Parsing in Linear Time
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• On compressing and indexing repetitive sequences
• Optimal pattern matching in LZW compressed strings
• Optimal succinctness for range minimum queries
• Rank/select operations on large alphabets
• Self-indexed grammar-based compression
• String Processing and Information Retrieval
• Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
• Succinct representations of permutations and functions
• The string edit distance matching problem with moves
• siEDM: an efficient string index and search algorithm for edit distance with moves

Cited in

(9)

• Approximation of Grammar-Based Compression via Recompression
• An online algorithm for lightweight grammar-based compression
• 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
• A succinct grammar compression
• Rpair: rescaling RePair with Rsync

Describes a project that uses

Uses Software

• siEDM

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)