## Abstract

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.

Original language | English |
---|---|

Article number | 9259056 |

Pages (from-to) | 317-328 |

Number of pages | 12 |

Journal | IEEE Transactions on Information Theory |

Volume | 67 |

Issue number | 1 |

DOIs | |

Publication status | Published - Jan 2021 |

## All Science Journal Classification (ASJC) codes

- Information Systems
- Computer Science Applications
- Library and Information Sciences