Grammar-based code

Grammar-based code

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 sequencex = x_1 cdots x_n, 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 reader is referred to Kieffer and Yang 2000.

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.

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.

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.
* [http://www.mit.edu/~6.454/www_fall_2002/emin/summary.pdf Great description of grammar-based codes with easy to follow example]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Code-switching — This article is about the use of more than one language in speech. For the use of multiple languages in writing, see Macaronic language. Sociolinguistics Areas of study …   Wikipedia

  • Grammar induction — Grammatical induction, also known as grammatical inference or syntactic pattern recognition, refers to the process in machine learning of inducing a formal grammar (usually in the form of re write rules or productions ) from a set of observations …   Wikipedia

  • Code talker — Codetalkers redirects here. For the band, see The Codetalkers. Choctaws in training in World War I for coded radio and telephone transmissions. Code talkers was a term used to describe people who talk using a coded language. It is frequently used …   Wikipedia

  • Parsing expression grammar — A parsing expression grammar, or PEG, is a type of analytic formal grammar that describes a formal language in terms of a set of rules for recognizing strings in the language. A parsing expression grammar essentially represents a recursive… …   Wikipedia

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia

  • The Portsmouth Grammar School — Infobox UK school name = The Portsmouth Grammar School size = 100px dms = motto = Praemia Virtutis Honores motto pl = established = 1732 approx = closed = c approx = type = Public school religion = Church of England president = head label = Head… …   Wikipedia

  • Affix grammar — An affix grammar is a kind of formal grammar; it is used to describe the syntax of languages, mainly computer languages, using an approach based on how natural language is typically described.The grammatical rules of an affix grammar are those of …   Wikipedia

  • Tunbridge Wells Grammar School for Boys — Tunbridge Wells Grammar School for Boys, also known as Tunbridge Wells Boys Grammar School or TWGSB , is a grammar school in Royal Tunbridge Wells, a town in Kent, England, UK. The school s Latin motto, Faber est quisque suæ fortunæ means Every… …   Wikipedia

  • International Code of Zoological Nomenclature — The International Code of Zoological Nomenclature is a set of rules in zoology that have one fundamental aim: to provide the maximum universality and continuity in the naming of all animals according to taxonomic judgment. The Code is meant to… …   Wikipedia

  • Colchester Royal Grammar School — For other schools with the name RGS, see Royal Grammar School. Colchester Royal Grammar School Motto Vitae Corona Fides (Faith is the Crown of Life) Established By 1206 Refounded 1539 Refounded 1584 Type …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”