Grammar-based code ================== (with start symbol ß) for the second sentence of the United States Declaration of Independence. Each blue character denotes a nonterminal symbol; they were obtained from a gzip-compression of the sentence. 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. To compress a data sequence x = x_1 \cdots x_n , a grammar-based code transforms x into a context-free grammar G . The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP-hard, 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. (with start symbol ß) for the second sentence of the United States Declaration of Independence. Each blue character denotes a nonterminal symbol; they were obtained from a gzip-compression of the sentence.]] 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. To compress a data sequence x = x_1 \cdots x_n , a grammar-based code transforms x into a context-free grammar G . The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP-hard, 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. ==See also== Dictionary coder Grammar induction Straight-line grammar ==External links== GLZA discussion and paper Description of grammar-based codes with example Sequitur codes Re-Pair codes Re-Pair codes a version of Gonzalo Navarro. GrammarViz 2.0 - implementation of Sequitur, Re-Pair, and parallel Re-Pair in Java. REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Grammar-based code}, url = {https://encyclopegia.org/a/grammar-based-code} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Grammar-based code UR - https://encyclopegia.org/a/grammar-based-code ER - CITE THIS ARTICLE ---------------- Cite this article: Grammar-based code Derived from: https://en.wikipedia.org/w/index.php?oldid=1348503317 Licence: CC BY-SA 4.0 Snapshot: enwiki-001348503317 Permalink: /a/grammar-based-code