{
  "id": "enwiki-001348503317",
  "slug": "grammar-based-code",
  "title": "Grammar-based code",
  "qid": "",
  "lead": "(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.",
  "body": "(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.",
  "categories": [
    "20157965",
    "20476821",
    "23603337",
    "24623845",
    "26220375",
    "29176270"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1348503317",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1776037276.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001348503317",
    "type": "webpage",
    "title": "Grammar-based code",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/grammar-based-code",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001348503317",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1348503317",
    "note": "Immutable snapshot enwiki-001348503317"
  }
}