Approximation ratios of \textsf{RePair}, \textsf{LongestMatch} and \textsf{Greedy} on unary strings
From MaRDI portal
Publication:6536243
DOI10.1007/978-3-030-32686-9_1zbMATH Open1539.68108MaRDI QIDQ6536243
Publication date: 19 April 2024
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