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

我们用大的和无边界的字母表来解决通用编码问题，并获得了以下结果。（1） We propose a practical and fast arithmetic coding algorithm for large alpha.我们的算法可以作为一个自然扩展的多算术编码（MAC），Yang和Jia提出了对无记忆源的限制。在另一边，我们的算法考虑到MAC中每个层的上下文，以及从存储器中有效地压缩序列的来源。进一步的，我们已经在个人计算机上实现了提议的算法，并且已经揭示了提议的算法所获得的压缩比原始MAC要好10%左右，而且它也是不合格的BZIP 2是最好的压缩算法之一。（2） We consider the universal coding problem for stationary ergodic sources with a countably infinite alphabet A= {1， 2，···}。我们展示了LZ 78和LZ 77代码的修改版本。Then， we show that for any source [logX_1] < ∞， both codes are asymptotically optimum，i. e. the code length per input symbol approaches its entropy rate with probability one。进一步，我们展示了LZ 78和LZ 77代码都可以被修改，这两种代码都是不对称的，以满足Kieffer的条件的任何家族的ergodic源。Hence，LZ 78和LZ 77代码的修改版本是最适合计数无限字母的最佳版本，如完美字母。

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.