Grammar-based code

Grammar-based codes are universal lossless data compression algorithms proposed in Kieffer-Yang 2000. To compress a data sequence$x=x_{1}\cdots x_{n}$, a grammar-based code first transforms $x$ into a context-free grammar $G$, and then uses an arithmetic coding algorithm to compress the grammar $G$. For a detailed description of grammar-based codes and context-free grammars, the read is referred to Kieffer-Yang 2000.

---

Kieffer-Yang 2000 J. C. Kieffer and E. Yang, "Grammar-based codes: A new class of universal lossless source codes," IEEE Trans. Inform. Theory, vol. 46, pp. 737--754, 2000.