Re-Pair Achieves High-Order Entropy

Gonzalo Navarro, Luís Russo

Abstract:

Re-Pair is a dictionary-based compression method invented in 1999 by Larsson and Moffat. Although its practical performance has been established through experiments, the method has resisted all attempts of formal analysis. In this paper we show that Re-Pair compresses a sequence $T[1,n]$ over an alphabet of size $\sigma$ and $k$-th order entropy $H_k$, to at most $2nH_k+o(n\log\sigma)$ bits, for any $k=o(\log_\sigma n)$.