算术编码的原理与分析

转自：http://kulasuki115.blogcn.com/diary,201492702.shtml

前言

　　人类已进入信息时代，信息时代的重要特征是信息的数字化，人们越来越依靠计算机获取和利用信息，这就需要对信息的表示、存储、传输和处理等关键技术进行研究。我们要把数值、文字、语言、声音、图像、图形、视频和动画等多种媒体转化成计算机所能处理的数字信息，但数字化后的视频和音频等媒体信息的数据量是非常大的。因此，数字化信息的数据量很大，这样大的数据量，无疑给存储器的存储容量、通信干线的信道传输率以及计算机的速度都提出了很高的要求。这个问题是多媒体技术发展中的一个非常棘手的瓶颈问题。要解决这一问题，单纯用扩大存储器容量、增加通信干线的传输率的办法是不现实的，采用数据压缩技术才是行之有效的方法。通过数据压缩手段减少信息数据量，以压缩形式存储和传输，既节约了存储空间，又提高了通信干线的传输效率。数据压缩技术的研究受到人们越来越多的关注，从基本的无损压缩到语音，图像和视频信号等信号的有损压缩，数据压缩在人们的日常生活中发挥着越来越重要的作用。

　　根据解码后数据与原始数据是否完全一致进行分类，数据压缩方法一般分为两类：①无损压缩，即解码图像与原始图像严格相同，压缩比大约在2：1－5：1之间，如霍夫曼编码，算术编码等；②有损编码，即还原图像与原始图像存在一定的误差，但视觉效果一般可以接受，压缩比可以从几倍到上百倍，如：PCM编码，预测编码、变换编码等。

　　算术编码作为一种高效的数据编码方法在文本，图像，音频：等压缩中有广泛的应用。它是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman编码效率提高10％左右。

　　在这篇论文中我们就来分析一下算术编码的原理，以及它与Huffman编码的区别,它的发展前景等，最后运用Visual C++来具体实现一个简单的算术编码器。

算术编码原理分析与实现

第一章：选题背景

1.1、算术编码的发展史

　　1948年，Shannon在提出信息熵理论的同时，也给出了一种简单的编码方法——Shannon编码。Shannon提出将信源符号依其出现的概率进行降序排列，用符号序列累计概率的二进制作为对信源的编码，并从理论上论证的了它的优越性。1952年，R.M.Fano又进一步提出了Fano编码。这些早期的编码方法揭示了变长编码的基本规律，也确实可以取得一定的压缩效果，但离真正实用的压缩算法还相去甚远。

　　第一个实用的编码方法是由D.A.Huffman在1952年的论文“最小冗余度代码的构造方法（A Method for the Construction of Minimum Redundancy Codes）”中提出的。直到今天，许多《数据结构》教材在讨论二叉树时仍要提及这种被后人称为Huffman编码的方法。Huffman编码在计算机界是如此著名，以至于连编码的发明过程本身也成了人们津津乐道的话题。据说，1952年时，年轻的Huffman还是麻省理工学院的一名学生，他为了向老师证明自己可以不参加某门功课的期末考试，才设计了这个看似简单，但却影响深远的编码方法。

　　Huffman编码效率高，运算速度快，实现方式灵活，从20世纪60年代至今，在数据压缩领域得到了广泛的应用。例如，早期UNIX系统上一个不太为现代人熟知的压缩程序COMPACT实际就是Huffman 0阶自适应编码的具体实现。1960年伊莱亚斯（Peter Elias）发现无需排序，只要编、解码端使用相同的符号顺序即可，并提出了算术编码的概念。伊莱亚斯没有公布他的发现，因为他知道算术编码在数学上虽然成立，但不可能在实际中实现。1976年，帕斯科（R.Pasco）和瑞萨尼恩（J.Rissanen）分别用定长的寄存器实现了有限精度的算术编码。20世纪80年代初，Huffman编码又出现在CP/M和DOS系统中，其代表程序叫SQ。今天，在许多知名的压缩工具和压缩算法（如WinRAR、gzip和JPEG）里，都有Huffman编码的身影。不过，Huffman编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。正因为如此，现代压缩技术通常只将Huffman视作最终的编码手段，而非数据压缩算法的全部。

　　科学家们一直没有放弃向信息熵极限挑战的理想。1968年前后，P.Elias发展了Shannon和Fano的编码方法，构造出从数学角度看来更为完美的Shannon-Fano-Elias编码。沿着这一编码方法的思路，1976年，J.Rissanen提出了一种可以成功地逼近信息熵极限的编码方法——算术编码。1979年，瑞萨尼恩和兰顿（G.G.Langdon）一起将算术编码系统化，并于1981年实现了二进制编码。

　　1982年，Rissanen和G.G.Langdon一起改进了算术编码。之后，人们又将算术编码与J.G.Cleary和I.H.Witten于1984年提出的部分匹配预测模型（PPM）相结合，开发出了压缩效果近乎完美的算法。1987年，威滕（Witten）等人发表了一个实用的算术编码程序。同期，IBM公司发表了著名的Q编码器（后用于JPEG和JBIG图像压缩标准）。从此，算术编码迅速得到了广泛的注意。

1.2、选择算术编码的原因

　　关于熵（Entropy）的概念：⑴熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就越小，数字上就是概率越小。⑵某个事件的信息量用=-lo表示，其中为第i个事件的概率，0〈1。按照香农（shannon）的理论，信源S的熵的定义为H(S)==lo(1/)其中是符号在S中出现的概率；lo(1/)表示包含在中的信息量，也就是编码所需要的位数。例如，一幅用256灰度级表示的图像，如果每一个象素点灰度的概率均为=1/256，编码每一个象素点就需要8位。

　　熵作为理论上的平均信息量，即编码一个信源符号所需的二进制位数，在实际的压缩编码中的码率很难达到熵值，不过熵可以作为衡量一种压缩算法的压缩比好坏的标准，码率越接近熵值，压缩比越高。
由于在许多场合，开始不知道要编码数据的统计特性，也不一定允许你事先知道它们的编码特性，因此算术编码在不考虑信源统计特性的情况下，只监视一小段时间内码出现的概率，不管统计是平稳的或非平稳的，编码的码率总能趋近于信源的熵值。

　　实现算术编码首先需要知道信源发出每个符号的概率大小，然后再扫描符号序列，依次分割相应的区间，最终得到符号序列所对应的码字。整个编码需要两个过程，即概率模型建立过程和扫描编码过程。

1.3、算术编码的原理

　　算术编码的基本原理是：根据信源可能发现的不同符号序列的概率，把[0，1]区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列的概率。这样信源发出的不同符号序列将与各子区间一一对应，因此每个子区间内的任意一个实数都可以用来表示对应的符号序列，这个数就是该符号序列所对应的码字。显然，一串符号序列发生的概率越大，对应的子区间就越宽，要表达它所用的比特数就减少，因而相应的码字就越短。

　　图1给出一个实现算术编码的示例。要编码的是一个来自四符号信源{A，B，C，D}的由五个符号组成的符号序列：ABBCD。假设已知各信源符号的概率分别为：P(A)=0.2,P(B)=0.4,P(C)=0.2,P(D)=0.2。编码时，首先根据各个信源符号的概率将区间[0，1]。分成四个子区间。符号A对应[0，0.2]，符号B对应[0.2,0.6]，符号C对应[0.6,0.8]，符号D对应[0.8,1.0]。符号序列中第一个符号是A，其对应的区间为[0,0.2]，接下来将这个区间扩展为整个高度，再根据各个信源符号的概率将这个间扩展为整个高度，再根据各个信源符号的概率将这个新区间分成四段；第二个符号是B，它对应新的子区间的第二个子区间，即对应区间[0.04,0.12]；再将该区间扩展为整个高度，再根据这个过程直接最后一个符号得到一个区间[0.08032,0.0816]，这样该区间内的任何一个实数就可以表示整个符号序列，如0.081。

1.4、算术编码研究的目的和意义

　　各种媒体信息（特别是图像和动态视频）数据量非常之大。例如：一幅640x480分辨率的24位真彩色图像的数据量约力9O0kb；一个1O0Mb的硬盘只能存储约l00幅静止图像画面。显然，这样大的数据量不仅超出了计算机的存储和处理能力，更是当前通信信道的传输速率所不及的。因此，为了存储、处理和传输这些数据，必须进行压缩。相比之下，语音的数据量较小，且基本压缩方法己经成熟，目前的数据压缩研究主要集中于图像和视频信号的压缩方面。图像压缩技术、视频技术与网络技术相结合的应用前景十分可观，如远程图像传输系统、动态视频传输一可视电话、电视会议系统等己经开始商品化，MPEG标准与视频技术相结合的产物一家用数字视盘机和VideoCD系统等都已进入市场。可以预计，这些技术和产品的发展将对本世纪末到二十一世纪的社会进步产生重大影响。而算术编码作为一种高效的数据编码方法在文本，图像，音频等压缩中有广泛的应用，所以，研究算术编码以更好的利用它是非常必要的。

1.5、算术编码的国内外研究现状和发展趋势

　　数字视频技术广泛应用于通信、计算机、广播电视等领域，带来了会议电视、可视电话及数字电视、媒体存储等一系列应用，促使了许多视频编码标准的产生。ITU-T与ISO/IEC是制定视频编码标准的两大组织，ITU-T的标准包括H.261、H.263、H.264，主要应用于实时视频通信领域，如会议电视；MPEG系列标准是由ISO/IEC制定的，主要应用于视频存储（DVD）、广播电视、因特网或无线网上的流媒体等。两个组织也共同制定了一些标准，H.262标准等同于MPEG-2的视频编码标准，而最新的H.264标准则被纳入MPEG-4的第10部分。本文按照ITU-T视频编码标准的发展过程，介绍H.261、H.263及H.264。

　　随着处理能力和存储器两者成本的降低，编码视频数据的网络支持变化多端及视频压缩编码技术的快速发展，旨在充分提高编码效率和增强网络环境稳定性的视频编码标准的需求日益上升。为了达到这些目的。ITU-T视频编码专家组（VCEG）和ISO/IEC运动图像专家组（MPEG）在2001年成立了一个联合视频小组（JVT），研究开发出一种新的高质量，低比特率的视频标准。实际上，1998年1月份就开始草案征集，1999年9月完成第一个草案，这便是H。26L草案。2001年7月，MPEG认为新的编码方式较之MPEG-4现有标准有很大优势，有必要吸收最新成果完善MPEG-4。为此，联合视频小组（JVT）开展了对H。26L研究。制定出基于高的视频分辨率的标准。旨在改善图像质量，并能够覆盖所有低带宽和高带宽的应用。2002年6月的JVT第5次会议通过了新标准的FCD版，2003年3月正式发布，新标准的名称为ITU-TH。26L或ISO/IEC MPEG-4AVC（或14496-10AVC）。H。264是ITU-T增强型多媒体通信标准H。26L基础上推出的能够为ITU-T和ISO/IEC共同使用的新一代视频编码标准，并且和MPEG毓标准形成技术体系。

　　H.264是由ISO/IEC与ITU-T组成的联合视频组（JVT）制定的新一代视频压缩编码标准。事实上，H.264标准的开展可以追溯到8年前。1996年制定H.263标准后，ITU-T的视频编码专家组（VCEG）开始了两个方面的研究：一个是短期研究计划，在H.263基础上增加选项（之后产生了H.263+与H.263++）；另一个是长期研究计划，制定一种新标准以支持低码率的视频通信。长期研究计划产生了H.26L标准草案，在压缩效率方面与先期的ITU-T视频压缩标准相比，具有明显的优越性。2001年，ISO的MPEG组织认识到H.26L潜在的优势，随后ISO与ITU开始组建包括来自ISO/IEC MPEG与ITU-T VCEG的联合视频组（JVT），JVT的主要任务就是将H.26L草案发展为一个国际性标准。于是，在ISO/IEC中该标准命名为AVC（Advanced Video Coding），作为MPEG-4标准的第10个选项；在ITU-T中正式命名为H.264标准。H.264的主要优点如下：在相同的重建图像质量下，H.264比H.263+和MPEG-4（SP）减小50%码率。对信道时延的适应性较强，既可工作于低时延模式以满足实时业务，如会议电视等；又可工作于无时延限制的场合，如视频存储等。提高网络适应性，采用“网络友好”的结构和语法，加强对误码和丢包的处理，提高解码器的差错恢复能力。在编/解码器中采用复杂度可分级设计，在图像质量和编码处理之间可分级，以适应不同复杂度的应用。相对于先期的视频压缩标准，H.264引入了很多先进的技术，包括4×4整数变换、空域内的帧内预测、1/4象素精度的运动估计、多参考帧与多种大小块的帧间预测技术等。新技术带来了较高的压缩比，同时大大提高了算法的复杂度。H.264标准采用的熵编码有两种：一种是基于内容的自适应变长编码（CAVLC）与统一的变长编码（UVLC）结合；另一种是基于内容的自适应二进制算术编码（CABAC）。CAVLC与CABAC根据相临块的情况进行当前块的编码，以达到更好的编码效率。CABAC比CAVLC压缩效率高，但要复杂一些。除上述ITU-T的视频压缩标准外，还有一些标准也比较流行，如MPEG-4、AVS、WM9 H.264也称为MPEG-4 AVC，而目前业内所说的MPEG-4一般是指SP（简级）或ASP（先进的简级），主要针对低码率应用，如因特网上的流媒体、无线网的视频传输及视频存储等，其核心类似于H.263。MPEG-4 SP和H.263有很多相似的地方，如附表所示。然而，这两个标准之间也有显著的不同，主要表现在：码流结构和头信息、

　　熵编码的部分码表、编码技术的一些细节。MPEG-4 ASP较SP增加了一些技术，主要有：1/4象素精度的运动估计、B帧、全局运动矢量（GMV），因而压缩效率得以提高。AVS是由我国自主制定的音/视频编码技术标准，主要面向高清晰度电视、高密度光存储媒体等应用。AVS标准以当前国际上最先进的MPEG-4 AVC/H.264框架为基础，强调自主知识产权，同时充分考虑了实现的复杂度。相对于H.264，AVS的主要特点有：（1）8×8的整数变换与64级量化；（2）亮度和色度帧内预测都是以8×8块为单位，亮度块采用5种预测模式，色度块采用4种预测模式；（3）采用16×16、16×8、8×16和8×8 4种块模式进行运动补偿；（4）在1/4象素运动估计方面，采用不同的四抽头滤波器进行半象素插值和1/4象素插值；（5）P帧可以利用最多2帧的前向参考帧，而B帧采用前后各一个参考帧。Window Meida 9（WM9）是微软公司开发的新一代数字媒体技术。一些测试表明，WM9的视频压缩效率比MPEG-2、MPEG-4 SP及H.263高很多，而与H.264的压缩效率相当。目前，H.261与H.263在视频通信中广泛应用，成熟的产品已经很多。H.263与H.261相比，增加了若干选项，提供了更灵活的编码方式，压缩效率大大提高，更适应网络传输。H.264标准的推出，是视频编码标准的一次重要进步，它与现有的MPEG-2、MPEG-4 SP及H.263相比，具有明显的优越性，特别是在编码效率上的提高，使之能用于许多新的领域。尽管H.264的算法复杂度是现有编码压缩标准的4倍以上，随着集成电路技术的快速发展，H.264的应用将成为现实。

第二章：原理分析

2.1、算术编码过程简述

　　算术编码在图像数据压缩标准（如JPEG，JBIG）中扮演了重要的角色。在算术编码中，消息用0到1之间的实数进行编码，算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。算术编码器的编码过程可用下面的例子加以解释。

　　[例1] 假设信源符号为{00, 01, 10, 11}，这些符号的概率分别为{ 0.1, 0.4, 0.2, 0.3 }，根据这些概率可把间隔[0, 1)分成4个子间隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1)，其中 表示半开放间隔，即包含 不包含 。上面的信息可综合在表1中。

表1、信源符号，概率和初始编码间隔

　　如果二进制消息序列的输入为：10 00 11 00 10 11 01。编码时首先输入的符号是10，找到它的编码范围是[0.5, 0.7)。由于消息中第二个符号00的编码范围是[0, 0.1)，因此它的间隔就取[0.5, 0.7)的第一个十分之一作为新间隔[0.5, 0.52)。依此类推，编码第3个符号11时取新间隔为[0.514, 0.52)，编码第4个符号00时，取新间隔为[0.514, 0.5146)，… 。消息的编码输出可以是最后一个间隔中的任意数。整个编码过程如图1所示。

图1、算术编码过程举例

　　这个例子的编码和译码的全过程分别表示在表2和表3中。根据上面所举的例子，可把计算过程总结如下。
考虑一个有M个符号 的字符表集，假设概率 ，而 。输入符号用 表示，第 个子间隔的范围用 表示。其中 ， 和 ， 表示间隔左边界的值, 表示间隔右边界的值， 表示间隔长度。编码步骤如下：

　　步骤1：首先在1和0之间给每个符号分配一个初始子间隔，子间隔的长度等于它的概率，初始子间隔的范围用 [ ， )表示。令 ， 和 。

　　步骤2：L和R的二进制表达式分别表示为：
和
其中 和 等于“1”或者“0”。
比较 和 ：①如果 ，不发送任何数据，转到步骤3；②如果 ，就发送二进制符号 。
比较 和 ：①如果 ，不发送任何数据，转到步骤3；②如果 ，就发送二进制符号 。
…
这种比较一直进行到两个符号不相同为止，然后进入步骤3，

　　步骤3： 加1，读下一个符号。假设第 个输入符号为 ，按照以前的步骤把这个间隔分成如下所示的子间隔：

令 ， 和 ，然后转到步骤2。

步骤 输入符号编码间隔 编码判决
110[0.5, 0.7)符号的间隔范围[0.5, 0.7)
200[0.5, 0.52)[0.5, 0.7)间隔的第一个1/10
311[0.514, 0.52)[0.5, 0.52)间隔的最后一个1/10
400[0.514, 0.5146)[0.514, 0.52)间隔的第一个1/10
510[0.5143, 0.51442)[0.514, 0.5146)间隔的第五个1/10开始，二个1/10
611[0.514384, 0.51442)[0.5143, 0.51442)间隔的最后3个1/10
701[0.5143836, 0.514402)[0.514384, 0.51442)间隔的4个1/10，从第1个1/10开始
8从[0.5143876, 0.514402中选择一个数作为输出：0.5143876
表2、编码过程

步骤 间隔译码符号 译码判决
1[0.5, 0.7)100.51439在间隔 [0.5, 0.7)
2[0.5, 0.52)000.51439在间隔 [0.5, 0.7)的第1个1/10
3[0.514, 0.52)110.51439在间隔[0.5, 0.52)的第7个1/10
4[0.514, 0.5146)000.51439在间隔[0.514, 0.52)的第1个1/10
5[0.5143, 0.51442)100.51439在间隔[0.514, 0.5146)的第5个1/10
6[0.514384, 0.51442)110.51439在间隔[0.5143, 0.51442)的第7个1/10
7[0.51439, 0.5143948)010.51439在间隔[0.51439, 0.5143948)的第1个1/10
7译码的消息：10 00 11 00 10 11 01
表3、译码过程

　　[例2] 假设有4个符号的信源，它门的概率如表4所示：

信源符号ai
概率
初始编码间隔[0, 0.5)[0.5, 0.75)[0.75, 0.875)[0.875, 1)
表4、符号概率

输入序列为 。它的编码过程如图2所示，现说明如下。
输入第1个符号是 ，可知 ，定义初始间隔 [ ， )＝[0.5, 0.75)，由此可知 ，左右边界的二进制数分别表示为：L＝0.5=0.1(B)，R＝0.7＝0.11… (B) 。按照步骤2， ，发送1。因 ，因此转到步骤3。
输入第2个字符 ， ，它的子间隔 ， )＝[0.5, 0.625)，由此可得 =0.125。左右边界的二进制数分别表示为：L＝0.5=0.100 … (B)，R＝0.101… (B)。按照步骤2， ，发送0，而 和 不相同，因此在发送0之后就转到步骤3。
输入第3个字符， ， , 它的子间隔 [ , )＝[0.59375, 0.609375)，由此可得 =0.015625。左右边界的二进制数分别表示为： ＝0.59375=0.10011 (B)， ＝0.609375=0.100111 (B)。按照步骤2， ， ， ，但 和 不相同，因此在发送011之后转到步骤3。
…
发送的符号是：10011…。被编码的最后的符号是结束符号。

图2、算术编码概念

　　就这个例子而言，算术编码器接受的第1位是“1”，它的间隔范围就限制在[0.5, 1)，但在这个范围里有3种可能的码符 , 和 ，因此第1位没有包含足够的译码信息。在接受第2位之后就变成“10”，它落在[0.5, 0.75)的间隔里，由于这两位表示的符号都指向 开始的间隔，因此就可断定第一个符号是 。在接受每位信息之后的译码情况如下表5所示。

接受的数字间隔译码输出
1[0.5, 1)-
0[0.5, 0.75)
0[0.5, 0.609375)
1[0.5625, 0.609375)-
1[0.59375, 0.609375)
………
表5、译码过程表

　　在上面的例子中，我们假定编码器和译码器都知道消息的长度，因此译码器的译码过程不会无限制地运行下去。实际上在译码器中需要添加一个专门的终止符，当译码器看到终止符时就停止译码。

转自：http://kulasuki115.blogcn.com/diary,201492702.shtml

2.2、算术编码与Huffman编码的区别

　　霍夫曼编码属于码字长度可变的编码类，即从下到上的编码方法。同其他码字长度可变的编码一样，可区别的不同码字的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”的技术。算法步骤如下： ① 初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 ② 把概率最小的两个符号组成一个新符号，即新符号的概率等于这两个符号概率之和。 ③ 重复第②步，直到形成一个符号为止，其概率最后等于1。 ④ 从编码树的根开始回溯到原始的符号，并将每一个下分枝赋值为1，上分枝赋值为0。

　　采用霍夫曼编码时有两个问题值得注意： ① 霍夫曼编码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，哪怕仅仅是 1位出现错误，也会引起一连串的错误，这种现象称为错误传播。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。 ② 霍夫曼编码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。

　　而算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔，消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。 算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0到1之间。编码过程中的间隔决定了符号压缩后的输出。 给定事件序列的算术编码步骤如下： ① 编码器在开始时将“当前间隔”[L，H]设置为[0，1]。 ② 对每一事件，编码器按步骤A和B进行处理。 A．编码器将“当前间隔”分为子间隔，每一个事件一个。 B．一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔对应于下一个确切发生的事件，并使它成为新的“当前间隔”。③最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。

　　算术编码是一种到目前为止编码效率最高的统计熵编码方法,它比著名的Huffman编码效率提高10％左右,但由于其编码复杂性和实现技术的限制以及一些专利权的限制,所以并不象Huffman编码那样应用广泛。算术编码有两点优于Huffman码： ①它的符号表示更紧凑； ②它的编码和符号的统计模型是分离的，可以和任何一种概率模型协同工作。后者非常重要, 因为只要提高模型的性能就可以提高编码效率。

　　Huffman 码字必定是整数的比特长,这样就会产生问题:如一个符号的概率为1P3 ,则编码该符号的最优比特数大约是1.6，那么Huffman不得不将其码字设为1比特或2比特,并且每种选择都会得到比理论上可能的长度更长的压缩消息。而算术编码可以解决这个问题。算术编码是一种高效清除字串冗余的算法。它避开用一个特定码字代替一输入符号的思想,而用一个单独的浮点数来代替一串输入符号, 避开了Huffman编码中比特数必须取整的问题。但是算术编码的实现有两大缺陷： ① 很难在具有固定精度的计算机完成无限精度的算术操作。 ② 高度复杂的计算量不利于实际应用。

　　算术编码是一种无失真的编码方法，能有效地压缩信源冗余度，属于熵编码的一种。算术编码的一个重要特点就是可以按分数比特逼近信源熵，突破了Haffman编码每个符号只不过能按整数个比特逼近信源熵的限制。对信源进行算术编码，往往需要两个过程，第一个过程是建立信源概率表，第二个过程是对信源发出的符号序列进行扫描编码。而自适应算术编码在对符号序列进行扫描的过程中，可一次完成上述两个过程，即根据恰当的概率估计模型和当前符号序列中各符号出现的频率，自适应地调整各符号的概率估计值，同时完成编码。尽管从编码效率上看不如已知概率表的情况，但正是由于自适应算术编码具有实时性好、灵活性高、适应性强等特点，在图像压缩、视频图像编码等领域都得到了广泛的应用。

2.3、算术编码的静态与自适应模型

　　举个简单的例子来说明吧。考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压缩保存的信息为 bccb。对信息 bccb 我们统计出其中只有两个字符，概率分布为 Pb = 0.5，Pc = 0.5。我们在压缩过程中不必再更新此概率分布，每次对区间的划分都依照此分布即可，对上例也就是每次都平分区间。这样，我们的压缩过程可以简单表示为：

输出区间的下限 输出区间的上限

--------------------------------------------------

压缩前 0.0 1.0

输入 b 0.0 0.5

输入 c 0.25 0.5

输入 c 0.375 0.5

输入 b 0.375 0.4375

　　可以看出，最后的输出区间在 0.375 - 0.4375 之间，该信息的熵值为 4 个二进制位，甚至连一个十进制位都没有确定，也就是说，整个信息根本用不了一个十进制位。如果改用二进制来表示上述过程的话，会发现可以非常接近该信息的熵值。

　　那为什么还要采用自适应模型呢？因为静态模型无法适应信息的多样性，例如，以上得出的概率分布没法在所有待压缩信息上使用，为了能正确解压缩，必须再消耗一定的空间保存静态模型统计出的概率分布，保存模型所用的空间将使我们重新远离熵值。其次，静态模型需要在压缩前对信息内字符的分布进行统计，这一统计过程将消耗大量的时间，使得本来就比较慢的算术编码压缩更加缓慢。另外还有最重要的一点，对较长的信息，静态模型统计出的符号概率是该符号在整个信息中的出现概率，而自适应模型可以统计出某个符号在某一局部的出现概率或某个符号相对于某一上下文的出现概率，换句话说，自适应模型得到的概率分布将有利于对信息压缩（可以说结合上下文的自适应模型的信息熵建立在更高的概率层次上，其总熵值更小），好的基于上下文的自适应模型得到的压缩结果将远远超过静态模型。

　　通常用“阶”（order）这一术语区分不同的自适应模型。刚刚上面的例子采用的是0阶自适应模型，也就是说，该例子中统计的是符号在已输入信息中的出现概率，没有考虑任何上下文信息。如果我们将模型变成统计符号在某个特定符号后的出现概率，那么，模型就成为了 1 阶上下文自适应模型。举例来说，要对一篇英文文本进行编码，已经编码了 10000 个英文字符，刚刚编码的字符是 t，下一个要编码的字符是 h。如果在前面的编码过程中已经统计出前 10000 个字符中出现了 113 次字母 t，其中有 47 个 t 后面跟着字母 h。得出字符 h 在字符 t 后的出现频率是 47/113，我们使用这一频率对字符 h 进行编码，需要 - ＝1.266位。
对比 0 阶自适应模型，如果前 10000 个字符中 h 的出现次数为 82 次，则字符 h 的概率是 82/10000，我们用此概率对 h 进行编码，需要 － = 6.930 位。考虑上下文因素的优势显而易见。我们还可以进一步扩大这一优势，例如要编码字符 h 的前两个字符是 gt，而在已经编码的文本中 gt 后面出现 h 的概率是 80%，那么只需要 0.322 位就可以编码输出字符h。此时，这种模型叫做 2 阶上下文自适应模型。

　　最理想的情况是采用 3 阶自适应模型。此时，如果结合算术编码，对信息的压缩效果将达到惊人的程度。采用更高阶的模型需要消耗的系统空间和时间至少在目前还无法让人接受，使用算术压缩的应用程序大多数采用 2 阶或 3 阶的自适应模型。

2.4、算术编码的转义码

　　使用自适应模型的算术编码算法必须考虑如何为从未出现过的上下文编码。例如，在 1 阶上下文模型中，需要统计出现概率的上下文可能有 256 * 256 = 65536 种，因为 0 - 255 的所有字符都有可能出现在 0 - 255 个字符中任何一个之后。当我们面对一个从未出现过的上下文时（比如刚编码过字符 b，要编码字符 d，而在此之前，d 从未出现在 b 的后面），该怎样确定字符的概率呢？

　　比较简单的办法是在压缩开始之前，为所有可能的上下文分配计数为 1 的出现次数，如果在压缩中碰到从未出现的 bd 组合，我们认为 d 出现在 b 之后的次数为 1，并可由此得到概率进行正确的编码。使用这种方法的问题是，在压缩开始之前，在某上下文中的字符已经具有了一个比较小的频率。例如对 1 阶上下文模型，压缩前，任意字符的频率都被人为地设定为 1/65536，按照这个频率，压缩开始时每个字符要用 16 位编码，只有随着压缩的进行，出现较频繁的字符在频率分布图上占据了较大的空间后，压缩效果才会逐渐好起来。对于 2 阶或 3 阶上下文模型，情况就更糟糕，我们要为几乎从不出现的大多数上下文浪费大量的空间。

　　我们通过引入“转义码”来解决这一问题。“转义码”是混在压缩数据流中的特殊的记号，用于通知解压缩程序下一个上下文在此之前从未出现过，需要使用低阶的上下文进行编码。举例来讲，在 3 阶上下文模型中，我们刚编码过 ght，下一个要编码的字符是 a，而在此之前，ght 后面从未出现过字符 a，这时，压缩程序输出转义码，然后检查 2 阶的上下文表，看在此之前 ht 后面出现 a 的次数；如果 ht 后面曾经出现过 a，那么就使用 2 阶上下文表中的概率为 a 编码，否则再输出转义码，检查 1 阶上下文表；如果仍未能查到，则输出转义码，转入最低的 0 阶上下文表，看以前是否出现过字符 a；如果以前根本没有出现过 a，那么我们转到一个特殊的“转义”上下文表，该表内包含 0 - 255 所有符号，每个符号的计数都为 1，并且永远不会被更新，任何在高阶上下文中没有出现的符号都可以退到这里按照 1/256 的频率进行编码。“转义码”的引入使我们摆脱了从未出现过的上下文的困扰，可以使模型根据输入数据的变化快速调整到最佳位置，并迅速减少对高概率符号编码所需要的位数。

2.5、算术编码中需要注意的几个问题

　　由于实际的计算机的精度不可能无限长，运算中出现溢出是一个明显的问题，但多数机器都有16位、32位或者64位的精度，因此这个问题可使用比例缩放方法解决。算术编码器对整个消息只产生一个码字，这个码字是在间隔[0, 1)中的一个实数，因此译码器在接受到表示这个实数的所有位之前不能进行译码。

　　⑴算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。⑵算术编码可以是静态的或者自适应的。在静态算术编码中，信源符号的概率是固定的。在自适应算术编码中，信源符号的概率根据编码时符号出现的频繁程度动态地进行修改，在编码期间估算信源符号概率的过程叫做建模。需要开开发态算术编码的原因是因为事先知道精确的信源概率是很难的，而且是不切实际的。当压缩消息时，我们不能期待一个算术编码器获得最大的效率，所能做的最有效的方法是在编码过程中估算概率。算术编码的静态与自适应模型因此动态建模就成为确定编码器压缩效率的关键。算术编码非常依赖计算机的计算能力和存储能力。过去，这种依赖极大地限制了它的发展，在提出的最初几年，算术编码压缩算法只在极小的范围内有原型实现。随着计算机科学技术的发展，许多算术编码的实现在执行速度上已经能够被人们接受。如前面所说的那样，实现算术编码的核心问题在于如何获得正确的频率，以及如何高效地实现精确的乘法计算。

　　在算术编码高阶上下文模型的实现中，对内存的需求量是一个十分棘手的问题。因为我们必须保持对已出现的上下文的计数，而高阶上下文模型中可能出现的上下文种类又是如此之多，数据结构的设计将直接影响到算法实现的成功与否。

　　在 1 阶上下文模型中，使用数组来进行出现次数的统计是可行的，但对于 2 阶或 3 阶上下文模型，数组大小将依照指数规律增长，现有计算机的内存满足不了我们的要求。比较聪明的办法是采用树结构存储所有出现过的上下文。利用高阶上下文总是建立在低阶上下文的基础上这一规律，我们将 0 阶上下文表存储在数组中，每个数组元素包含了指向相应的 1 阶上下文表的指针，1 阶上下文表中又包含了指向 2 阶上下文表的指针……由此构成整个上下文树。树中只有出现过的上下文才拥有已分配的节点，没有出现过的上下文不必占用内存空间。在每个上下文表中，也无需保存所有 256 个字符的计数，只有在该上下文后面出现过的字符才拥有计数值。由此，我们可以最大限度地减少空间消耗。

第三章：简单实现

3.1、开发环境

　　操作系统：Windows XP，Windows 2000
　　应用软件：Visual C++6.0

3.2、Visual C++简介

　　本次毕业设计主要研究的是算术编码，其具体的算法是通过Visual C++编程来实现的。

　　在向对象的程序设计技术是当今全球程序员普遍采用的一种程序设计方法，是软件开发的最新潮流。在众多的开发工具中，Microsoft公司的Visual C++6.0独树一帜（1998年底，微软推出了其开发工具企业版套件Visual Studio6.0,Visual C++是其中之一），将面向对象的程序设计方法和可视化的软件开发环境完美地结合起来，合得开发Windows平台的应用程序更加方便，深入。Visual C++自诞生以来，一直是Windows环境下最主要的应用开发系统之一。Visual C++功能十分强大，支持面对对象编程技术，支持组件共享，不仅可以提高软件系统开发的速度，而且可以大大提高软件的质量。Visual C++不仅是C++语言的集成开发环境，而且与Win32紧密相连，所以，利用Visual C++开发系统可以完成各种各样的应用程序的开发，从底层软件直到上层直接面向用户的软件，而且， Visual C++强大的调试功能也为大型复杂软件的开发提空了有效的排错手段。Visual C++程序的执行速度以及对操作系统访问的权限之高，是其他许多语言无法比拟的，加上Windows操作系统的支持，就使得Visual C++的高级程序员对整个计算机的硬件系统和软件系统在各方面的访问和控制更加游刃有余。

　　进入20世纪90年代以来，随着多媒体技术和图形图像技术的不断发展，可视化（Visual）技术得到广泛的重视，越来越多的计算机专业人员和非专业人员都开始研究并应用可视化技术。所谓可视化技术，一般是指软件开发阶段的可视化和对计算机图形技术和方法的应用，它是当前发展迅速并引人注目的技术之一。它的特点是把原来抽象的数字，表格，功能逻辑等用直观的图形，图像表现出来。可视化编程是它的重要应用之一。所谓可视化编程，就是指在软件开发过程中，用直观的具有一定含义的图标按钮，图形化的对象取代原来手工的抽象的编辑，运行，浏览操作，软件开发过程中表现为鼠标操作和拖放图形化的对象以及指定对象的属性，行为的过程。这种可视化编程方法易学易用，提高了工作效率。

　　Visual C++是一个很好的可视化编程工具，使用Visual　C++环境来开发基于Windows的应用程序大大缩短了开发时间，而且它的界面更友好，给程序员提供了一个完整方便的开发界面和许多的辅助开发工具，便于程序员操作。在没有可视化开发工具之前，程序员要花几个月的时间来完成Windows程序的界面开发，而现在只需较少的时间就可以完成。

　　开发环境是程序员同Visual C++的交互界面，通过它程序员可以访问C++源代码编辑器,资源编辑器,使用内部调试器,还可以创建项目文件。

　　Visual C++不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点,而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2、Winsock网络、3D控制界面。由于Visual C++本身就是一个图形的开发界面，它提供了丰富的关于位图操作的函，对开发图像处理系统提供了极大的方便。

3.3、算术编码的实现

　　因为算术编码的动态编码即自适应编码比较复杂，所以在此我做的只是实现一个简单的静态模型。部分代码：

　　⑴以下为编码过程：

　　编码流程图如下：

　　以下为部分代码：

void compress()
{
int i;
char c;
SYMBOL s;
FILE *compressed_file;
FILE*source_file; 　　　//定义指针文件
source_file=fopen( "source.txt", "rb" ); //是以读的方式打开源文件
if ( source_file == NULL )
AfxMessageBox("Could not open source file", MB_OK);
compressed_file=fopen( "test.cmp", "wb" );
if ( compressed_file == NULL )
AfxMessageBox( "Could not open output file" );
initialize_output_bitstream(); //初始化输入文件
initialize_arithmetic_encoder();
while(!feof(source_file))
{
fread(&c, 1, 1, source_file);
convert_int_to_symbol( c, &s );//查出此字符对应的概率区间
encode_symbol( compressed_file, &s );编码
if ( c == '/0' )
break;
}
flush_arithmetic_encoder( compressed_file );//处理编码结束时的有效概率
flush_output_bitstream( compressed_file );//输出码流到文件中
fclose( compressed_file);
fclose(source_file);
}

　　下面为每次编码后，概率区间改变的处理过程：

range = (long) ( high-low ) + 1;
high = low + (unsigned short int )
(( range * s->high_count ) / s->scale - 1 );
low = low + (unsigned short int )
(( range * s->low_count ) / s->scale );
//重新为新的待编字符调节设定high,low

……
if ( ( high & 0x8000 ) == ( low & 0x8000 ) )//检查是否有可以输出的bit
{
output_bit( stream, high & 0x8000 );//输出最高位
while ( underflow_bits > 0 )//输出一些借位溢出的bit
{
output_bit( stream, ~high & 0x8000 );
underflow_bits--;
}
}
//把高位与1000（二进制码）比较，低位与1000比较，相同则输出，不同则返回

else if ( ( low & 0x4000 ) && !( high & 0x4000 ))//检查是否有可能溢出
{
underflow_bits += 1;
low &= 0x3fff;//消除可能溢出的第二位
high |= 0x4000;
}
else
return ;
low <<= 1;//低位补0
high <<= 1;
high |= 1;//高位补1
}

　　上边说明的是：把低位与0100，高位与0100比较，相同则输出，向前移位，后补一位；不同则返回。

void flush_arithmetic_encoder( FILE *stream )
{
output_bit( stream, low & 0x4000 );
underflow_bits++;
while ( underflow_bits-- > 0 )
output_bit( stream, ~low & 0x4000 );
}//连续地进行编码，当输入bit流为0时，

　　⑵以下为译码过程：

　　解码流程图如下：

　　以下为部分代码：

short int get_current_count( SYMBOL *s )
{
long range;
short int count;
range = (long) ( high - low ) + 1;
count = (short int)
((((long) ( code - low ) + 1 ) * s->scale-1 ) / range );
return( count );
}
//找到当前位置count，根据码表，找到当前对应的字符

void initialize_arithmetic_decoder( FILE *stream )
{
int i;
code = 0;
for ( i = 0 ; i < 16 ; i++ )
{
code <<= 1;
code += input_bit( stream );
}
low = 0;
high = 0xffff;
}

range = (long)( high - low ) + 1;
high = low + (unsigned short int)
(( range * s->high_count ) / s->scale - 1 );
low = low + (unsigned short int)
(( range * s->low_count ) / s->scale );
//重新定位high low

if ( ( high & 0x8000 ) == ( low & 0x8000 ) )
//将高位与1000比较，如果相同则溢出

else if ((low & 0x4000) == 0x4000 && (high & 0x4000) == 0 )
{
code ^= 0x4000;
low &= 0x3fff;
high |= 0x4000;
}//比较第二位，将编码与0100相比较，相同则溢出

else
return;
low <<= 1;
high <<= 1;
high |= 1;
code <<= 1;
code += input_bit( stream );
}//

第四章：结果分析

运行界面如图：

　　最下面为输入字符，中间为编译过程，最上面为译码结果，整个程序的运行过程是：输入一个文本文件，转为二进制码储存，然后利用算术编码的方法进行编码，最后再译码成字符格式。

第五章：总结

　　各种媒体信息（特别是图像和动态视频）数据量非常之大，算术编码作为一种高效的数据编码方法在文本，图像，音频等压缩中有广泛的应用。所以，研究算术编码有非常好的前景与实用价值。本次毕业设计课题名称为“算术编码原理分析与实现”，围绕这个中心，本文主要介绍了算术编码的基本原理，应用，算法的实现等等。用Visual C++程序实现算术编码的整个过程。

　　通过分析和事例可见，应用Visual C++程序对图像处理中的算术编码问题处理时，具有操作方便，处理速度快等特点。Visual C++程序的图像处理中经常用到的技术和方法在工具箱里都可以实现，所以，在对数字图像进行处理时，可以充分利用Visual C++程序的图像处理工具箱，使图像处理工作者可以从烦琐的编程工作中解脱出来。

　　算术编码对整条信息（无论有多么长），其输出仅仅是一个小数，而且是一个介于0和1之间的二进制小数。例如算术编码对某条信息的输出为1010001111，那么它表示小数0.1010001111,也即是十进制小数0.64。
在以上程序中，码表不是按实际情况制作，而是等间隔定义的，熵最大，则压缩率比较小，没能表现出算术编码压缩率比较大的优点。

参考文献

[1]张远夏，浅谈算术编码的编码译码过程，玉林师范学院学报，2003，4。
[2]林福宗，多媒体技术基础[M]，清华大学出版社，2000。
[3]陈明，多媒体技术基础[M]，中央广播电视大学出版社，2000。
[4]杨义先,林须端. 编码密码学. 北京:人民邮电出版社,1992。
[5]何兵,陈健，MPEG22AAC缩放因子的算术编码方法，上海交通大学学报，2002，5。
[6]方世强，李远青，胡刚，文本压缩技术综述，工业工程，2002年第2期。
[7]Davidlove,向极限挑战：算术编码，http://blog.csdn.net/davidlove/，2003年7月11日

致 谢 辞

　　经过将近三个月的时间，本次毕业设计的既定任务已基本完成。通过这次毕业设计，我除了深入地学到了更多相关的专业知识之外，更重要的是经历了毕业设计这个过程，熟悉了一般课题研究的整个过程，为今后更深入的学习和工作奠定坚实的基础。在这次课题研究及论文编写中，李中年老师给予了大量的建议及指导，提供了课题研究的方向及大量的参考资料和参考网站。在他的帮助下，课题的疑难问题能够得以成功解决，课题能够如期顺利地完成。同时，老师严谨的治学态度和实事求是的科研精神在课题研究中时刻影响着我，这将成为我们在以后学习工作中的榜样，激励着我们进步。

　　在此特别感谢老师的悉心指导！同时也衷心的感谢电信学院的领导给予我们学习上、生活上、思想上的引导和帮助。

　　感谢长江大学所有老师对我的教育和帮助。
　　感谢电信学院信工2001级的同学们，在学习和生活中对我的关心和帮助。
　　感谢含辛茹苦养育我的父母！
　　最后向所有关心和帮助过我的人们致以最衷心的感谢！

郑 岚
2005年6月