第8章--数据压缩算法NEW

1、,算法分析与复杂度理论2009,罗熊北京科技大学信息工程学院计算机系,数据压缩算法,2009.4,3,提纲,数据压缩基本概念ASCII码压缩算法哈夫曼编码算术编码词典编码,4,将信源所发出的信号用较少的数码表示，减少容纳给定数据集合的信号空间。所谓信号空间，亦即被压缩的对象是指：物理空间，即数据存储介质的尺寸。时间区间，传输消息集合所需要的时间。电磁频谱区域，如为传输消息的带宽等。信号空间的各种形式相互关联。减少存储空间就能提高传输效率和节省带宽的占用。,1.数据压缩基本概念,5,(1)信息量定义。设信源x由属于集合Ama1,a2,am的m个可能的符号产生，若信源事件aj的概率为P(aj)，则

2、定义事件aj的信息量I(aj)I(aj)logP(aj)作为事件aj所包含的信息量的量度，称为自信息。单位：取2为底的对数，则单位为比特(bit)；取e为底的对数，则单位为奈特。,信息的量度,6,从信息量的定义可以看出，信息是事件aj的不确定因素的度量。事件发生的概率越大，事件的信息量越小；反之，一个发生可能性很小的事件，携带的信息量就很大，甚至使人们“震惊”。例如：在32个数码中任选1个数码时，设每个数码选中的概率是相等的，则那么，任一数码的信息量为,7,(2)信源的熵。一个通信系统并非只传送1个符号，而是多个符号，这就需要定义整个信源符号的平均信息量的大小。我们把自信息的统计平均值数学期望

3、即信源x中每个符号的平均信息量，称为信源x的熵。当信源x中的每个符号是等概率的且是独立的时候，平均信息量最大，此时，j=1，2，m则,8,例如：若信号xa1,a2的概率分别为P(a1)0.9，P(a2)0.1，则符号的平均信息量，即信源x的熵为H(x)=-(0.9lb0.9+0.1lb0.1)=0.467bit若a1,a2等概率，P(a1)=P(a2)=0.5，则信源x的平均信息量达到最大，即H(x)=Hm(x)=lb2=1bit所以二进制1位数据(0/1)的每1位的信息量即为1比特。,9,再看一个例子，设一幅图片有4个灰度级S=A，B，C，D，这4个灰度级所出现的概率分别为P(aj)=0.6

4、，0.2，0.06，0.14，则H(x)=-(0.6lb0.6+0.2lb0.2+0.06lb0.06+0.14lb0.14)=1.547bit即其平均信息熵为1.547bit。这说明表示这4个灰度级所使用的最少平均位数为1.547bit。,平均信息熵是一种理论上的最佳编码的平均码长。,10,问题,一个无记忆信源有四种符号0、1、2、3，已知p(0)=3/8；p(1)=1/4；p(2)=1/4；p(3)=1/8，试求由6000个符号构成的信息所包含的信息量。,11,可逆压缩和不可逆压缩,可逆压缩叫做无失真、无差错编码。压缩后的数据可以精确地恢复为原来的数据。如ZIP、RAR、ARJ、CAB等文

5、件，都是可逆压缩。不可逆压缩叫做失真编码。压缩后的数据不可能精确地恢复成原始数据。如在计算机中存储的图片、声音、视频等文件。人的感觉器官本身对于图片、声音、视频中的某些信息的丢失，是难以察觉的。不可逆压缩技术的标准有：JPEG、MPEG-1、MPEG-2、MPEG-4等，均达到了很高的压缩比。,12,2.ASCII码压缩算法,数采用不同的基数来表示，长度不同。一般来说，基数较大，长度较短。,例如，十进制的1234是四位，需要四个字节存储，用16进制数表示为三位，4D2，只需要两个字节。,如果采用100为基数，即每两位十进制数用一个字节存放，就可以压缩50%。,例如，十进制的1234表示为百进制

6、数，即1234，只需要两个字节。,但是数字0099只需要7个比特，每个字节还有一个比特闲置，因此还可以压缩。把第八个数的依次放到前7个字节的最高位上。这样可以压缩62.5%。,13,1、将原数据的每两位数字作为一组，其值在0099之间；然后将它们转化为16进制，即0099分别对应于00H63H。2、从第一个16进制数开始，3、每8个16进制数为一组，将第8个数字拆成7个比特，把它们依次放到前面7个16进制数的最高位上。4、重复第3步，直至完成全部数据为止。,14,原数据：1234567891929394,按百进制分组：1234567891929394转换为16进制：0C22384E5B5C5D

7、5E每8个数为一组，将第8个，即5E=01011110的7个比特分别填到前7个数的最高位。,最后原数据压缩编码的结果为7个16进制的数据：8C22B8CEDBDC5D存储空间由原来的16个字节变成了7个字节。,15,3.哈夫曼编码,哈夫曼（D.A.Huffman）于1952年提出一种编码方法，它完全依据字符出现的概率来构造平均长度最短的编码，也称之为最佳编码。,哈夫曼树为在权为wl，w2，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为哈夫曼树。哈夫曼编码中各字符编码的长度不同，它的基本理论基于下列定理：在变长编码中，若各码字长度严格按照所对应的符号出现概率的大小

8、逆序排列，则其平均长度最小。为了避免产生歧义，编码时必须使得任一字符的编码都不是另外任意字符编码的前缀，这种编码称为前缀编码。,16,1.将n个频率为p1,p2,pn的字符表示为n个结点，将每个结点看成二叉树Ti，频率pi为其权值wi，组成集合F=T1,T2,Tn。2.在F中选取两棵权值最小的树作为左、右子树构造一棵新二叉树，令新二叉树的的权值为其左、右子树的权值之和。3.在F中删除这两棵树，并加入新的二叉树。4.重复2和3，直到F中只有一棵树为止。5.约定左、右分支分别为0和1。从根到叶子的路径的0和1的序列，即该字符的哈夫曼编码。,17,【例】计算哈夫曼编码。平均码长L=10.375+30

9、.175+30.175+30.15+30.125=2.25，编码需要402.25=90位。,18,应用哈夫曼编码应注意的事项：哈夫曼编码方法构造出来的码不是唯一的，但对于同一信源而言，其平均码字长是相同的，其编码效率是一样的。哈夫曼编码对不同的信源其编码效率是不同的，只有当信源概率分布很不均匀的时候，哈夫曼编码才会收到显著效果。,19,问题,一个信源包含6个符号信息，它们出现的概率分别是0.3、0.2、0.15、0.15、0.1、0.1，试用二进制码元的哈夫曼编码方法对该信源的6个符号做信源编码（画出哈夫曼编码树），并求出码字的平均长度和编码效率（=信息熵/平均码长）。,20,由于哈夫曼编码使

10、用整数个二进制位对符号进行编码，这种方法在某些情况下无法得到最优压缩效果。例如，某个字符的出现概率是80%，该字符事实上只需要-log2(0.8)0.322位编码，但哈夫曼编码一定会为其至少分配1位的编码，这样一来，整个信息的80%在压缩后几乎相当于理想长度的3倍左右。这是哈夫曼编码的局限之一！算术编码不是将单个信源符号映射成一个码字，而是对信源整体进行编码。把信源符号表示为01之间的子区间。消息序列中的元素越多，所得到的区间就越小，就需要更多的数位来表示这个区间。在最后确定的区间里选择一个代表性的小数，转化为二进制作为实际的编码输出。,4.算术编码,21,【例】假设信源符号为a，b，c，d，

11、每个符号对应的概率分别为0.1，0.4，0.2，0.3，当输入的信息符号序列为cadacdb时，写出其算术编码及解码过程。,22,输入,23,24,算术编码方法复杂，但比哈夫曼编码提高了5%左右的效率，且无需传送码表。在JPEG的扩展系统中，用算术编码取代了哈夫曼编码。由于实际计算机的精度不可能无限长，运算中出现溢出是一个明显的问题（但可以通过比例缩放方法解决）。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。,25,问题,设有一个信源具有4个可能出现的符号X1、X2、X3、X4，其出现的概率分别为1/2、1/4、1/8、1/8，试以符号序列X2X1X4X3X1

12、为例，描述其算术编码和解码的过程。,26,有许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。因此，人们提出了许许多多的数据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码（DictionaryEncoding）技术就是属于这一类，这种技术属于无损压缩技术。词典编码的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。,5.词典编码,27,基本思想是：构造一个字典，将信息中反复出现的字符串，登记为较短的字符串，解码时对这种字符串，通过查字典，转换为原字符串。该算法的原

13、理很简单，但要真正实现却很困难，因为它存在几个长期困扰着研究者的难点：1、如何找到这些重复出现的字符串？2、如何找到尽量长的字符串被替代？3、怎样选用较短的字符串？如何区分原始信息中就已经存在的用于代替的字符串？,词典编码法的种类很多，归纳起来大致有两类。,28,第一类词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。,29,第二类算法的想法是企图从输入的数据中创建一个“短语词典（DictionaryofthePhrases）”，这种短语不一定是具有具体含义的短语，它可以是任意字符的组合

14、。编码数据过程中当遇到已经在词典中出现的“短语”时，编码器就输出这个词典中的短语的“索引号”，而不是短语本身。,30,LZ算法,1977年，JacobZiv和AbrahamLempel发表了论文顺序数据压缩的一个通用算法。1978年，他们发表了该论文的续篇通过可变比率编码的独立序列的压缩。这两篇论文提出的两个压缩技术被称为LZ77和LZ78算法。它们的思路和字典法颇为相似，因此，人们将基于这一思路的编码方法称作字典式编码。字典式编码不但在压缩效果上大大超过了哈夫曼编码，而且，对于好的实现，其压缩和解压缩的速度也异常惊人。,31,LZ77算法,LZ77算法又称为“滑动窗口压缩”，如下图：,32,

15、LZ77算法的基本流程,重复进行以下处理，直至所有数据处理完毕：1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，2、如果找到，输出三元符号组(off,len,c)，其中off为窗口中匹配字符串相对窗口边界的偏移，len为可匹配的长度，c为下一个字符；将窗口向后滑动len+1个字符。3、如果未找到，输出三元符号组(0,0,c)，其中c为下一个字符；将窗口向后滑动1个字符。,33,假设窗口的大小为10个字符，我们刚编码过的10个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee。,窗口,首先发现，可以和要编码字符匹配的最长串为ab(off=0,

16、len=2),ab的下一个字符为a，我们输出三元组：(0,2,a)。,a,b,a,34,现在将窗口向后滑动3(2+1)个字符，窗口中的内容为：dbbccaaaba，剩余字符为eaaabaee，下一个字符e在窗口中没有匹配，我们输出三元组：(0,0,e)。,35,又将窗口向后滑动1个字符，其中内容变为：bbccaaabae。这时发现，要编码的aaabae在窗口中存在(off=4,len=6)，其后的字符为e，可以输出：(4,6,e)。,36,最后又将窗口向后滑动7个字符。这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。,37,LZ77算法的解压缩,LZ77算法

17、的解压缩的过程十分简单，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符c输出（如果off和len都为0则只输出后继字符c)，即可还原出原始数据。,38,LZ77算法的讨论,1、编码方法,分量off与窗口的大小有关，完全可以用固定的位数来表示它。分量len可以使用一种变长的编码方式来表示该长度值。字符c，用8个二进制位对其编码。,39,2、输出方式原始LZ77算法即使没有匹配，仍然需要输出一个len=0的三元组来表示单个字符，还可以设计出另外一种更为有效的输出方式：将匹配串和不能匹配的单个字符分别编码、分别输出，输出匹配串时不同时输出后续字

18、符。,40,3、如何查找匹配串限制可匹配字符串的最大长度（例如20个字节），按照大小顺序组织成二叉有序树。在这样的二叉有序树中进行字符串的查找，其效率是很高的。当然，也可以采用KMP、KR、BM等快速串匹配算法来依次进行长度为20、19、18的模式匹配。,41,LZ78算法,LZ78算法的基本思路与LZ77算法类似，也是利用已经处理过的编码信息，但它发生匹配时，不是保存一个三元组，而是一个二元组：匹配位置和不匹配的第一个字符。同时，还要将这个字符串保存到内存中，为此，它需要一个不断增长的编码字串表（字典）。与LZ77相比，LZ78的最大优点是在每个编码步骤中减少了字符串比较的数目，而压缩率与L

19、Z77类似。,42,如对符号串“ababcbabaaaaaaa”编码，需要的字典：,43,LZ78算法的框架,voidLZ78(void)将字典D置空;while(还有字符未处理完)current=0;goon=1;read(w);while(goon)if(wD)current=#w;read(k);w=w+k;elsegoon=0;append(D,w);/*将字符串w放到字典的尾部*/w=last_char(w);/*取字符串w的末尾字符*/write(current,w);/*输出匹配位置和不匹配字符*/,#w表示w在字典中的序号,44,LZW算法,LZ78算法很难一次匹配到更长的字符

20、串，而且，它所保存的信息量仍然有冗余，因为如果每一个字符都一定能匹配成功的话，也可以不需要保存匹配不成功的字符。LZW算法的基本思路就是要尽量“拉长”这些串，为此，它将LZ78算法中的每一个被分割的子串的最后一个字符作为下一个子串的开始。当然这么做肯定会增加字典的长度。而且需要先将所有可能出现的单字符先放到字典中以保证单字符一定能匹配成功。WinZIP，WinRAR等压缩工具及GIF、PNG等文件格式都是LZ系列算法的受益者。,45,LZW算法的框架,voidLZW(void)将所有单字符放入字典D中；read(w);while(还有字符未处理完)read(k);if(w+kD)w=w+k;elsewrite(w在字典中的序号);append(dictionary,w+k);w=k;,46,对于字符串“ababcbaaaaaaaa”，得到的字典如右：,原字符串,压缩码,序号,压缩后的编码为：a,b,c+1,2,4,3,5,1,9,10,单字符可事先约定，从而无需传输。,47,LZW解压缩算法,voidunLZW(void)