A separation between RLSLPs and LZ77

DOI10.1016/j.jda.2018.09.002zbMath1486.68058DBLPjournals/jda/BilleGGP18OpenAlexW2896151262WikidataQ60554302 ScholiaQ60554302MaRDI QIDQ1632509

Travis Gagie, Philip Bille, Inge Li Gørtz, Nicola Prezza

Publication date: 14 December 2018

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://orbit.dtu.dk/en/publications/c211d4ee-440d-46ca-b410-9bb248f5650f

zbMATH Keywords

Thue-Morse sequencegrammar-based compressionSLPLZ77RLSLPrun-length compression

Mathematics Subject Classification ID

Combinatorics on words (68R15) 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)

Related Items (1)

On the approximation ratio of LZ-end to LZ77

Uses Software

• r-index

Cites Work

• Unnamed Item
• Unnamed Item
• On compressing and indexing repetitive sequences
• Approximation of grammar-based compression via recompression
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• The smallest grammar problem revisited
• Unending chess, symbolic dynamics and a problem in semi-groups
• The Lempel–Ziv Complexity of Fixed Points of Morphisms
• The Smallest Grammar Problem
• Combinatorics on Words
• A universal algorithm for sequential data compression
• Fully Dynamic Data Structure for LCE Queries in Compressed Space
• Random Access to Grammar-Compressed Strings and Trees

This page was built for publication: A separation between RLSLPs and LZ77