Grammar-based codes

Grammar-based codes or Grammar-based compression are compression algorithms based on the idea of constructing a context-free grammar (CFG) for the string to be compressed. Examples include universal lossless data compression algorithms [1] and SEQUITUR, among others. To compress a data sequence x = x_1 \cdots x_n, a grammar-based code transforms x into a context-free CFG G. The problem to find a smallest grammar for an input sequence is known to be NP-hard,[2] so many grammar-transform algorithms are proposed from theoretical and practical viewpoints. Generally, the produced grammar G is further compressed by statistical encoders like arithmetic coding.

Examples and characteristics

The class of grammar-based codes is very broad. It includes block codes, variations of the incremental parsing Lempel-Ziv code,[3] the multilevel pattern matching (MPM) algorithm,[4] and many other new universal lossless compression algorithms. 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.

Practical algorithms

The compression programs of following are available from external links.

  • Sequitur[5] is a classical grammar compression algorithm that sequentially translates an input text into a CFG, and then the produced CFG is encoded by an arithmetic coder.
  • Re-Pair[6] is a greedy algorithm by the strategy of most-frequent-first substitution. The compressive performance is powerful, although the main memory space is very large.


External links

  • Description of grammar-based codes with example
  • Sequitur codes
  • Re-Pair codes
  • Re-Pair codes a version of Gonzalo Navarro.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.