The Smallest Grammar Problem Revisited

In a seminal paper, Charikar et al. derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Here the gaps for LZ78 and BISECTION are closed by showing that the approximation ratio of LZ78 is...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2021-01, Vol.67 (1), p.317-328
Main Authors: Bannai, Hideo, Hirayama, Momoko, Hucke, Danny, Inenaga, Shunsuke, Jez, Artur, Lohrey, Markus, Reh, Carl Philipp
Format: Article
Language:English
Subjects:
Alphabets
Approximation
approximation algorithm
Compressors
Encoding
Entropy
Grammar
Lower bounds
LZ78
Maintenance engineering
Mathematical analysis
RePair
Size measurement
smallest grammar problem
String compression
Upper bound
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In a seminal paper, Charikar et al. derive upper and lower bounds on the approximation ratios for several grammar-based compressors, but in all cases there is a gap between the lower and upper bound. Here the gaps for LZ78 and BISECTION are closed by showing that the approximation ratio of LZ78 is \Theta ((\text {n}/\log \text {n})^{2/3}) , whereas the approximation ratio of BISECTION is \Theta (\sqrt {\text {n}/\log \text {n}}) . In addition, the lower bound for RePair is improved from \Omega (\sqrt {\log \text {n}}) to \Omega (\log \text {n}/\log \log \text {n}) . Finally, results of Arpe and Reischuk relating grammar-based compression for arbitrary alphabets and binary alphabets are improved.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2020.3038147