A separation between RLSLPs and LZ77

DOI10.1016/J.JDA.2018.09.002MaRDI QIDQ1632509zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Philip Bille, Travis Gagie, 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

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

Recommendations

• On the approximation ratio of LZ-end to LZ77
• Relations between greedy and bit-optimal LZ77 encodings
• From LZ77 to the run-length encoded Burrows-Wheeler transform, and back
• LZ77 computation based on the run-length encoded BWT
• scientific article; zbMATH DE number 975330
• Converting SLP to LZ78 in almost Linear Time
• A comparison of index-based Lempel-Ziv LZ77 factorization algorithms
• LZ77 factorisation of trees
• Conversion from RLBWT to LZ77
• Error Resilient LZ'77 Data Compression: Algorithms, Analysis, and Experiments

Cites work

• scientific article; zbMATH DE number 1740032 (Why is no real title available?)
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• A universal algorithm for sequential data compression
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximation of grammar-based compression via recompression
• Combinatorics on Words
• Fully dynamic data structure for LCE queries in compressed space
• On compressing and indexing repetitive sequences
• Random access to grammar-compressed strings and trees
• The Lempel–Ziv Complexity of Fixed Points of Morphisms
• The Smallest Grammar Problem
• The smallest grammar problem revisited
• Unending chess, symbolic dynamics and a problem in semi-groups

Cited in

(3)

• Converting SLP to LZ78 in almost Linear Time
• On the approximation ratio of LZ-end to LZ77
• Balancing run-length straight-line programs

Describes a project that uses

Uses Software

• r-index

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1632509)