霍夫曼编码霍夫曼编码

多媒体技术基础(第3版)第2章数据无损压缩张奇复旦大学计算机科学技术学院2015年4月2020年2月12日第2章数据无损压缩2of72第2章数据无损压缩目录2.1数据的冗余2.1.1冗余概念2.1.2决策量2.1.3信息量2.1.4熵2.1.5数据冗余量2.2统计编码2.2.1香农-范诺编码2.2.2霍夫曼编码2.2.3算术编码2.3RLE编码2.4词典编码2.4.1词典编码的思想2.4.2LZ77算法2.4.3LZSS算法2.4.4LZ78算法2.4.5LZW算法参考文献和站点2020年2月12日第2章数据无损压缩3of722.0数据无损压缩概述数据可被压缩的依据数据本身存在冗余听觉系统的敏感度有限视觉系统的敏感度有限三种多媒体数据类型文字(text)数据——无损压缩根据数据本身的冗余(Basedondataredundancy)声音(audio)数据——有损压缩根据数据本身的冗余(Basedondataredundancy)根据人的听觉系统特性(Basedonhumanhearingsystem)图像(image)/视像(video)数据——有损压缩根据数据本身的冗余(Basedondataredundancy)根据人的视觉系统特性(Basedonhumanvisualsystem)2020年2月12日第2章数据无损压缩4of722.0数据无损压缩概述(续1)数据无损压缩的理论——信息论(informationtheory)1948年创建的数学理论的一个分支学科，研究信息的编码、传输和存储该术语源于ClaudeShannon(香农)发表的“AMathematicalTheoryofCommunication”论文题目，提议用二进制数据对信息进行编码最初只应用于通信工程领域，后来扩展到包括计算在内的其他多个领域，如信息的存储、信息的检索等。在通信方面，主要研究数据量、传输速率、信道容量、传输正确率等问题。数据无损压缩的方法霍夫曼编码(Huffmancoding)算术编码(arithmeticcoding)行程长度编码(run-lengthcoding)词典编码(dictionarycoding)……2020年2月12日第2章数据无损压缩5of722.0数据无损压缩概述(续2)TheFatherofInformationTheory——ClaudeElwoodShannonBorn:30April1916inGaylord,Michigan,USADied:24Feb2001inMedford,Massachusetts,USA信息论之父介绍2020年2月12日第2章数据无损压缩6of722.0数据无损压缩概述(续3)ClaudeShannon——Thefoundingfatherofelectroniccommunicationsage；AmericanmathematicalengineerIn1936~1940,MIT:Master'sthesis,AsymbolicanalysisofrelayandswitchingcircuitsDoctoralthesis:ontheoreticalgeneticsIn1948:Amathematicaltheoryofcommunication,landmark,climax(AnimportantfeatureofShannon'stheory:conceptofentropy)2020年2月12日第2章数据无损压缩7of722.1数据的冗余冗余概念人为冗余在信息处理系统中，使用两台计算机做同样的工作是提高系统可靠性的一种措施在数据存储和传输中，为了检测和恢复在数据存储或数据传输过程中出现的错误，根据使用的算法的要求，在数据存储或数据传输之前把额外的数据添加到用户数据中，这个额外的数据就是冗余数据视听冗余由于人的视觉系统和听觉系统的局限性，在图像数据和声音数据中，有些数据确实是多余的，使用算法将其去掉后并不会丢失实质性的信息或含义，对理解数据表达的信息几乎没有影响数据冗余不考虑数据来源时，单纯数据集中也可能存在多余的数据，去掉这些多余数据并不会丢失任何信息，这种冗余称为数据冗余，而且还可定量表达2020年2月12日第2章数据无损压缩8of722.1数据的冗余(续1)决策量(decisioncontent)在有限数目的互斥事件集合中，决策量是事件数的对数值在数学上表示为H0=log(n)其中，n是事件数决策量的单位由对数的底数决定Sh(Shannon):用于以2为底的对数Nat(naturalunit):用于以e为底的对数Hart(hartley)：用于以10为底的对数2020年2月12日第2章数据无损压缩9of722.1数据的冗余(续2)信息量(informationcontent)具有确定概率事件的信息的定量度量在数学上定义为其中，是事件出现的概率举例：假设X={a,b,c}是由3个事件构成的集合，p(a)=0.5，p(b)=0.25，p(b)=0.25分别是事件a,b和c出现的概率，这些事件的信息量分别为，I(a)=log2(1/0.50)=1shI(b)=log2(1/0.25)=2shI(c)=log2(1/0.25)=2sh一个等概率事件的集合，每个事件的信息量等于该集合的决策量22()log[1/()]log()Ixpxpx()px2020年2月12日第2章数据无损压缩10of722.1数据的冗余(续3)熵(entropy)按照香农(Shannon)的理论，在有限的互斥和联合穷举事件的集合中，熵为事件的信息量的平均值，也称事件的平均信息量(meaninformationcontent)用数学表示为2020年2月12日第2章数据无损压缩11of722.1数据的冗余(续4)数据的冗余量2020年2月12日第2章数据无损压缩12of722.2统计编码统计编码给已知统计信息的符号分配代码的数据无损压缩方法编码方法香农-范诺编码霍夫曼编码算术编码编码特性香农-范诺编码和霍夫曼编码的原理相同，都是根据符号集中各个符号出现的频繁程度来编码，出现次数越多的符号，给它分配的代码位数越少算术编码使用0和1之间的实数的间隔长度代表概率大小，概率越大间隔越长，编码效率可接近于熵2020年2月12日第2章数据无损压缩13of722.2.1统计编码——香农-范诺编码香农-范诺编码(Shannon–Fanocoding)在香农的源编码理论中，熵的大小表示非冗余的不可压缩的信息量在计算熵时，如果对数的底数用2，熵的单位就用“香农(Sh)”，也称“位(bit)”。“位”是1948年Shannon首次使用的术语。例如最早阐述和实现“从上到下”的熵编码方法的人是Shannon(1948年)和Fano(1949年)，因此称为香农-范诺(Shannon-Fano)编码法2020年2月12日第2章数据无损压缩14of722.2.1香农-范诺编码香农-范诺编码举例有一幅40个像素组成的灰度图像，灰度共有5级，分别用符号A，B，C，D和E表示。40个像素中出现灰度A的像素数有15个，出现灰度B的像素数有7个，出现灰度C的像素数有7个，其余情况见表2-1(1)计算该图像可能获得的压缩比的理论值(2)对5个符号进行编码(3)计算该图像可能获得的压缩比的实际值表2-1符号在图像中出现的数目符号ABCDE出现的次数157765出现的概率15/407/407/406/405/402020年2月12日第2章数据无损压缩15of722.2.1香农-范诺编码(续1)(1)压缩比的理论值按照常规的编码方法，表示5个符号最少需要3位，如用000表示A，001表示B，…，100表示E，其余3个代码(101，110，111)不用。这就意味每个像素用3位，编码这幅图像总共需要120位。按照香农理论，这幅图像的熵为21222222()()log()()log(())()log(())()log(())=(15/40)log(40/15)+(7/40)log(40/7)++(5/40)log(40/5)2.196niiiHXpxpxpApApBpBpEpE这个数值表明，每个符号不需要用3位构成的代码表示，而用2.196位就可以，因此40个像素只需用87.84位就可以，因此在理论上，这幅图像的的压缩比为120:87.84≈1.37:1，实际上就是3:2.196≈1.372020年2月12日第2章数据无损压缩16of722.2.1香农-范诺编码(续2)(2)符号编码对每个符号进行编码时采用“从上到下”的方法。首先按照符号出现的频度或概率排序，如A，B，C，D和E，见表2-2。然后使用递归方法分成两个部分，每一部分具有近似相同的次数，如图2-1所示2020年2月12日第2章数据无损压缩17of722.2.1香农-范诺编码(续3)（3）压缩比的实际值按照这种方法进行编码需要的总位数为30+14+14+18+15＝91，实际的压缩比为120:91≈1.32:1图2-1香农-范诺算法编码举例2020年2月12日第2章数据无损压缩18of722.2.2统计编码——霍夫曼编码霍夫曼编码(Huffmancoding)霍夫曼(D.A.Huffman)在1952年提出和描述的“从下到上”的熵编码方法根据给定数据集中各元素所出现的频率来压缩数据的一种统计压缩编码方法。这些元素(如字母)出现的次数越多，其编码的位数就越少广泛用在JPEG,MPEG,H.26X等各种信息编码标准中2020年2月12日第2章数据无损压缩19of722.2.2霍夫曼编码—CaseStudy1霍夫曼编码举例1现有一个由5个不同符号组成的30个符号的字符串：BABACACADADABBCBABEBEDDABEEEBB计算(1)该字符串的霍夫曼码(2)该字符串的熵(3)该字符串的平均码长(4)编码前后的压缩比2020年2月12日第2章数据无损压缩20of722.2.2霍夫曼编码—CaseStudy1(续1)符号出现的次数log2(1/pi）分配的代码需要的位数B101.585?A81.907?C33.322?D42.907?E52.585?合计30符号出现的概率2020年2月12日第2章数据无损压缩21of722.2.2霍夫曼编码—CaseStudy1(续2)(1)计算该字符串的霍夫曼码步骤①：按照符号出现概率大小的顺序对符号进行排序步骤②：把概率最小的两个符号组成一个节点P1步骤③：重复步骤②，得到节点P2，P3，P4，……，PN，形成一棵树，其中的PN称为根节点步骤④：从根节点PN开始到每个符号的树叶，从上到下标上0(上枝)和1(下枝)，至于哪个为1哪个为0则无关紧要，但通常把概率大的标成1，概率小的标成0步骤⑤：从根节点PN开始顺着树枝到每个叶子分别写出每个符号的代码2020年2月12日第2章数据无损压缩22of722.2.2霍夫曼编码—CaseStudy1(续3)符号B(10)A(8)E(5)D(4)C(3)P1(7)P2(12)P3(18)P4(30)01101010代码B(11)A(10)E(00)D(011)C(010)2020年2月12日第2章数据无损压缩23of722.2.2霍夫曼编码—CaseStudy1(续4)符号出现的次数log2(1/pi）分配的代码需要的位数B101.5851120A81.9071016C33.3220109D42.90701112E52.5850010合计301.06730个字符组成的字符串需要67位5个符号的代码2020年2月12日第2章数据无损压缩24of722.2.2霍夫曼编码—CaseStudy1(续5)(2)计算该字符串的熵