Grammar-based code

Examples include universal lossless data compression algorithms.

The problem of finding a smallest grammar for an input sequence (smallest grammar problem) is known to be NP-hard,[2] so many grammar-transform algorithms are proposed from theoretical and practical viewpoints.

is further compressed by statistical encoders like arithmetic coding.

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

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.

Straight-line grammar (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.