# Grammar-based code

**compact representations**

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

13 Related Articles

### Data compression

**compressionvideo compressioncompressed**

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.

Grammar-based codes like this can compress highly repetitive input extremely effectively, for instance, a biological data collection of the same or closely related species, a huge versioned document collection, internet archival, etc. The basic task of grammar-based codes is constructing a context-free grammar deriving a single string.

### Smallest grammar problem

Smallest grammar problem

Grammar-based code

### Straight-line grammar

**Algorithms for context-free grammar generation**

Straight-line grammar

Grammar-based code

### Context-free grammar

**context-free grammarscontext-freecontext free grammar**

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.

### Lossless compression

**losslesslossless data compressioncompression**

Examples include universal lossless data compression algorithms.

### Arithmetic coding

**arithmetic coderarithmetic encodingarithmetic code**

Generally, the produced grammar G is further compressed by statistical encoders like arithmetic coding.

### Block code

**linear block codedistanceblock encoding**

It includes block codes, variations of the incremental parsing Lempel-Ziv code, the multilevel pattern matching (MPM) algorithm, and many other new universal lossless compression algorithms.

### LZ77 and LZ78

**LZ77Lempel-ZivLempel-Ziv compression**

It includes block codes, variations of the incremental parsing Lempel-Ziv code, the multilevel pattern matching (MPM) algorithm, and many other new universal lossless compression algorithms.

### Entropy rate

**ratesource information rate**

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.

### Ergodicity

**ergodicnon-ergodicergodic measure**

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.

### Sequitur algorithm

**Sequitur**

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

### Induction of regular languages

**Regular language learning**

Obtaining compact representations of finite languages

### Heavy path decomposition

Subsequent applications of heavy path decomposition have included solving the level ancestor problem, computing the edit distance between trees, graph drawing and greedy embedding, finding a path near all nodes of a given graph, fault diagnosis in fiber-optic communication networks, and decoding grammar-based codes, among others.