信息论 第5章(基于字典编码和算术编码)

信息论基础TheBasisofInformationTheory主题No5：基于字典编码和算术编码基于字典编码概论哈夫曼编码和游程编码得到的结果是变长码，而基于字典的编码方法得到的结果是定长码，特别适合计算机文件的压缩和保存。此类压缩编码方法是两位以色列研究人员在1977年提出来的，由于他们的名字分别为AbrahamLempel和JakobZiv，所以基于字典的压缩编码方法简称为LZ算法。Lz算法基本原理只要知道某个“单词”在字典中的位置(即序号),就可以知道这个“单词”的内容,“单词”的序号和“单词”的内容存在一一对应的关系.我们将计算机文件按“单词”进行分割,然后用“单词”在字典中的序号取代“单词”的内容,就可以得到全部由序号组成的编码结果.计算机文件是以字节为单位组成的,每个字节的取值从0到255(28＝256).把每个字节都看成一个“字符”,我们再把连续的若干个“字符”看成一个“单词”将全部“单词”组合起来就成为“字典”.由于字典的容量有限,不可能包罗万象.故在LZ压缩算法中,字典的内容直接由被压缩的文件生成.一边编码,一边将新发现的“单词”增加到字典中.在解码的过程中,同样是一边解码,一边生成字典.故LZ编码算法在储存压缩文件时不需要保存字典,是一种自适应算法.通常序号的长度为12比特,即0到4095,而“单词”的平均长度远大于12比特,从而达到压缩的效果.从而达到压缩目的.1984年,TerryWelch对LZ算法进行改进,使得所以的单词有同样的结构,推出LZW压缩编码算法.LZW编码算法LZW压缩编码算法如下：(1)字典初始化:将被压缩文件中所有使用到的单字节字符放入字典中.为了压缩任何类型的文件,可以将字典前256个位置分配给计算机文件中出现的所有256个可能的单个字符.(2)动态数据初始化:初始化新单词存放位置指针P,将它指向字典的第一个空位置;读入被压缩文件的第一个字符cha,作为待处理单词W.单词的前缀为空,即Q=4095,尾字符就是cha,码字N也是cha.(3)如果文件中再没字符,输出当前单词W的序号,编码过程完备.如果文件中还有字符,把当前单词W作为前缀,再从被压缩文件中读入一个字符CH,把CH作为尾字符,得到一个单词W1.(4)在字典中查找,如果字典中已经有W1,则更新当前单词,将W1看作当前单词W,返回第(3)步;如果字典中没有W1,先将原单词W的序号输出,再将新单词W1增加到字典中,然后把刚刚读入的字符CH作为当前单词W,返回第(3)步.LZW编码算法的例子ABCABDABCAAAABBBABACBCA例1设有一文件内容为用LZW算法，具体编码过程如下表.步骤当前单词读入字符查找对象查找结果编码输出字典扩充前缀尾字符码字内容码字位置新单词0A1FFFA041BAB无A041100AB2FFFB042CBC无B042101BC3FFFC043ACA无C043102CA4FFFA041BAB1005041B100DABD无AB100103ABD6FFFD044ADA无D044104DA7FFFA041BAB1008041B100CABC无AB100105ABC9FFFC043ACA10210043A102ACAA无CA102106CAA11FFFA041AAA无A041107AA步骤当前单词读入字符查找对象查找结果编码输出字典扩充前缀尾字符码字内容码字位置新单词12FFFA041AAA10713041A107BAAB无AA107108AAB14FFFB042BBB无B042109BB15FFFB042BBB10916042B109ABBA无BB10910ABBA17FFFA041BAB10018041B100CABC10519100C105AABCA无ABC10510BABCA20FFFA041BAB10021041B100CABC10522100C105AABCA10B23105A10B无ABCA10BLZW解码算法(1)字典初始化:将字典的前256给位置分配给256个单字节字符.(2)动态数据初始化:初始化新单词存放位置指针P,将它指向字典的第一个空位置;读入压缩文件的第一个码字,由于第一个码字必定是一个单字符,可以从初始字典中查表得到,译码输出,并记忆它的码字N.(4)如果读入的码字是无效码字(FFF),则解码结束,否则继续.(3)如果压缩文件没有码字,则解码结束,否则继续.(5)如果在字典有码字对应的单词,则采用递归算法,输出该单词的内容.并将该单词的第一个字符作为尾字符,将已经记忆的前一个码字作为前缀,组成一个新的单词,写入字典,然后记下当前码字,返回第(3)步;否则先在字典生成新的单词,再输出这个单词,将新单词的码字记忆下,再返回第(3)步.LZW解码算法的例子接着上面例1编码后的解码,在实际解码过程中,每次读入三个字节,分解为两个码字.假设有一个压缩文件,其内容为:04104204310010204110704210910510BFFF步骤读入码字记忆码字解码输出字典位置新单词0041A

1042041B100AB2043042C101BC3100043AB102CA4044100D103ABD5100044AB104DA6102100CA105ABC7041102A106CAA8107041AA107AA9042107B108AAB10109042BB109BB11105109ABC10ABBA1210B105ABCA10BABCA13FFF算术编码的思想假设某离散独立信源有n个消息:x1,…,xn,且对应的概率分别为:p(x1),…,p(xn).如果将这些概率用线段的长度来表示,则概率大的消息对应长的线段,概率小的消息对应短的线段.再将这些线段顺序连接起来,其总长度必然等于1.0P2=P1+p(x2)P1=p(x1)Pn=1Pn-1=Pn-2+p(xn-1)x1x2……xn算术编码的基本原理由于每个消息的起点位置等于前面各个消息的概率累积，故将它定义为累积概率Pk.反过来,也可以由累积概率来计算某个消息的概率:pk＝Pk-Pk-1,即两个相邻起点之间的距离等于这个线段的长度.每个消息所对应的线段从起点开始,到下一个线段的起点为此,但不包含下一个线段的起点,即消息Xk的对应区间为[Pk-1,Pk).任意选择一个小数,它必然落在某个消息对应的线段上这说明,可以用一个具有大小概念的小数来表示某个消息,这就是算术编码的基本出发点.算术编码具体过程设消息Xk的概率为pk,其对应区间为[Pk-1,Pk)计算Xk的信息量I(Xk),取的整数L,再将Xk的起点Pk用二进制小数表示保留小数点后L位,将后面的余数进位到小数点后第L位,得到的小数C就是消息Xk的算术编码结果.I(Xk)≤L<I(Xk)+1算术编码的例子[例1]某个信源有四个消