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

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

Authors: Danny Hucke 

Publication date: 19 April 2024

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

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)

Cites Work

• Title not available (Why is that?)
• Universal lossless compression via multilevel pattern matching
• Compression of individual sequences via variable-rate coding
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Smallest Grammar Problem
• Approximation of grammar-based compression via recompression
• On the length of word chains
• Data compression via textual substitution
• Grammar-based codes: a new class of universal lossless source codes
• The smallest grammar problem revisited
• 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

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