RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy
Artículo

Open/ Download
Publication date
2019Metadata
Show full item record
Cómo citar
Ochoa, Carlos
Cómo citar
RePair and All Irreducible Grammars are Upper Bounded by High-Order Empirical Entropy
Author
Abstract
© 1963-2012 IEEE. 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 sigma , 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|H-{k}(S) + o(|S|log sigma) for any kin o(log -sigma |S|) , where H-{k}(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.
Indexation
Artículo de publicación SCOPUS
Identifier
URI: https://repositorio.uchile.cl/handle/2250/171326
DOI: 10.1109/TIT.2018.2871452
ISSN: 00189448
Quote Item
IEEE Transactions on Information Theory, Volumen 65, Issue 5, 2019, Pages 3160-3164
Collections