转算术编码算法的分析与实现[转]算术编码算法的分析与实现2011-06-09 14：20本论文题目：算术编码算法的分析与实现，作者：叶叶，于2010年10月16日在编程论坛上发表。

页面地址：。

本论文全文及相关配套程序可以在上述页面中下载。

请尊重他人劳动成果，转载或引用时请注明出处。

目录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前言早在1948年C.E.Shannon提出信息论[1]的时候，就提出了算术编码的思想。

但是经过多年的研究，许多学者认为算术编码是无法实现的。

算术编码要求进行无限精度的实数运算，这在仅能进行有限精度运算的计算机系统上是无法进行的。

随着研究的深入，终于在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所示。

图2.1"BCCB"的编码过程首先说明一点，这里使用的是自适应模型。

也就是说一开始时，三个符号的频度都是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.6501)。

输出属于这个区间的一个小数，例如0.64。

那么经过算术编码的压缩，数据"BCCB"最后输出的编码就是0.64。

2.2解码算术编码进行解码时仅输入一个小数。

解码前首先需要对区间[0,1)按照初始时的符号频度进行分割。

然后观察输入的小数位于那个子区间。

输出对应的符号，选择对应的子区间，然后从选择的子区间中继续进行下一轮的分割。

不断的进行这个过程，直到所有的符号都解码出来。

整个过程相当于编码时的逆运算。

在我们的例子中，输入的小数是0.64。

首先，初始时三个符号的概率都是1/3，按照这个概率分割区间。

观察图2.1可以发现0.64落在子区间[0.3333,0.6667)中，于是可以解码出"B"。

并且选择子区间[0.3333,0.6667)作为下一个区间。

输出"B"后更新频度，根据新的概率对区间[0.3333,0.6667)进行分割。

这时0.64落在子区间[0.5834,0.6667)中，于是可以解码出"C"。

按照上述过程进行，直到所有的符号都解码出来。

可见，只需要一个小数就可以完整还原出原来的所有数据。

3改进3.1整数运算上一节中描述的算法，在当前的计算机系统上是很难实现的。

尤其是无限精度的实数运算。

所以在实现的时候，需要对算法做一些改进。

使得它可以在当前的计算机系统上较快的运行。

当然，这种改进是以降低运算精度为代价的。

也就是说，这种改进实际上会降低算法的压缩率。

但是，它会使算法的实现成为可能。

观察前面描述的算法过程可以发现，运算时区间的上下沿都是小于1的小数。

那么我们可以省略0和小数点，仅仅使用小数的尾数来表示小数。

省略0和小数点后的尾数，实际上就是一个无限大的整数。

使用无限整数的部分高位来表示整数，并在这些整数上进行整数运算就可以模拟出实数运算。

在我们的例子里，可以使用区间[3333,6667)来表示区间[0.3333,0.6667)。

最后可以输出64来表示0.64。

另外，分割区间、选择子区间的过程，相当于将一个区间映射到另一个更小的区间中(以下简称"映射区间")。

如果我们知道一个符号的频度。

以及符号值小于该符号的其它符号的频度总计(以下简称"累积频度(Cumulative Frequency)")。

还有到目前为止所有符号频度的总计(以下简称"总计频度(Total Frequency)")。

那么就可以根据这些频度信息，从当前区间中计算出映射区间。

计算的公式如下。

Range=High-Low+1 High=Low+Range*(CumFreq+Freq)div Total-1Low=Low+Range*CumFreq div Total其中Low表示区间的下沿；High表示区间的上沿；Range表示区间的范围；Freq 表示符号频度；CumFreq表示累积频度；Total表示总计频度。

这些变量中保存的都是整数，并进行整数运算。

其中div表示整除。

另外需要注意一点，这里使用闭区间[Low,High]，而不是使用右开区间[Low,High)。

在我们的例子里，实数运算时四舍五入到小数点后4位。

那么在整数运算时可以采用4位整数来进行。

初始区间可以设定在[0,9999]的闭区间中。

按照上述公式进行编码计算所得的结果如表3.1所示。

输入数据输入符号映射区间区间范围""[0000,9999]10000"B"B[3333,6665]3333"BC"C[5832,6665]834"BCC"C[6332,6665]334"BCCB"B[6387,6498]112表3.1整数运算的区间变化将表3.1中的数据与图2.1中的数据进行对比可以发现，整数运算会降低运算精度。

整数运算时最后映射到区间[6387,6498]，实数运算时最后映射到区间[0.6390,0.6501)。

由于精度降低运算出现了误差，但是我们仍旧可以输出64代替0.64来表示整个数据。

所以这种精度的降低是在允许的范围内。

在解码的时候也可以进行整数运算。

根据输入的整数数值、当前区间的下沿和总计频度，可以计算出一个估算出来的累积频度(以下简称"估算频度(Estimate Frequency)")。

其计算公式如下。

Range=High-Low+1 EstFreq=((Value-Low+1)*Total-1)div Range其中，Value表示输入的整数数值；EstFreq表示估算频度。

利用估算频度在当前的累积频度表中查找，当满足CumFreq≤EstFreq<CumFreq+Freq的条件时，就可以解码出一个符号。

利用解码出的符号可以得到对应的累积频度和频度。

根据这些频度信息，可以从当前区间中计算出映射区间。

这一点同编码时是一样的。

计算出映射区间后，更新对应符号的频度，又可以进行新的一轮解码。

在我们的例子中，输入的整数数值是64。

但是64本质上是0.64，所以在参与运算时要将64扩展成6400。

初始时区间的范围同编码时是一样的，从[0,9999]开始。

利用6400进行解码，其过程如表3.2所示。

映射区间估算频度累积频度解码符号A BC[0000,9999]1 01 2B[3333,6665]3 01 3C[5832,6665]3 01 3C[6332,6665]1 01 3B表3.2整数运算的解码过程可以看出利用一个整数数值64，就可以解码出全部数据。

另外，观察解码过程可以发现。

在解码时不仅要计算映射区间，还要计算和查找估算频度。

所以算术编码的解码过程通常要比编码过程慢。

在本小节中给出的计算公式都来自WNC源代码。

观察这些计算公式可以发现，有许多运算是重复的。

这意味着，这些公式还有改进的可能。

在本文的第4节中将给出改进后的计算方法。

3.2正规化上述算法实际上是无法实现的。

观察表3.1可以发现，随着编码的进行区间范围会越来越小，最后区间范围会趋向0。

如果编码较长的数据，区间范围为0时就无法继续编码。

解决这一问题的方法是使用正规化(Renormalization,又称"归一化")。

正规化操作就是当区间的上下沿满足一定的条件时，将一定的位数从区间中移出，同时对区间进行一次放大。

使用正规化操作，可以在有限区间上模拟无限区间的运算。

当然这种模拟同样会降低精度，但是它让无限区间的运算成为可能。

下面就来介绍正规化操作的过程。

上一节已经说过，区间的运算可以转换为整数运算。

而区间的上下沿都是用整数来保存。

在实现的时候，都是进行二进制整数运算。

在本节中为了说明方便全部使用二进制整数来表示区间的上下沿。

那么对于一个区间的上下沿有可能出现以下两中情况。

[00101101,或[10101101,01001011]11001011]情况1情况2可以发现这两种情况中，区间上下沿的最高位都是相同的。