Grammar-based coding: new perspectives

Grammar-based coding is investigated from three new perspectives. First, we revisit the performance analysis of grammar-based codes by proposing context-based run-length encoding algorithms as new performance benchmarks. A redundancy result stronger than all previous corresponding results is established. We then extend the analysis of grammar-based codes to sources with countably infinite alphabets. Let Λ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any Λ for which there exists a universal code. Moreover, upper bounds on the worst-case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Finally, we propose a new theoretic framework for compression in which grammars rather than sequential stochastic processes are used as source generating models, and point out some open problems in the framework.