Grammar-based code

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

(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.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1348503317 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.