The Smallest Grammar Problem Revisited
Hideo Bannai, Momoko Hirayama, Danny Hucke, Shunsuke Inenaga, Artur Jeż, Markus Lohrey, Carl Philipp Reh · IEEE Transactions on Information Theory · 2020
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 Θ((n/log n)2/3), whereas the approximation ratio of BISECTION is Θ(√(n/log n)). In addition, the lower bound for RePair is improved from Ω(√(log n)) to Ω(log n/log log n). Finally, results of Arpe and Reischuk relating grammar-based compression for arbitrary alphabets and binary alphabets are improved.