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.

A 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)