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

DOI10.1007/978-3-030-32686-9_1zbMATH Open1539.68108MaRDI QIDQ6536243

Danny Hucke

Publication date: 19 April 2024

zbMATH Keywords

data compressionapproximation algorithmaddition chaingrammar-based compression

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation of grammar-based compression via recompression
• On the length of word chains
• The smallest grammar problem revisited
• The Smallest Grammar Problem
• Data compression via textual substitution
• Compression of individual sequences via variable-rate coding
• Universal lossless compression via multilevel pattern matching
• Grammar-based codes: a new class of universal lossless source codes
• RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy

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