转算术编码算法的分析与实现

《转算术编码算法的分析与实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、转算术编码算法的分析与实现[转]算术编码算法的分析与实现2011-06-0914：20本论文题目：算术编码算法的分析与实现，作者：叶叶，于2010年10月16日在编程论坛上发表。页面地址：。本论文全文及相关配套程序可以在上述页面中下载。请尊重他人劳动成果，转载或引用时请注明出处。目录1前言22理论22.1编码22.2解码33改进43.1整数运算43.2正规化54实现84.1编码84.2解码104.3统计模型115分析126结束语12参考文献13附录13算术编码算法的分析与实现作者：叶叶(网名：yeye55)摘要：分析了算术编码的理论基础，着重介绍WNC算法的实现方式。详细讨论了

2、算术编码原理、正规化操作、WNC算法代码实现等技术。给出了一个切实可行的应用程序。关键词：算术编码；正规化；Delphi中图分类号：TP301.61前言早在1948年C.E.Shannon提出信息论[1]的时候，就提出了算术编码的思想。但是经过多年的研究，许多学者认为算术编码是无法实现的。算术编码要求进行无限精度的实数运算，这在仅能进行有限精度运算的计算机系统上是无法进行的。随着研究的深入，终于在1987年IanH.Witten、RadfordM.Neal和JohnG.Cleary发表了一篇论文[2]，提出了一种基于整数运算的算术编码实现算法。该算法后来被命名为CACM87，并

3、应用于ITU-T的H.236视频编码标准。也有学者根据作者姓名将该算法称之为WNC算法。WNC算法是一个实用性算法，它可以应用在许多方面。在Witten等人的论文[2]中给出了一个使用C语言编写的WNC算法实现程序的源代码(以下简称"WNC源代码")。在许多时候，WNC源代码已经作为算术编码的范本程序来使用。本文将分析算术编码的理论基础，并着重介绍WNC算法的实现方式。同时给出一个在Delphi7.0下开发，使用算术编码算法压缩数据的应用程序。2理论2.1编码算术编码将整个要编码的数据映射到一个位于[0,1)的实数区间中。并且输出一个小于1同时大于0的小数来表示全部数据。利用这

4、种方法算术编码可以让压缩率无限的接近数据的熵值，从而获得理论上的最高压缩率。算术编码进行编码时，从实数区间[0,1)开始。按照符号的频度将当前的区间分割成多个子区间。根据当前输入的符号选择对应的子区间，然后从选择的子区间中继续进行下一轮的分割。不断的进行这个过程，直到所有符号编码完毕。对于最后选择的一个子区间，输出属于该区间的一个小数。这个小数就是所有数据的编码。现在来举个例子。假设一份数据由"A"、"B"、"C"三个符号组成。现在要编码数据"BCCB"，编码过程如图2.1所示。图2.1"BCCB"的编码过程首先说明一点，这里使用的是自适应模型。也就是说一开始时，三个符号的频度

5、都是1。随着编码的进行再更新频度。另外，在计算时理论上要使用无限小数。这里为了说明方便，四舍五入到小数点后4位。观察图2.1可以发现算术编码的过程。首先，算术编码是从区间[0,1)开始的。这时三个符号的概率都是1/3，按照这个概率分割区间。第一个输入的符号是"B"，所以我们选择子区间[0.3333,0.6667)作为下一个区间。输入"B"后更新频度，根据新的概率对区间[0.3333,0.6667)进行分割。这时输入的符号是"C"，我们可以选择子区间[0.5834,0.6667)。继续更新频度、分割区间、选择子区间，直到符号全部编码完成。我们最后得到的区间是[0.6390,0.6

6、501)。输出属于这个区间的一个小数，例如0.64。那么经过算术编码的压缩，数据"BCCB"最后输出的编码就是0.64。2.2解码算术编码进行解码时仅输入一个小数。解码前首先需要对区间[0,1)按照初始时的符号频度进行分割。然后观察输入的小数位于那个子区间。输出对应的符号，选择对应的子区间，然后从选择的子区间中继续进行下一轮的分割。不断的进行这个过程，直到所有的符号都解码出来。整个过程相当于编码时的逆运算。在我们的例子中，输入的小数是0.64。首先，初始时三个符号的概率都是1/3，按照这个概率分割区间。观察图2.1可以发现0.64落在子区间[0.3333,0.6667)中，于是

7、可以解码出"B"。并且选择子区间[0.3333,0.6667)作为下一个区间。输出"B"后更新频度，根据新的概率对区间[0.3333,0.6667)进行分割。这时0.64落在子区间[0.5834,0.6667)中，于是可以解码出"C"。按照上述过程进行，直到所有的符号都解码出来。可见，只需要一个小数就可以完整还原出原来的所有数据。3改进3.1整数运算上一节中描述的算法，在当前的计算机系统上是很难实现的。尤其是无限精度的实数运算。所以在实现的时候，需要对算法做一些改进。使得它可以在当前的计算机