Approximation ratios of \textsf{RePair}, \textsf{LongestMatch} and \textsf{Greedy} on unary strings

DOI10.1007/978-3-030-32686-9_1MaRDI QIDQ6536243zbMATH OpenFDO

Authors Danny Hucke

Publication date 19 April 2024

zbMATH Keywords

approximation algorithmdata compressionaddition chaingrammar-based compression

Mathematics Subject Classification ID

Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Recommendations

• scientific article; zbMATH DE number 2119662
• The smallest grammar problem revisited
• The Smallest Grammar Problem
• Approximation of grammar-based compression via recompression
• Approximation of Grammar-Based Compression via Recompression

Cites work

• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1149447 (Why is no real title available?)
• scientific article; zbMATH DE number 3435566 (Why is no real title available?)
• Approximation of grammar-based compression via recompression
• Compression of individual sequences via variable-rate coding
• Data compression via textual substitution
• Grammar-based codes: a new class of universal lossless source codes
• On the length of word chains
• RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy
• The Smallest Grammar Problem
• The smallest grammar problem revisited
• Universal lossless compression via multilevel pattern matching

This page was built for publication: Approximation ratios of \textsf{RePair}, \textsf{LongestMatch} and \textsf{Greedy} on unary strings

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