Application of Lempel–Ziv factorization to the approximation of grammar-based compression

2003/06/01 by Wojciech Rytter · 1 voice · 18 citations
Computer Science · #Algorithms and Data Compression #Natural Language Processing Techniques #semigroups and automata theory

paper · pdf · doi:10.1016/s0304-3975(02)00777-6

crossref issued 2003/06/01 · crossref published 2003/06/01 · crossref published-print 2003/06/01 · openalex publication_date 2003/06/01 · crossref created 2003/06/02 · crossref deposited 2024/12/12 · openalex created_date 2025/10/10 · crossref indexed 2026/04/04 · openalex updated_date 2026/07/31

Cited by

• Online Pattern Matching for String Edit Distance with Moves
• Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
• Tight Lower Bounds for Central String Queries in Compressed Space
• Grammar-compressed Self-index with Lyndon Words
• Faster fully compressed pattern matching by recompression
• Longest Common Extensions with Recompression
• LZRR: LZ77 Parsing with Right Reference
• Approximation ratio of RePair
• Rank, select and access in grammar-compressed strings
• On the Smallest Size of Internal Collage Systems
• Searching and Indexing Genomic Databases via Kernelization
• Binary Jumbled Pattern Matching on Trees and Tree-Like Structures
• Compact q-gram Profiling of Compressed Strings
• Online Self-Indexed Grammar Compression
• Optimal Time Random Access to Grammar-Compressed Strings in Small Space
• Optimal Dynamic Strings
• Faster Approximate Pattern Matching in Compressed Repetitive Texts
• Tailoring r-index for metagenomics

Discussions

• What are the tightest known bounds on the number of rules in the smallest grammar(s) (upper & lower), If rules can have arbitrary length, and size is just the number of rules, you can always make a gr [stackexchange, 4 points]