Development of Universal Coding Algorithms for Sources with Large and Unbounded Alphabets

点击翻译按钮获取中文摘要

We dealt with the universal coding problems for large and unbounded alphabets, and obtained following results.(1) We propose a practical and fast arithmetic coding algorithm for large alphabets. Our algorithm can be regarded as a natural extension of Multilevel Arithmetic Coding (MAC) proposed by Yang and Jia which is restricted to memoryless sources. On the other hand, our algorithm considers the context in each layer in the MAC, and effectively compresses sequences from sources with memory. Further, we have implemented the proposed algorithm on the personal computer, and have revealed that the compression ratio obtained by the proposed algorithm is about 10% better than that of the original MAC, and that it also outperforms BZIP2 which is one of the best compression algorithm.(2) We consider the universal coding problem for stationary ergodic sources with a countably infinite alphabet A= {1, 2, ・・・}. We show modified versions of LZ78 and LZ77 codes for sources with the alphabet A. Then, we show that for any source μwith E_μ[logX_1] < ∞, both codes are asymptotically optimum, i.e. the code length per input symbol approaches its entropy rate with probability one. Further, we show that both LZ78 and LZ77 codes can be modified such that both are asymptotically optimal for any family of ergodic sources satisfying the Kieffer's condition. Hence, modified versions of LZ78 and LZ77 codes are optimal for countably infinite alphabets as well as finite alphabets.