Re-pair Achieves High-Order Entropy
Gonzalo Navarro, Luís M. S.Russo · DCC · 2008
Re-pair is a dictionary-based compression method invented in 1999 by J. Larsson and A. Moffat [Off-line dictionary-based compression. Proc. IEEE, 88(11):1722-1732, 2000], lacking up to now an efficiency analysis. We show that re-pair compresses a sequence T[1,n] over an alphabet of size sigma to at most 2nHk+ o(n log sigma) bits, for any k = o(logsigman), where Hkis either the classical information-theory or the empirical k-th order entropy (in the latter, the model is inferred from the sequence statistics).