算术编码算法的分析及实现.pdf

声明 本论文题目：算术编码算法的分析与实现，作者：叶叶，于2010 年10 月16 日在编程 论坛上发表。页面地址：/bbs/view12-29356-1.htm 。本论文全文及相关 配套程序可以在上述页面中下载。请尊重他人劳动成果，转载或引用时请注明出处。 目录 1 前言2 2 理论2 2.1 编码2 2.2 解码3 3 改进4 3.1 整数运算4 3.2 正规化5 4 实现8 4.1 编码8 4.2 解码10 4.3 统计模型11 5 分析12 6 结束语12 参考文献13 附录13 算术编码算法的分析与实现 作者：叶叶（网名：yeye55 ） 摘要：分析了算术编码的理论基础，着重介绍WNC 算法的实现方式。详细讨论了算术 编码原理、正规化操作、WNC 算法代码实现等技术。给出了一个切实可行的应用程序。 关键词：算术编码；正规化；Delphi 中图分类号：TP301.6 1 前言 [1] 早在1948 年C. E. Shannon 提出信息论 的时候，就提出了算术编码的思想。但是经过 多年的研究，许多学者认为算术编码是无法实现的。算术编码要求进行无限精度的实数运算， 这在仅能进行有限精度运算的计算机系统上是无法进行的。随着研究的深入，终于在 1987 年Ian H. Witten、Radford M. Neal 和John G. Cleary 发表了一篇论文[2]，提出了一种基于整数 运算的算术编码实现算法。该算法后来被命名为CACM87，并应用于ITU-T 的H.236 视频 编码标准。也有学者根据作者姓名将该算法称之为WNC 算法。WNC 算法是一个实用性算 法，它可以应用在许多方面。在Witten 等人的论文[2] 中给出了一个使用C 语言编写的WNC 算法实现程序的源代码（以下简称“WNC 源代码”）。在许多时候，WNC 源代码已经作为 算术编码的范本程序来使用。本文将分析算术编码的理论基础，并着重介绍WNC 算法的实 现方式。同时给出一个在Delphi 7.0 下开发，使用算术编码算法压缩数据的应用程序。 2 理论 2.1 编码 算术编码将整个要编码的数据映射到一个位于[0,1)的实数区间中。并且输出一个小于1 同时大于0 的小数来表示全部数据。利用这种方法算术编码可以让压缩率无限的接近数据的 熵值，从而获得理论上的最高压缩率。 算术编码进行编码时，从实数区间[0,1)开始。按照符号的频度将当前的区间分割成多个 子区间。根据当前输入的符号选择对应的子区间，然后从选择的子区间中继续进行下一轮的 分割。不断的进行这个过程，直到所有符号编码完毕。对于最后选择的一个子区间，输出属 于该区间的一个小数。这个小数就是所有数据的编码。现在来举个例子。假设一份数据由 “A ”、“B ”、“C ”三个符号组成。现在要编码数据“BCCB ”，编码过程如图2.1 所示。 B C C B 1.0000 0.6667 0.6667 0.6667 C : 1 / 4 C : 1 / 3 C : 2 / 5 0.5834 C : 3 / 6 0.6667