Grammar-based codes

From Wikipedia, the free encyclopedia

This article or section needs to be wikified to meet Wikipedia's quality standards. Please help improve this article with relevant internal links. (August 2007)

Grammar-based codes are compression algorithms based on the idea of constructing a context-free grammar for the string to be compressed. Examples include universal lossless data compression algorithms proposed in Kieffer and Yang 2000, and SEQUITUR(http://sequitur.info/), among others. To compress a data sequence, a grammar-based code first transforms x into a context-free grammar G, and then uses an arithmetic coding algorithm to compress the grammar G. For a detailed description of grammar-based codes and context-free grammars, the read is referred to Kieffer and Yang 2000.

[edit] Examples

The class of grammar-based codes is very broad. It includes block codes, variations of the incremental parsing Lempel-Ziv code Ziv and Lempel 1978 (LZ78), the multilevel pattern matching (MPM) algorithm Kieffer et al. 2000, and many other new universal lossless compression algorithms.

[edit] Coding Theorems

Grammar-based codes are universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source with a finite alphabet.

[edit] References

Kieffer-Yang 2000. J. C. Kieffer and E.-H. Yang, "Grammar-based codes: A new class of universal lossless source codes," IEEE Trans. Inform. Theory, vol. 46, pp. 737--754, 2000.

Ziv and Lempel 1978. J. Ziv and A. Lempel, "Compression of individual sequences via variable rate coding," IEEE Trans. Inform. Theory, vol. 24, pp. 530--536, 2000.

Kieffer et al. 2000. J. C. Kieffer, E.-H. Yang, G. Nelson, and P. Cosman, "Universal lossless compression via multilevel pattern matching," IEEE Trans. Inform. Theory, vol. 46, pp. 1227--1245, 2000.

Great description of grammar-based codes with easy to follow example