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

©2002IBMCorporationAlgorithmAlgorithmAnalysis&ComplexityTheoryUSTB算法分析与复杂度理论•2009罗熊[e-mail]北京科技大学信息工程学院计算机系©2002IBMCorporationAlgorithmAlgorithmAnalysis&ComplexityTheoryUSTB数据压缩算法2009.4AlgorithmUSTBAlgorithmDesign&Analysis3提纲数据压缩基本概念ASCII码压缩算法哈夫曼编码算术编码词典编码AlgorithmUSTBAlgorithmDesign&Analysis4将信源所发出的信号用较少的数码表示，减少容纳给定数据集合的信号空间。所谓信号空间，亦即被压缩的对象是指：①物理空间，即数据存储介质的尺寸。②时间区间，传输消息集合所需要的时间。③电磁频谱区域，如为传输消息的带宽等。信号空间的各种形式相互关联。减少存储空间就能提高传输效率和节省带宽的占用。1.数据压缩基本概念AlgorithmUSTBAlgorithmDesign&Analysis5(1)信息量定义。设信源x由属于集合Am＝{a1,a2,…,am}的m个可能的符号产生，若信源事件aj的概率为P(aj)，则定义事件aj的信息量I(aj)I(aj)＝－logP(aj)作为事件aj所包含的信息量的量度，称为自信息。单位：取2为底的对数，则单位为比特(bit)；取e为底的对数，则单位为奈特。信息的量度AlgorithmUSTBAlgorithmDesign&Analysis6从信息量的定义可以看出，信息是事件aj的不确定因素的度量。事件发生的概率越大，事件的信息量越小；反之，一个发生可能性很小的事件，携带的信息量就很大，甚至使人们“震惊”。例如：在32个数码中任选1个数码时，设每个数码选中的概率是相等的，则那么，任一数码的信息量为321)a(Pjbit52lb321lb)a(I5jAlgorithmUSTBAlgorithmDesign&Analysis7(2)信源的熵。一个通信系统并非只传送1个符号，而是多个符号，这就需要定义整个信源符号的平均信息量的大小。我们把自信息的统计平均值——数学期望即信源x中每个符号的平均信息量，称为信源x的熵。当信源x中的每个符号是等概率的且是独立的时候，平均信息量最大，此时，j=1，2，…，m则)a(lbP)a(P)x(Hjm1jjlbmH)x(Hmaxm1)a(PjAlgorithmUSTBAlgorithmDesign&Analysis8例如：若信号x{a1,a2}的概率分别为P(a1)＝0.9，P(a2)＝0.1，则符号的平均信息量，即信源x的熵为H(x)=-(0.9×lb0.9+0.1×lb0.1)=0.467bit若a1,a2等概率，P(a1)=P(a2)=0.5，则信源x的平均信息量达到最大，即H(x)=Hm(x)=lb2=1bit所以二进制1位数据(0/1)的每1位的信息量即为1比特。AlgorithmUSTBAlgorithmDesign&Analysis9再看一个例子，设一幅图片有4个灰度级S={A，B，C，D}，这4个灰度级所出现的概率分别为P(aj)={0.6，0.2，0.06，0.14}，则H(x)=-(0.6×lb0.6+0.2×lb0.2+0.06×lb0.06+0.14×lb0.14)=1.547bit即其平均信息熵为1.547bit。这说明表示这4个灰度级所使用的最少平均位数为1.547bit。平均信息熵是一种理论上的最佳编码的平均码长。AlgorithmUSTBAlgorithmDesign&Analysis10问题一个无记忆信源有四种符号0、1、2、3，已知p(0)=3/8；p(1)=1/4；p(2)=1/4；p(3)=1/8，试求由6000个符号构成的信息所包含的信息量。AlgorithmUSTBAlgorithmDesign&Analysis11可逆压缩和不可逆压缩可逆压缩叫做无失真、无差错编码。压缩后的数据可以精确地恢复为原来的数据。如ZIP、RAR、ARJ、CAB等文件，都是可逆压缩。不可逆压缩叫做失真编码。压缩后的数据不可能精确地恢复成原始数据。如在计算机中存储的图片、声音、视频等文件。人的感觉器官本身对于图片、声音、视频中的某些信息的丢失，是难以察觉的。不可逆压缩技术的标准有：JPEG、MPEG-1、MPEG-2、MPEG-4等，均达到了很高的压缩比。AlgorithmUSTBAlgorithmDesign&Analysis122.ASCII码压缩算法数采用不同的基数来表示，长度不同。一般来说，基数较大，长度较短。例如，十进制的1234是四位，需要四个字节存储，用16进制数表示为三位，4D2，只需要两个字节。如果采用100为基数，即每两位十进制数用一个字节存放，就可以压缩50%。例如，十进制的1234表示为百进制数，即1234，只需要两个字节。但是数字00~99只需要7个比特，每个字节还有一个比特闲置，因此还可以压缩。把第八个数的依次放到前7个字节的最高位上。这样可以压缩62.5%。AlgorithmUSTBAlgorithmDesign&Analysis131、将原数据的每两位数字作为一组，其值在00~99之间；然后将它们转化为16进制，即00~99分别对应于00H~63H。2、从第一个16进制数开始，3、每8个16进制数为一组，将第8个数字拆成7个比特，把它们依次放到前面7个16进制数的最高位上。4、重复第3步，直至完成全部数据为止。AlgorithmUSTBAlgorithmDesign&Analysis14原数据：1234567891929394按百进制分组：1234567891929394转换为16进制：0C22384E5B5C5D5E每8个数为一组，将第8个，即5E=01011110的7个比特分别填到前7个数的最高位。000011000C00100010220011100038010011104E010110115B010111005C010111015D18C01B81CE1DB1DC0最后原数据压缩编码的结果为7个16进制的数据：8C22B8CEDBDC5D存储空间由原来的16个字节变成了7个字节。AlgorithmUSTBAlgorithmDesign&Analysis153.哈夫曼编码哈夫曼（D.A.Huffman）于1952年提出一种编码方法，它完全依据字符出现的概率来构造平均长度最短的编码，也称之为最佳编码。哈夫曼树为在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为哈夫曼树。哈夫曼编码中各字符编码的长度不同，它的基本理论基于下列定理：在变长编码中，若各码字长度严格按照所对应的符号出现概率的大小逆序排列，则其平均长度最小。为了避免产生歧义，编码时必须使得任一字符的编码都不是另外任意字符编码的前缀，这种编码称为前缀编码。AlgorithmUSTBAlgorithmDesign&Analysis161.将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的序列，即该字符的哈夫曼编码。AlgorithmUSTBAlgorithmDesign&Analysis17【例】计算哈夫曼编码。平均码长L=1×0.375+3×0.175+3×0.175+3×0.15+3×0.125=2.25，编码需要40×2.25=90位。AlgorithmUSTBAlgorithmDesign&Analysis18应用哈夫曼编码应注意的事项：•哈夫曼编码方法构造出来的码不是唯一的，但对于同一信源而言，其平均码字长是相同的，其编码效率是一样的。•哈夫曼编码对不同的信源其编码效率是不同的，只有当信源概率分布很不均匀的时候，哈夫曼编码才会收到显著效果。AlgorithmUSTBAlgorithmDesign&Analysis19问题一个信源包含6个符号信息，它们出现的概率分别是0.3、0.2、0.15、0.15、0.1、0.1，试用二进制码元的哈夫曼编码方法对该信源的6个符号做信源编码（画出哈夫曼编码树），并求出码字的平均长度和编码效率（=信息熵/平均码长）。AlgorithmUSTBAlgorithmDesign&Analysis20由于哈夫曼编码使用整数个二进制位对符号进行编码，这种方法在某些情况下无法得到最优压缩效果。例如，某个字符的出现概率是80%，该字符事实上只需要-log2(0.8)≈0.322位编码，但哈夫曼编码一定会为其至少分配1位的编码，这样一来，整个信息的80%在压缩后几乎相当于理想长度的3倍左右。这是哈夫曼编码的局限之一！算术编码不是将单个信源符号映射成一个码字，而是对信源整体进行编码。把信源符号表示为0~1之间的子区间。消息序列中的元素越多，所得到的区间就越小，就需要更多的数位来表示这个区间。在最后确定的区间里选择一个代表性的小数，转化为二进制作为实际的编码输出。4.算术编码AlgorithmUSTBAlgorithmDesign&Analysis21【例】假设信源符号为{a，b，c，d}，每个符号对应的概率分别为{0.1，0.4，0.2，0.3}，当输入的信息符号序列为cadacdb时，写出其算术编码及解码过程。AlgorithmUSTBAlgorithmDesign&Analysis22输入AlgorithmUSTBAlgorithmDesign&Analysis23AlgorithmUSTBAlgorithmDesign&Analysis24算术编码方法复杂，但比哈夫曼编码提高了5%左右的效率，且无需传送码表。在JPEG的扩展系统中，用算术编码取代了哈夫曼编码。由于实际计算机的精度不可能无限长，运算中出现溢出是一个明显的问题（但可以通过比例缩放方法解决）。算术编码也是一种对错误很敏感的编码方法，如果有一位发生错误就会导致整个消息译错。AlgorithmUSTBAlgorithmDesign&Analysis25问题设有一个信源具有4个可能出现的符号X1、X2、X3、X4，其出现的概率分别为1/2、1/4、1/8、1/8，试以符号序列X2X1X4X3X1为例，描述其算术编码和解码的过程。AlgorithmUSTBAlgorithmDesign&Analysis26有许多场合，开始时不知道要编码数据的统计特性，也不一定允许你事先知道它们的统计特性。因此，人们提出了许许多多的数据压缩方法，企图用来对这些数据进行压缩编码，在实际编码过程中以尽可能获得最大的压缩比。这些技术统称为通用编码技术。词典编码（DictionaryEncoding）技术就是属于这一类，这种技术属于无损压缩技术。词典编码的根据是数据本身包含有重复代码这个特性。例如文本文件和光栅图像就具有这种特性。5.词典编码AlgorithmUSTBAlgorithmDesign&Analysis27基本思想是：构造一个字典，将信息中反复出现的字符串，登记为较短的字符串，解码时对这种字符串，通过查字典，转换为原字符串。该算法的原理很简单，但要真正实现却很困难，因为它存在几个长期困扰着研究者的难点：1、如何找到这些重复出现的字符串？2、如何找到尽量长的字符串被替代？3、怎样选用较短的字符串？如何区分原始信息中就已经存在的用于代替的字符串？词典编码法的种类很多，归纳起来大致有两类。Algori