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

为具有大且无限制的字母表的源开发通用编码算法

• 批准号: 13650397
• 负责人: UYEMATSU Tomohiko
• 金额: $ 1.09万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2001
• 资助国家: 日本
• 起止时间: 2001 至 2002
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-13650397/
• 关键词: large alphabet; countably infinite alphabet; source coding; arithmetic code; universal code

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.

我们使用通用的编码问题，并获得了以下结果另一方面，我们的算法在Mac中的每个层中的上下文都会进一步压缩来自源的序列。 10％的MAC ORMS BZIP2是最好的压缩算法之一。 。对于任何满足Kieffer状况的千古soudic家族的最佳选择。

项目成果

T. Uyematsu: "Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet"Proc. of Symposium on Information Theory and Its Applications 2001. 481-484 (2001)

T. Uyematsu：“具有可数无限字母表的源的 Lempel-Ziv 代码的两种变体的渐近最优性”Proc。

S. Shimada: "Universal Coding Algorithm of Sources with Large Alphabets"Proc. of the 2002 IEICE General Conference. A-6-3. (2000)

S. Shimada：“大字母源的通用编码算法”Proc。

Tomohiko UYEMATSU, Fumio KANAYA: "Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet"第24回 情報理論とその応用シンポジウム 予稿集. II. 481-484 (2001)

Tomohiko UYEMATSU、Fumio KANAYA：“可数无限字母源的 Lempel-Ziv 代码的两种变体的渐近最优性”第 24 届信息论及其应用研讨会论文集 II（2001 年）。

Tomohiko Uyematsu: "Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet"Proceedings 2002 IEEE International Symposium on Information Theory. 122 (2002)

Tomohiko Uyematsu：“可数无限字母源的 Lempel-Ziv 码的两种变体的渐近最优性”2002 年 IEEE 国际信息论研讨会论文集。

Tomohiko Uyematsu: "Asymptotical Optimality of Two Variations of Lempel-Ziv Codes for Sources with Countably Infinite Alphabet"第24回情報理論とその応用シンポジウム予稿集. II. 481-484 (2001)

Tomohiko Uyematsu：“可数无限字母源的 Lempel-Ziv 码的两种变体的渐近最优性”第 24 届信息论及其应用研讨会论文集 II（2001 年）。