The Universality of Grammar-Based Codes for Sources With Countably Infinite Alphabets
D.-K. He, En‐hui Yang · IEEE Transactions on Information Theory · 2005
In this paper, we investigate the performance of grammar-based codes for sources with countably infinite alphabets. Let /spl Lambda/ 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 /spl Lambda/ if and only if there exists a universal code for /spl Lambda/. 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. Depending upon the conditions satisfied by length-n individual sequences, these bounds range from O(loglogn/logn) to O(1/log/sup 1-/spl alpha//n) for some 0</spl alpha/<1. These results complement the previous universality and redundancy results in the literature on the performance of grammar-based codes for sources with finite alphabets.