RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy
Carlos Ochoa, Gonzalo Navarro · IEEE Transactions on Information Theory · 2018
Irreducible grammars are a class of context-free grammars with well-known representatives, such as Repair (with a few tweaks), Longest Match, Greedy, and Sequential. We show that a grammar-based compression method described by Kieffer and Yang (2000) is upper bounded by the high-order empirical entropy of the string when the underlying grammar is irreducible. Specifically, given a string S over an alphabet of size σ, we prove that if the underlying grammar is irreducible, then the length of the binary code output by this grammar-based compression method is bounded by |S|Hk(S) + o(|S|log σ) for any k ∈ 0(logσ|S|), where Hk(S) is the k-order empirical entropy of S. This is the first bound encompassing the whole class of irreducible grammars in terms of the high-order empirical entropy, with coefficient 1.