算术编码与哈夫曼编码

安徽大学本科毕业论文（设计、创作）题目哈夫曼编码与算术编码压缩效率比较学生姓名：李伟学号：E20714134院（系）：计算机科学与技术专业：软件工程入学时间：2007年9 月导师姓名：韩莉职称/学位:讲师/硕士导师所在单位：安徽大学计算机科学与技术学院完成时间：2011年5 月哈夫曼编码与算术编码压缩效率比较摘要算术编码和哈夫曼编码都利用信源符号的概率分布特性进行编码，使平均码长逼近信息熵是压缩编码算法的第一要求，算术编码比哈夫曼编码逼近信息熵的能力要强，但是编码效率和实现往往是一对矛盾，编码效率的提高，往往要在实现上付出代价，所以，选择压缩算要权衡这两点。本论文开篇先引入了信息论的一些概念，因为编码理论发源于信息论，是各种编码算法的数学基础。然后在第2章分析了算术编码原理，并从无限精度的算术编码原理过渡到在计算机上能够实现的二进制编码原理。在第3章紧接着介绍了哈夫曼编码原理，并讨论了怎样把信源符号映射为对应的码字，过程中用到的哈夫曼编码表是编码与解码的关键。在第4章对两者的编码效率作了比较，主要是结合信息论中的一些概念从微观上对两者逼近信息熵的能力作了比较，并在这章最后对两者在文本文件的压缩效果的表现上给出了一些实验结果。最后，在5章，主要是对前面内容做了些补充和总结。关键词：信息熵；算术编码；哈夫曼编码；编码效率ThecomparisonofHuffmanCodingandArithmeticCodinginFile

Compression

AbstractFulluseoftheprobabilitydistributionofsourcesymbolsisthefeatureofthearithmeticencodingandHuffmanencoding.Approachingtheaveragecodelengthtotheinformationentropycomefirstwhendesigningacompressionalgorithm.Tothecapacityofclosingtoinformationentropy,arithmeticencodingisstrongerthanHuffmanencoding.However,thecodingefficiencyandimplementationisoftenacontradiction:toimprovecodingefficiency,whichmeansthealgorithmimplementationprocessneedstopayahigherprice.Therefore,youneedtoweighbothwhenchoosingacompressionalgorithm.Inthebeginningofthisthesis,itfirstintroducedsomeoftheconceptsofinformationtheory.Becauseencodingalgorithmsarederivedfrominformationtheoryandinformationtheoryisthemathematicalfoundationofvariouscodingalgorithms.TheninChapter2,itintroducestheprincipleofarithmeticcoding.Forbettertounderstandthebinaryarithmeticcodingprinciple,itfirstintroducestheunlimitedprecisionarithmeticcoding.InChapter3,itdescribestheHuffmancodingtheory,anddiscusseshowtomapsourcesymboltothecorrespondingcodeword,amongwhichHuffmancodinganddecodingtableisthekey.InChapter4,thecodingefficiencyofthetwoalgorithmsiscompared.Mainlycomparethecapacitiestoapproximateinformationentropywithsomeoftheconceptsininformationtheory.Andthefinalpartinthischapter,someexperimentalresultsaregiventoshowthecompressioneffecttocompressatextfile.Finally,inChapter5,itgivessomeadditionsandsummary.Keywords:InformationEntropy;ArithmeticCoding;HuffmanCoding;CodingEfficiency目录引言„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„1数据压缩概念及技术分类„„„„„„„„„„„„„„„„„„„„1统计编码的数学准备„„„„„„„„„„„„„„„„„„„„„„2统计编码简介„„„„„„„„„„„„„„„„„„„„„„„„„5算术编码„„„„„„„„„„„„„„„„„„„„„„„„„„„„5算术编码简介„„„„„„„„„„„„„„„„„„„„„„„„„5无限精度的算术编码„„„„„„„„„„„„„„„„„„„„„„6二进制编码„„„„„„„„„„„„„„„„„„„„„„„„„„9二进制解码„„„„„„„„„„„„„„„„„„„„„„„„„„13哈夫曼编码„„„„„„„„„„„„„„„„„„„„„„„„„„„14哈夫曼编码简介„„„„„„„„„„„„„„„„„„„„„„„„14哈夫曼编码原理„„„„„„„„„„„„„„„„„„„„„„„„14哈夫曼解码原理„„„„„„„„„„„„„„„„„„„„„„„„16哈夫曼编码与解码系统模型„„„„„„„„„„„„„„„„„„„16哈夫曼编码形式不唯一„„„„„„„„„„„„„„„„„„„„„17算术编码与哈夫曼编码的比较„„„„„„„„„„„„„„„„„„„17两者编码效率的比较„„„„„„„„„„„„„„„„„„„„„„17两者压缩率的比较„„„„„„„„„„„„„„„„„„„„„„„19总结„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„20主要参考文献„„„„„„„„„„„„„„„„„„„„„„„„„„„22致谢„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„„231引言1.1数据压缩概念及技术分类数据压缩，就是将信息的一种表示方式转换为另一种表示方式，信息的新的表示方式与原有表示方式相比较所含的信息量相同或是在可以承受的范围内有所损失，但是新的表示方式所用到的符号数量要比原有表示方式要尽可能的少。数据压缩是必要的，不管是在生物系统中还是在人工系统中都存在数据压缩。尤其是处在这个信息爆炸的时代，怎样更有效的存储信息和传递信息对于文明进步的作用都是显而易见的。从不同视角看到的数据压缩的益处有：在通信信道上更快的传输信息，这就相应的减少了信道的占有时间，这可看作在时间上进行了压缩；在同一通信信道上并行的传输各种频率的互不干扰的信息，如xDSL技术在普通电话线上实现把低端频谱留给传统电话使用，把高端频谱留给上网用户使用，这可看作在频率域上进行了压缩；传输信号当然需要能量消耗，因此对数据进行压缩也就间接地减少了能量消耗，这可看作是在能量上进行了压缩；各种存储系统的存储空间都不是无限的，对数据进行压缩后，就可以在同样的存储空间存储更多的数据，这可看作是空间上的压缩。任何系统，尤其在活动时，都同时涉及到时间、空间和能量上的消耗，所以数据压缩就是从这三方面同时进行了压缩，这样就使得系统更加的有效的运行。既然数据压缩是必要的，那么就要考虑从哪些方面来说数据可以被压缩，一般可从以下几方面考察：一是，数据中通常存在着多余成分，即允余度。例如，存储在计算机上的一份文本文件，内容可假设是一部英文小说，可以想象，26个英文字母重复出现，各个字母出现的频率有大有小，而且不仅字母重复出现，字母组成的单词也重复出现，进一步，某些字母总是在某单词的一定位置上以高概率重复出现，某些单词也总是在一个特定句式的特定位置以高概率重复出现等等，计算机是以二进制形式存储文件的，那么用二进制符号怎样有效的表示这个由英文字符、各种标点符号和控制字符组成的文本文件就是怎样对数据进行压缩的问题，而压缩显然就要利用这些允余度的不同类型，例如，我们赋予高概率字符以相对少的二进制位数，赋予低概率字符以相对多的的二进制位数，那么这样表示后所得的总的二进制位数肯定比不考虑各个字符出现概率，而给不同字符按照ASCII码分配二进制位数所得的总的二进制位数要少很多。二是，数据中的各个部分前后之间总是存在着相关性。例如，电视上显示的动态画面，实际上是由离散的不同画面（帧）组成的，之所以看似是连续的只是因为帧的播放速度超过了人类的反应速度并且利用了人类的视觉暂留效应，但为使画面看似连续，不仅要利用人类本身的生物特性，还要保证帧之间的过渡是相对平滑的，也就是相邻两帧之间只有动态上的细微变化，而大部分画面在两帧之间是相同的，很显然，这种相关性是可以很好的加以利用的。三是，对于人而言，我们的感受器只能接受外界中很小一部分的信息。例如，人眼只能感受阳光中的可见光，而对紫外光不可见，但一些昆虫如蜜蜂却能感受紫外光，如果人为的屏蔽掉紫外光部分，对人眼而言，我们并不能对屏蔽前与屏蔽后的阳光加以区分，但蜜蜂就不同了，可能就因为无法感受紫外光，就找不到花蜜了，所以，对于人而言，并不是数据中所有的信息对我们都是必要的，不必要的部分就可以屏蔽掉。数据压缩可分为无损压缩和有损压缩，下面分别简要的介绍可逆压缩和不可逆压缩：可逆压缩，是利用数据的统计特性，即数据的允余度进行压缩的一类方法，允余度的去除或是减少并不影响原始数据无失真的恢复，即是一个可逆的过程。但从编码效率上来讲，可逆压缩受到待编码数据本身的信息熵的限制，无法达到更高的编码效率。也就是由于这样的限制，仅使用可逆压缩方法是不可能解决多媒体的存储和传输的所有问题的，因此，这类方法一般适用于在压缩过程中不允许有丝毫损失的情况，如在计算机磁盘上存储文件，数据通信等领域。常用的可逆压缩方法有：哈夫曼编码、算术编码、LZW编码等。不可逆压缩，是利用人类对图像或声波中的某些频率成分的不敏感特性，允许压缩过程中损失一定的信息，虽然不能完全恢复原始数据，但是所损失的部分对人类理解理解原始数据的影响可承受，好处就是与可逆压缩相比，能够获得更高的编码效率，因此，广泛适用与语音、图像和视频数据的压缩。不可逆压缩的方法有很多，这里不列举。统计编码的数学准备统计编码某种程度上与可逆压缩同义，因此可混用。在1.1节中，我们用到了允余度和信息熵的概念，这两个概念都由信息论的开创者香农(ClaudeE.shannon)首次提出，因此这一小节主要介绍信息论中的一些概念，这些概念有助于我们更好的理解统计编码。信源空间概念：X: a a a—a信源空间表示为：123mP(X):p(a)p(a)p(a)—123—p(a)m其中，0<p(a)<1(i=1,2,...,m) 区p(a)二1imi=1符号a代表信源可能发出的符号，p(a)发符号a的先验概率。i i i用信源空间表示信源X的必要前提，就是信源可能发出的各种不同符号的概率先验可知，或事先可测定，测定信源的概率空间是构建信源空间的关键。信源符号的自信息量：数学上定义为：I(a)=-logp(a) 说明：TOC\o"1-5"\h\zi r ia为信源所发符号，p(a)为信源发符号a的概率，概率越大，不确定性越i i i小，概率越小，不确定性越大。而自信息量I(a)既表示收信者确切无误收到信源符号a后，从a中获得的信i i i息量，同时也表示收到符号a之前，收信者对于信源所发符号a存在的不确ii定性的度量。自信息量I(a)的单位取决于对数的底，即r值，若r=2,则自信息量的单位i为比特(bit)，不指明正整数r具体值时,则自信息量的单位为r进制信息单位。信源的信息熵：数学上定义为：r进制形式H(X)= p(a)logp(a)TOC\o"1-5"\h\zr irii=12进制形式H(X)=-Sp(a)logp(a) 说明：2 i 2 ii=1⑴运用对数换底公式，可得：H(X)=H(X)logrr 2 2(2)信息熵作为信源X的总体信息测度，表示信源每发一个符号所能提供的平均信息量，同时也表示收信者在接收到符号之前，对信源X存在的平均不确定性的度量。最大离散熵定理：H(p,p,.,p)<H(p,p.p)1 2mmax1 2m其中，说明：H(p,p,…,p)=H(丄，丄，…,丄)=一区—log丄=logm

max1 2mmmm m2m2其中，说明：i=1(1)熵函数H(p,p，…,p)是信源X的信息熵的另一种表示方法，其中p.代表1 2m ip(a)。(2)熵函数具有上凸性，所以熵函数具有极大值，此极大值就是其最大值H，max最大值在pi=1/m时，即信源符号等概率分布时取得。离散信源信息熵的最大值只取决于信源的符号种类数m值，m值越大，其信息熵的最大值越大。信源X所含有的允余度：:=H(X)-H(X)=logm-H(X) 说明：max2信源符号等概率分布时，允余度匚二0,因此离散独立信源的允余度隐含在信源符号的非等概率分布之中。也就是说，只要信源符号不是等概率分布，就存在能够对信源数据进行数据压缩的可能性，允余度的存在是能够进行统计编码的前提。对信源编码所得平均码长：n=np(a)+np(a)H Fnp(a)=£np(a) 说明：1 1 2 2 mm iii=1n是信源符号a的码字长度。ii平均码长n是各个信源符号的码字长度ni在信源X的概率空间!p(a),p(a),•••,p(a)｝上的统计平均值。1 2 m编码效率：n=H(X”n 说明：n值越大，表示每一个码符号所携带的平均信息量越多，反之，就越少。对于给定的待编码信源，由于各个信源符号的概率已经经过统计确定，所以信源熵的值也就固定不变了，所以编码效率的高低只取决于平均码长n，所以提高信源编码的效率，就是要设法减小平均码长n。平均码长n存在下限：n>h(X) 说明：r⑴在证明过程中，得到：当且仅当对所有i(i=1,2,…,m)，都有p(a)=1rni时，in=H(X)才成立，其中n是信源符号a的码字长度。r i i(2)单义可译码的平均码长n，再小也不会小于信源熵。所以一旦信源确定，其信源熵也就随之确定，平均码长的下限值也随之确定，在这个范畴内编码效率不可能超过1(100%)，要想进一步提高编码效率，只有通过改变信源本身才能做到。1.3统计编码简介1.2节的内容是设计统计编码的理论基础，所以有了1.2节的介绍，统计编码这类方法就可简单表述为：利用信源符号的概率分布特性，寻找每个信源符号的出现概率与其码字长度之间的最优匹配，这种最优匹配就是要做到平均码长最小，也即平均码长要最大程度的趋近信息熵值。怎么利用信源符号的概率分布特性，来为每个信源符号分配码字，达到最大程度趋近信息熵值的目的在具体介绍哈夫曼编码和算术编码时会清楚地了解到。算术编码2.1算术编码简介很明显，各种统计编码都是变字长编码方法，但变字长的含义对于哈夫曼编码和算术编码是有些区别的，哈夫曼编码独立的为每个符号依据其概率大小分配相应长度的码字，码字长度都是整数个比特（bit）,而算术编码无需为一个符号设定一个码字，它直接对整个输入符号序列进行编码，并输出一个码字来代表整个符号序列，编码过程也自然是递推形式的和连续的，这样在衡量平均每个符号所对应的码字长度时，会知道码字长度都是以分数形式的比特（bit）来分配的，精确度可以很趋近于logp（a），这样算术编码与哈夫曼编码相比就能够更大程度地i趋近信源（整个符号序列）的信息熵。稍具体的来讲，算术编码不是将单个的信源符号映射成一个码字，而是将整个输入符号映射为左闭右开区间［0,1）内的一个子区间，这一子区间的宽度等于整个符号序列的概率（整个符号序列的概率又等于输入符号的概率之积），可以想象在编码过程中，每编码一个信源符号，都会相应得到新的区间，新的区间作为编码下一个信源符号所要待划分的区间，就这样一直对后续的符号依次编码，直到所有的符号被编码，即编码完毕，最后得到的区间内的任何一个小数都能代表整个符号序列，但一般选择一个容易变成二进制数字的小数作为实际的编码输出。上述阐述过程可能有点抽象，在2.2节将更加详细的加以说明。回顾算术编码的发展历程会发现，算术编码的发展不是一蹴而就的，其思想的源头可追溯到香农（shannon），再由P.Elias正式提出其完整思想（但还不实用），后来又由R.Pasco、J.Rissanen、G.G.Langdon和Written等人将其实用化，一直到算术编码家族中的一些成员成为如H.263视频压缩标准和JPEG2000图像压缩标

准的核心，共经历了约40多年的时间，直到现在算术编码的研究改进也没有停止。无限精度的算术编码由P.Elias正式提出的算术编码需要无限精度的浮点运算，随着符号序列的输入，计算精度将无限制的增加，相应的编码位数也无限制的增加，而这样的要求是在当前计算机上无法实现的。虽然如此，但无限精度的算术编码可用来更清楚地说明算术编码的基本原理，同时通向实用化的有限精度、不做乘法的二进制算术编码也是基于此而改进得到的。如果我们把编码过程中得到的每一区间的下限作为码字，并用C表示，区间大小用A表示，那么算术编码原理可表述如下：设输入符号序列s设输入符号序列s取自信源空间X: aaa a123mP(X):p(a)p(a)p(a) p(a)123m后接符号a(aeX)，那么就扩展为符号序列sa，空符号序列记作Q，只有一个iii符号a的序列就是0a，那么算术编码的两个迭代关系可表示为：ii码字更新：C(sa)=C(s)+P(a)xA(s)ii区间更新：A(sa)=p(a)xA(s)ii其中P(a)=p(a)+p(a)+…+p(a)被称为符号a的累积概率。i 1 2 i-1 i如果初始区间为实数区间［0,1),那么初始条件为：C(0)=0,A(0)=1和P(0)=0,p(0)=1。可见，在编码任何符号之前，初始区间为lc(0),C(0)+A(0))=b,l),从上述描述的迭代关系可看出每次编码符号a，区间宽度都依据符号a的出现概率而变ii窄，随着编码的符号序列越来越长，相应的区间宽度也随之变得越来越窄，那么表示区间所需的数字位数也会越来越多，而且，我们还会发现，大概率符号比小概率符号使区间变窄的幅度要小，所增加的数字位数也较之更少，这是符合统计编码原理的。下面的实例追踪这一编码过程，有助于我们理解算术编码工作的细节。实例1：设待编码符号来自信源空间：X:a bcde!实例1：设待编码符号来自信源空间：p(X):0.20.10.10.30.20.1符号!作为结束符，作为编码和解码结束的标识，就像中文中句号的作用，若待编码的符号串为一英文单词“dead!”，当然编码和解码过程都是从初始区间（0,1）开始的。注意:上述信源X的各符号的概率值来自某一统计模型，统计模型得到的各符号的概率值独立于特编码的符号串中各符号的概率值，是大量统计的产物，能比较真实的预测一个字符在待编码的整个符号序列中的概率值，例如一本英文小说中各字符的概率值是确定的，但是在编码时可能不允许事先统计其符号概率分布，但是我们事先经过某些方法统计过大量其他英文小说的字符概率分布，那么就用之前已知的字符概率分布来预测未知待编码字符串的字符概率分布。如果让aaaaaa分别依次对应abcde!,那么就能用算术编码原理中介绍123456的两个迭代关系实现算术编码。开始时得到一张表，反映了开始时各个字符的累积概率和区间划分情况：下标F宇符込槪率贸Q累執规率P匹）区间范国1aQ200[0.0,0.2)2b0102[0.2,0.3)3c0103[03,04)4d0304[0电0刀Q020.7[0.7,0.9)610109[09,1.0)表1：信源X中字符的分布概率、累积分布概率和初始区间划分情况好，现在开始编码：编码第1个字符d:C(0d)二C(0)+P(d)xA(0)二0+0.4x1.0二0.4A(ed)二p(d)xA(e)二0.3x1.0二0.3区间范围由[0,1)更新为\c(Qd),C(Qd)+A(Qd))=b.4,0.7)；编码第2个字符e:C(Qde)二C(Qd)+P(e)xA(Qd)二0.4+0.7x0.3二0.61A(Qde)二p(e)xA(Qd)二0.2x0.3二0.06区间由b.4,0.7)更新为lc(Qde),C(Qde)+A(Qde))=b.61,0.67)；编码第3个字符a:过程类似；编码第4个字符d:过程类似；编码第5个字符!:C(Qdead!)二C(Qdead)+P(!)xA(Qdead)二0.6148+0.9x0.0036二0.61804A(Qdead!)二p(!)xA(Qdead)二0.1x0.0036二0.00036至此，所有字符都已编码，最后得到的区间为：Ic(Qdead!),C(Qdead!)+A(Qdead!))=b.61804,0.61840)。然后从此区间内选择一个数位较短的实数作为最后的码字输出给解码器上述编码过程如图1所示：解码原理可以看作是编码原理的逆过程，解码器开始也按照编码时各个字符的概率分布(来自统计模型)对初始区间〔0,1)进行划分，然后解码器把从编码器接收到的码字与各字符相对应的概率区间作比较，比较的意思是说看码字属于哪个字符对应的概率区间，比如选择编码得到的最后区间的左端点实数0.61804作为码字，解码器就会发现码字0.61804属于字符d所对应的概率区间〔0.4,0.7)，然后就解码出第一个字符d,为了避免一次又一次的为字符分配区间，减少计算量，在解码出第一个字符后，比如解码出字符d后，按照表1就把区间更新为d所对应的区间［0.4,0.7)，区间大小A=0.3,然后开始解码下一个字符，用原码字0.61804减去字符d对应区间的左端点值L=0.4,得到的值再除以d对应区间的大小A=0.3即计算式：(0.61804-L)A二(0.61804-0.4”0.3二0.7268，然后把0.7268作为新的码字，通过查找表1发现0.7268属于字符e对应的区间［0.7,0.9)，这就解码出第二个字符e,并把e对应的区间［0.7,0.9)作为新区间，左端点L=0.7，区间大小A=0.2，不断重复上述过程，直到解码出结束符!，解码过程宣告完毕。需要说明的是作为结束符的!是不可见的，严格说并不属于被编码字符串，是人为附加上去的，作用只是为了在解码器解码出全部字符之后作为标识来停止解码器的运行，如果没有结束符，解码器将无法判断何时结束解码。2.3二进制编码上节无限精度的算术编码理论由于当前计算机基于二进制的设计而无法直接编程实现，而计算机能做到的就是对无限精度的实数进行近似模拟，这种近似对大量数据的压缩效果的影响很小，而算术编码在理论上能够很大程度上趋近信息熵的优越性使得其有很大的现实意义。通过上节可知，算术编码每次编码和解码都要做乘法，而且必须在规定的时间内完成(信源符号周期限制)，有时就难以实现，但若被编码对象本身或是被映射成二元序列(如01符号序列)，且其符号概率较小者(用L表示)的概率为p(L)=2-q，其中Q为整数，则上节介绍的无限精度的算术编码原理的两个迭代关系就可以在计算机上用移位和单纯的加减运算来实现，从而避免乘法。另外，随着输入符号序列s长度的增长，码字C(s)的数位也随之相应增加，而这样精度的码字在计算机上是无法表示的(寄存器位数有限)，这就要求将寄存器中存储的已编码的码字高位及时输出。而当寄存器中为输出部分高位均为1时，则低位运算略有增加，就可能进位到已输出部分，特别是当这种连续的1很长时。这一问题就是有限精度算术编码所固有的进位问题。JRissanen和G.G.Langdon利用插入一个额外的0(即填充位)来隔断进位的扩展，这会对编码略有影响，但由于影响很小，所以下面仍用填充位来隔断进位的扩展。类似码字的情况，区间大小A(s)也只能基于有限位数的寄存器来实现更新。有限精度的算术编码原理所用到的迭代关系与上节介绍的相同，但由于这次的编码对象是二进制序列，并且用2-q来估计小概率符号的出现概率，所以能够进一步得到如下迭代关系：设待编码符号来自符号集扫,厶｝,并且若p(L)=2-q，那么p(H)=1-p(L)=1-2-Q；而人为让P(H)=0，那么P(L)=p(H)=1-2-Q。上述对初始区间〔0,1)的最初划分情况可用下图表示：H L0 1-严 1.0图2：大概率符号H与小概率符号L在初始区间中的分布情况从而，有限精度、不作乘法且将设变量Q已经估计出的二进制算术编码顺序步骤如下：1.初始化步骤：C他)=0.00…0,A(©)=0.11…1，C和A小数点后的位数由参数q确定。2•对区间宽度A(s)更新：当编码小概率符号L时：A(sL)=p(L)x2-Q(相当于A(s)右移Q位)当编码大概率符号H时：A(sH)=p(H)xA(s)=(1-2-q)xA(s)=A(s)-A(s)x2-q=A(s)-A(sL)3•对码字C(s)更新：当编码大概率符号H时：C(sH)=C(s)+P(H)xA(s)=C(s)当编码小概率符号L时：C(sL)=C(s)+P(L)xA(s)=C(s)+(1-2-q)xA(s)=C(s)+A(sH)4•如果发现A(s)<0.10…0，则A(s)重复左移，直到A(s)>0.10…0为止，而若A(s)左移，那么C(s)也需要左移同样位数。如果紧靠码字C(s)的小数点前有连续v个1,则紧靠小数点前的位置插入一填充位0，来隔断进位扩展。按上述步骤对字符序列中的所有字符进行上述处理过程，编码完毕后输出最后的码字C(s)。步骤1中初始区间宽度在多大程度上趋近于1取决于参数q，而参数q值大小又一般依据p(L)而定，而p(L)是统计模型对下一位是小概率符号L可能出现的概率预测，例如如果有p(L)的最小值为2-15，那么参数q值就一般取16。如果没有步骤4，那么区间A当缩小到很小时，就必须用很高的精度才能把它和0区分开来，而步骤4的作用就是，当发现区间小到某一程度时，就将区间左移若干位，直到区间大于某种程度，而区间A加倍后，码字C也须随之加倍。实例2：编码二元符号串“01000101”，统计出大概率符号H是‘0'，小概率符号是‘1'，某一统计模型提供的对这个长度为8的字符串各个位置出现小概率符号L的概率预测分别为2-2,2-1,2-2,2-2,2-3,2-1,2-2,2-2，最大的Q值为3，那么就取q=4,v=3。现在对其进行编码：编码第1个符号‘0'统计模型预测p(1)=2-2A(Q1)=A(e)xp⑴=0.1111x2-2=0.0011A(©0)=A(©)xp(0)=A®)—A(©1)=0.1111-0.0011=0.1100C(00)=C(0)=0.0000编码第2个符号‘1'统计模型预测p(1)=2-1A(01)=A(0)xp⑴=0.1100x2-i=0.0110A(00)=A(0)-A(01)=0.1100-0.0110=0.0110C(01)=C(0)+A(00)=0.0000+0.0110=0.0110此时，由于C(01)<0.1000,因此A(01)与C(01)须左移1位，得：A(01)=0.1100，C(01)=0.1100编码第3个符号‘0'：过程类似，得到：A(010)=0.1001,C(010)=0.1100编码第4个符号‘0'：过程类似，得到：A(0100)=0.1110,C(0100)=1.1000编码第5个符号‘0'：过程类似，得到：A(01000)=0.1101,C(01000)=1.1000编码第6个符号‘1'：过程类似，得到：A(010001)=0.1100,C(010001)=11.1110编码第7个符号‘0'统计模型预测p(1)=2-2此次遇到了新的情况，下面是完整的过程：A(0100011)=A(010001)xp⑴=0.1100x2-2=0.0011A(0100010)=A(010001)-A(0100011)=0.1100-0.0011=0.0110C(0100010)=C(010001)=11.1110此时，由于A(0100010)<0.1000，因此A(0100010)与C(0100010)须左移1位，得:A(01000010)=0.1100，C(0100010)=111.1100此时又发现，C(0100010)紧靠小数点前有v=3个连续1,因此还需在C(0100010)紧靠其小数点前插入一填充位0，那么C(0100010)=1110.1100编码最后一个符号‘1'统计模型预测p(1)=2-2A(01000101)=A(0100010)xp⑴=0.1100x2-2=0.0011A(01000100)=A(0100010)-A(01000101)=0.1100-0.0011=0.1001C(01000101)=C(0100010)+A(01000100)=1110.1100+0.1001=1111.0101此时，由于A(01000101)v0.1000,因此，须将A(01000101)和C(01000101)左移两位，得：A(01000101)=0.1100，C(01000101)=111101.0100上述编码过程如图所示：

11000111110符号0A和C顷左移2IV.得:111101.01000.00000.01100.11000.11000.1100111110111110011000111110符号0A和C顷左移2IV.得:111101.01000.00000.01100.11000.11000.110011111011111001110.1100111101010.0000+0.1100.,A和O：：贝左移一应，得:0.1100+0.1100A和C须左移1位，得:图3：编码“01000101”过程注：上图中的箭头是为了更清楚的表明左移的过程，每一区间只标明了两端点的值，右端点由码字C和区间A的和组成，在图的最右部分标明的符号是为了说明各个符号所最终对应的区间。此时，编码就宣告结束了，编码器最后一项工作就是从最后得到的区间中选择一个代表性的二进制小数作为码字输出，最后得到的区间为：[C(01000101),C(01000101)+A(01000101))=[111101.0100,111110.0000)回想在编码过程中共做了5次左移处理(在图3中用箭头标识)，码字C和区间A共左移(1+1+1+1+2)=6比特位，因此，要考虑码字C和区间A实际的小数点位置，须将代表区间的数值右移6位，那么，最后得到的区间就变为[0.1111010100,0.1111100000)，此区间信息可作为编码输出信息给解码器，但是只要从此区间内选择一个位数比较短的值并且省略掉小数点和小数点前的0作为输出码字就可以，例如将1111011作为最后的码字输出。这个最终码字的码字长度有7位，比用ASCII表示的被编码二元字符串的长度要小很多。2.4二进制解码二进制解码是二进制编码的逆过程。解码器从编码器接收到的码字，去掉了小数点和小数点之前的0，并且这个码字中可能还包括填充位，如果有填充位的话，在开始解码前还要除去填充位的影响，回想，在二进制编码步骤5中，如果发现码字C的小数点前有v个连续1，那么就在紧靠小数点前插入填充位0，那么，解码时，当发现码字整数部分的高位有v个连续1，就要检测第v+1位，第v+1为可能为0可能为1，0的情况说明当编码计算码字时，没有向第v+1位有进位，1的情况说明编码计算码字时，有向第v+1位有进位，使得填充位位置的0变为了1，所以解码前去掉填充的影响要分别考虑这两种情况。解码器也从区间大小为A(s)=0.11…1的区间作为开始解码的初始区间，女口果当前未解码字符表示为X,在字符x之前已经被解码的字符串表示为s，，有了以上讨论和假设，二进制解码步骤可表述如下：1初始化区间：A(s')=0.11…1解码器检测码字C的高位部分的v位的二进制位值：如果发现v位二进制位都是1，那么接着检测第v+1位即填充位的值：若第v+1位为0，说明没有向第v+1位进位，填充位的位置还是0，那么就直接去掉第v+1位的0，即除去了填充位的影响。若第v+1位为1，说明又向第v+1位进位，填充位位置的0由于进位的影响由0变为了1，那么去掉此位后，由于后面有进位，还要对码字进行加1处理，加1的位置是第v位。子区间宽度A更新：对小概率符号L：A(sZ)=A(sr)x2-q对大概率符号H：A(s'H)=A(s')-A(sZ)判断解码字符：如果C(s)<A(s'H):则解码出字符为H,并置A(s')=A(s'H)如果C(s)>A(s'H):则解码出字符为L,并置C(s)=C(s)-A(s'H),A(s')=A(s'L)5如果A(sx)v0.10・・・0,则A与C重复左移，直到A(sx)>0.10…0回到步骤2，接着解码下一个字符，直到解码出所有字符。哈夫曼编码哈夫曼编码简介哈夫曼编码是一种变字长编码方法，对出现概率较大的信源符号赋予较短的码字，对出现概率较小的信源符号赋予较长的码字，但哈夫曼编码被称为最佳码并不仅仅如此，重要的是按照什么方法去为信源符号分配码字，哈夫曼编码通过构造哈夫曼编码表来达到最佳性，哈夫曼编码对信源符号进行编码，能够保证各码字的码长严格按照所对应的信源符号的出现概率大小逆序排列，使得在变字长分组码范畴内，使其得到的平均码长最小。哈夫曼编码原理因为信源多种多样，那么不妨在编码时把普通的计算机文件作为信源，如一个文本文件且此文本文件中字符由ASCII码表示，那么此种文件都是由一个个的字节组成，每字节都是一个字符，当然每个字符的ASCII码表示都是8位，共256种，因此，这样的文件最多含有256种字符。这样，文件中的所包含的字符都可看作一个信源符号。哈夫曼编码事先要统计文件中各个字符的出现概率，如果文件允许编码器统计字符，那么通过统计文件中包含的总字符数和每种字符在文件中出现的次数，就很容易计算得到每种字符在文件中出现的概率。构造一个文件的哈夫曼编码表是文件编码与解码的关键。设某个文件中含有q种字符：s,s,s,…,s，并且统计出每种字符在文件中123q的出现概率分别为：p(s),p(s),p(s),…,p(s)，则编码的具体步骤为：123q将q个信源符号s,s,s，…,s，按其概率分布p(s),p(s),p(s)，…,p(s)的大123q123q小，以递减次序，由大到小进行排序。用字符‘0'和‘1'分别代表概率最小的两个信源符号，并把这两个概率最小的信源符号的概率相加，所得的概率和值用一个虚拟信源符号代表，与余下的(q-2)个信源符号组成含有(q-1)个信源符号的新信源，称作第一次缩减信源X。1把缩减信源X中的符号仍按照相应概率大小以递减次序进行排列，再将其中1两个概率最小的信源符号分别用‘0'和‘1'表示，并把这两个符号的概率相加，所得的概率和值用另一个虚拟信源符号代表，这样又形成了含有(q-2)个信源符号的第二次缩减信源X。2按照上述步骤，依次继续下去，直到信源中只剩下两个信源符号为止，将这最后两个信源符号分别用‘0'和‘1'表示，这两个信源符号的概率之和必定等于1，也用一虚拟信源符号代表。然后从最后得到的概率为1的信源符号开始，进行回推，把回推过程中所遇到的‘0'和‘1'按先后顺序排列成字符串，这样的字符串对应着各个不同字符，因为这样的‘0'和‘1'组成的字符串并不是计算机中的二进制，所以不妨称为伪码字。上述编码过程，就是为文件中的字符建立了一一映射的关系f:sTc,i=1,2,……，q，其中s代表不同的字符，c代表对应字符s的伪码字。iiiii为了将伪码字替换为真正的码字，还必须建立一个映射关系 g:cTw，iii=1,2,……,q,其中c与映射关系f中同义，w代表对应字符的码字。映射gii的作用就是将由字符串组成的伪码字替换成码字，从而通过映射g(f(s))=w，ii建立了哈夫曼编码表。下面具体说明一下怎样把伪码字替换为码字，在此用一种间接的方法解决这个问题，具体做法为：将源文件中每个字符通过查找哈夫曼编码表的办法用伪码字作替换，将替换的结果保存在一个临时文件temporary.txt中，临时文件temporary.txt就是一个由字符‘0'和‘1'组成的字符串。一般来说，这个临时文件要比原文件大得多，比如，原文件中的字符‘a'用伪码字“001110010”替换，前者只占一个字节，而后者最少占10个字节，临时文件当然不是最终得到的压缩文件，只是为了便于实现压缩与解压。接下来是将临时文件temporary.txt变为由码字组成的文件。方法是，相当于建立一个映射关系h:strTd，i=1,2，……，256，其中str是由字符‘0'和iii‘1'组成的字符数为8的字符串，d是介于0和266之间的整数。临时文件从结构上说是由不等长的伪码字组成的，由伪码字映射后的码字也是不等长的，而计算机中的存储单位一般都是单字节的倍数，如字节，双字节，四字节，因此很难用一个准确的存储空间单位来存储码字，如果空间太大，对码字长度短的码字来说是一种空间浪费，而空间太小，对码字长度长的码字来说又无法存放，因此，为了压缩与解压的方便，不如将temporary.txt进行等长划分，使得连续的8个字符为一组，组成str，用一整数d做替换，替换的ii结果是得到由整数d即二进制组成的压缩文件。i上述码字替换伪码字的过程，可能会出现最后一组‘0'和‘1'组成的字

符串不足8个字符，那么就保持不变，不做替换，附加到压缩文件中。3.3哈夫曼解码原理哈夫曼解码过程是文件编码过程的逆过程，由于哈夫曼编码可即时解码，因此只要得到一个码字w,则通过查找哈夫曼编码表得到相应的字符，映射过程是i编码时映射的逆过程：f-1(g-1(W))。因此，每从压缩文件中读出一个码字，就i从通过查找哈夫曼编码表用字符替换相应的码字，当压缩文件中所有的码字被字符替换掉，也就宣告解压过程完成了。虽然解压是压缩的逆过程，但是还不能直接通过对哈夫曼编码表反向查找将压缩文件解压。首先，在压缩文件中除了最后字符数不满8的字符串作为附加数据没有压缩外，其他的每个字节都对应着一个长度为8的字符串。因此，通过映射h的逆映射h-1将压缩文件中的整数替换为8位字符串str，全部替换完毕后不i要忘了将没有压缩的字符串附加到临时文件temporary.txt中去，这样就得到了完整的临时文件temporary.txt。由于临时文件是由伪码字组成的，通过映射f的逆映射f-i：cTs，实现用字符s替换伪码字c，全部都替换完毕后，就实现了解iiii压。3.4哈夫曼编码与解码系统模型有了上述讨论，哈夫曼编码与解码系统模型可以简单如图所示：图4：哈夫曼编码系解码系统模型哈夫曼编码形式不唯一按照哈夫曼编码原理构造的哈夫曼编码表不唯一，这主要由于两个原因，一是在为两个最小概率的信源符号指定字符‘0'和‘1'的的顺序上不唯一。二是对信源符号按概率大小递减排序时，所得到的形式也不唯一，这是由于可能有出现概率相等的信源符号，对于两个和两个以上概率相等的信源符号排序的结果显然是不唯一的虽然哈夫曼编码形式不唯一，但是各种编码形式所得到的平均码长被证明是大小相同的，所以并不影响压缩效果。算术编码与哈夫曼编码的比较4.1两者编码效率的比较统计编码，利用信源符号的概率分布特性，寻找每个信源符号的出现概率与其码长之间的最优匹配，这种最优匹配是要做到平均码长最小，也就是说要使平均码长最大程度的趋近信息熵值。哈夫曼编码和算术编码都属于统计编码，因此，两者的编码方法自然具有统计编码的特性，但从理论上就能说明很多情况中算术编码比哈夫曼编码编码效率要高，所以两者编码效率的不同原因就在于“最优匹配”的方法不同，结果就造成两者各自使其平均码长趋近信息熵值的程度不同。在1.2节统计编码的数学准备中，有自信息量的概念，定义为：I(a)=-logp(a),其含义不赘述，统计编码就是要做到为信源符号a分配的码i2ii字的码字长度要趋近或等于信源中该字符的自信息量I(a)，如果每个信源符号i的码字都能符合这个要求，那么平均码长就能很好的趋近甚至等于信息熵值，这样编码效率就能接近甚至等于100%。自信息量可以作为信源中某个字符编码效率的衡量指标。例如，信源中某符号a的出现概率为p(a)=0.8，那么其自信息ii量I(a)=-log0.8=0.322(bit),这说明若要使符号a的编码效率达到100%，那i2i么只需要为其分配长度为0.322bit的码字，但哈夫曼编码只能为此符号分配长度为1bit的0或1，几乎是理想码字长度的3倍，编码效率很低。可以把自信息量看作自变量为p(a)的函数，称作自信息量函数，不难发现，自信息量函数i是个单调递减函数，p(a)越大，I(a)就越小，也就是说当某个符号的概率接近ii于1时，自信息量函数至接近0，那么哈夫曼编码的效率将降到最低。哈夫曼编码虽然能够保证各码字的码长严格按照所对应的信源符号的出现概率大小逆序排列，但由于码字长度都是整数个比特(bit),对某个符号而言，哈夫曼编码只能以整数个比特(bit)趋近其自信息量，对所有信源符号而言，哈夫曼编码只能以整数个比特(bit)趋近信息熵，这样的性质，限制了哈夫曼编码趋近信息熵的能力。虽然，从上述的例子中哈夫曼的编码效率很低，但是对于实际的文本文件，不可能有哪个字符达到0.8这么大的出现概率，一般，信源符号的出现概率都很低，因为实际的文件中字符数很多，因此用哈夫曼编码实际文件，是能够获得可观的压缩效率的。在1.2节统计编码的理论基础中，平均码长等于下限信息熵的条件是：当且仅当对所有信源符号a，都有p(a)二1/2ni，其中n是信源符号a的码字长度。i i i i就是说各信源符号的出现概率与1/2ni相比有较明显的出入时，哈夫曼编码不能很好的趋近信息熵。这个定理与上面用自信息量I(a)来讨论编码效率，本质上i是相同的。当信源所含有的允余度比较小时，也就是说，信源符号的概率分布比较接近等概率分布式时，用哈夫曼编码方法就更加不能得到可观的编码效率，因为此时对信源符号进行哈夫曼编码，得到的各符号对应的码字将接近等长码，如，对本来就用等长的ASCII编码的文本文件，当文件内符号概率分布接近等概率分布时，就根本起不到多少压缩效果。算术编码可以克服哈夫曼编码的上述缺点，原因在于算术编码跳出了分组编码的范畴，它只输出一个代表整个符号序列的码字，并且该码字长度是精确地与整个符号序列的概率大小相对应的。虽然算术编码没有一个符号对应一个码字的概念，但平均码长的概念是可用的，可以用代表整个符号序列的码字的长度除以符号总数作为平均码长，这样一来，可以说用平均码长来衡量平均意义上的每个符号所对应的码字长度。但每种符号的概率大小不同，对平均码长的贡献是不同的，算术编码也像哈夫曼编码一样，概率大的符号对平均码长的贡献相对小，概率小的符号对平均码长的贡献相对大，但关键一点是，某符号a对平均码长的贡i献很接近-p(a)logp(a)，因为是按分数比特接近的。算术编码得到的平均码长ii可以按分数比特(bit)趋近信息熵，这就突破了哈夫曼编码以整数比特(bit)趋近信息熵的限制。回想，在2.2节无限精度的算术编码原理和2.3节二进制编码原理中，在进行算术编码之前，都对信源符号的概率作了预测，比如，在2.2节无限精度的算术编码原理讨论中的实例1，对可能出现的各个字符都作了概率预测，并按照这个概率估计值为不同字符分配相应区间，而且在接下来的区间划分中也保持各个字符被分配的区间比例不变，就是说一直都是用这个概率预测值作为分配区间的依据，可以想象，对信源符号的概率预测值，必定不同于被编码信源符号的出现概率，但是采用这种模式进行编码就好像忽略掉了实际的符号出现概率，再结合算术编码原理，大概率符号比小概率符号使区间缩窄的范围要小，所增加的编码位数就更少，所以如何预测各符号的出现概率，作为分配区间的依据，直接影响到算术编码的编码效率。如果概率预测值与实际符号出现概率偏差很大，编码效率将受到很大影响，相比哈夫曼编码也将没有了优势，甚至不如哈夫曼编码。介绍2.3节二进制编码原理中，对小概率符号L作了概率预测，并2-q表示，其中Q是整数，那么对小概率符号L作概率预测就是确定整数Q值，如果Q值能够让2-Q与小概率符号的出现概率p相等，那么编码效率就是100%。确定Q值是保证算术编码编码效率的关键，使大部分小概率符号L的出现概率等于2-q，那么平均码长将很好的趋近信息熵。两者压缩率的比较4.1节两者编码效率的比较中的“编码效率”是基于1.2节编码效率的定义：耳二H(Xn，即编码效率为信息熵与平均码长之比，为了在宏观上衡量文件的压缩效果，引入“压缩率”的概念，压缩率等于压缩前后文件大小之差与压缩前文件大小之比，那么，编码效率越高，压缩率就越大，所以压缩率越大越好。用完全由ASCII编码的txt文件为例，并理想化的把它作为离散无记忆信源处理，编码三个主要由小写英文字母组成的英文名著txt文件得到：哈夫曼编码源文件容压縮前担(Byte)压縮后大小(Byte)压縮率a.txt2204080123