---
title: Grammar-based code
slug: grammar-based-code
qid: 
snapshot: enwiki-001348503317
content_hash: 
license: CC BY-SA 4.0
source: https://en.wikipedia.org/w/index.php?oldid=1348503317
tags: [20157965, 20476821, 23603337, 24623845, 26220375, 29176270]
---

# Grammar-based code

> [!note] Provenance
> Snapshot `enwiki-001348503317` · content root `…`
> Derived from <https://en.wikipedia.org/w/index.php?oldid=1348503317> · Licensed CC BY-SA 4.0

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