Grammar-based codes orgrammar-based compression arecompression algorithms based on the idea of constructing acontext-free grammar (CFG) for the string to be compressed. Examples include universallossless data compression algorithms.[1] To compress a data sequence, a grammar-based code transforms into a context-free grammar.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.Generally, the produced grammar is further compressed by statistical encoders likearithmetic coding.
The class of grammar-based codes is very broad. It includesblock codes, the multilevel pattern matching (MPM) algorithm,[3] variations of the incremental parsingLempel-Ziv code,[4] and many other new universal lossless compression algorithms.Grammar-based codes are universal in the sense that they can achieve asymptotically theentropy rate of any stationary,ergodic source with a finite alphabet.
The compression programs of the following are available from external links.
Sequitur[5] 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.
Re-Pair[6] is a greedy algorithm using the strategy of most-frequent-first substitution. The compressive performance is powerful, although the main memory space requirement is very large.
GLZA,[7] which constructs a grammar that may be reducible, i.e., contain repeats, where the entropy-coding cost of "spelling out" the repeats is less than the cost creating and entropy-coding a rule to capture them. (In general, the compression-optimal SLG is not irreducible, and the Smallest Grammar Problem is different from the actual SLG compression problem.)
^Kieffer, J. C.; Yang, E.-H. (2000), "Grammar-based codes: A new class of universal lossless source codes",IEEE Trans. Inf. Theory,46 (3):737–754,doi:10.1109/18.841160
^Charikar, M.; Lehman, E.; Liu, D.; Panigrahy, R.; Prabharakan, M.; Sahai, A.; Shelat, A. (2005), "The Smallest Grammar Problem",IEEE Trans. Inf. Theory,51 (7):2554–2576,doi:10.1109/tit.2005.850116,S2CID6900082
^Nevill-Manning, C. G.; Witten, I. H. (1997), "Identifying Hierarchical Structure in Sequences: A linear-time algorithm",Journal of Artificial Intelligence Research,7 (4):67–82,arXiv:cs/9709102,doi:10.1613/jair.374,hdl:10289/1186,S2CID2957960
^Conrad, Kennon J.; Wilson, Paul R. (2016). "Grammatical Ziv-Lempel Compression: Achieving PPM-Class Text Compression Ratios with LZ-Class Decompression Speed".2016 Data Compression Conference (DCC). p. 586.doi:10.1109/DCC.2016.119.ISBN978-1-5090-1853-6.S2CID3116024.
