The smallest grammar problem revisited

Abstract

In a seminal paper of Charikar et al. on the smallest grammar problem, the authors 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 $\mathsf{BISECTION}$ are closed by showing that the approximation ratio of $LZ78$ is $\Theta ((n/\log n{)}^{2/3})$, whereas the approximation ratio of $\mathsf{BISECTION}$ is $\Theta (\sqrt{n/\log n})$. In addition, the lower bound for $\mathsf{RePair}$ is improved from $\Omega (\sqrt{\log n})$ to $\Omega (\log n/\log \log n)$. Finally, results of Arpe and Reischuk relating grammar-based compression for arbitrary alphabets and binary alphabets are improved.

arXiv commentA short version of this paper appeared in the Proceedings of SPIRE 2016. This work has been supported by the DFG research project LO 748/10-1 (QUANT-KOMP)