The universality of grammar-based codes for sources with countably infinite alphabets

摘要

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/) for some 0