Grammar-based code

compact representationsGrammar-based codes
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
15 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

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.

Lossless compression

losslesslossless data compressioncompression
Examples include universal lossless data compression algorithms.

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.

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

ergodicergodic measurenon-ergodic
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.

Heavy path decomposition

Heavy-Light 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.