字典编码课件.ppt_163文库

资源描述

1、1第五章字典编码n迄今为止，我们大多假设符号是独立的n但这对许多常见数据类型来说是不对的n如：文本、图像和源代码文件n基本思想n标识经常出现的符号模式保存于字典中n对这些常出现的模式采用更有效的编码方式用其在字典中的索引作为码字n而对其它部分采用缺省（不太有效）的编码方式n以期总的编码效率更高n注意n这对如文本这样的信源是合理的n显然对（接近）随机数据不会有效2例n考虑某英文文本信源n26 字母和6个标点符号n单字符，定长码n5 比特/字符n4字符模式，定长码n20比特/模式(324=220=1,048,576)n假设为非均匀分布n字典：256个最常出现的模式，每个用8比特编码n对其它模式用

2、20比特编码n再增加1比特用于指示是上述两种情况中的哪种3例(2)n若用p 表示使用字典的概率，则比特率为R=9p+21(1-p)=21-12pn压缩 21-12p p 0.084n还不太坏n在等概率假设下，p=0.00025n p越大，性能越好选择最可能出现的模式存于字典中n为了达到好的性能，需要知道信源的结构信息n有足够的先验信息，静态字典n否则，在编码过程中获得信源的知识自适应字典4静态字典n静态字典n对信源的结构有足够的先验知识时，利用先验知识构造字典n对特定应用特别有效n只对针对其设计的特定应用和数据有效n例：电话号码的区号n例：学校的学生信息表5自适应字典n有许多场合，开始时不

3、知道要编码数据的统计特性，也不一定允许事先知道它们的统计特性。n字典编码的思路：根据数据本身包含有重复代码的特性n例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮n如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。n实用的字典编码算法的核心就是如何动态地形成字典，以及如何选择输出格式以减小冗余。6自适应字典n开始nJacob Ziv/Abraham Lempeln1977(LZ77/LZ1),1978(LZ78/LZ2)n1984 Terry Welch(LZW)nLZ77 vs.LZ78n两种不同的方法n有很多变种n是很多主流压缩

4、的基础7LZ77n基本方法：字典为先前已编码序列的一部分n搜索缓冲区为当前字典，通常为几千字节n机制：滑动窗口n搜索缓冲区(Search buffer)、前向（look ahead）缓冲区、搜索指针(search pointer)n目标：在搜索缓冲区中，寻找与搜索指针指向的字符串匹配的最长串，并对其进行编码n基本原理：如果某些模式在局部重复出现，能得到更有效的表示8LZ77(2)n(o)ffset=search ptr-match ptr=7n(l)ength=连续匹配的字符数=4n(c)odeword=C(r)n编码n=nIf|search buff|=S,|A|=A,S+|LA buff|

7、滑动词典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。nLZ77解码器比编码器简单得多（非对称压缩）n维持一个与编码器窗口大小相同的缓冲区，并在缓冲区中找出匹配串，将匹配串及第3个字段的字符写入输出流，同时移进缓冲区n在如文件压缩（一次压缩，多次还原）的场合很有用13LZ77的变种n迄今为止n自适应模型，没有先验知识n渐近接近知道信源统计知识的情况n但是，局部性起到了很大作用n改进n变长编码noffset:各数值基本均匀分布，一般用定长码nlength:可用Huffman码/Golomb码/Exp-Golomb码nPKZip,

8、Zip,Lharcm ONG,gzip,ARJn可变缓冲区大小n需设计较完善的数据结构来实现对大缓冲区的快速搜索nLZSS：搜索缓冲区（字典）用对分查找树保持，前向缓冲区用循环队列表示n取消 nLZSS：只需增加1一个标记位，用于指示是否为单字符14LZ78nLZ77假设模式满足局部性nLZ78:n没有搜索缓冲区代之以显式的字典n编码器/解码器必须同步建立字典n 如没有匹配，将字典原有词条+当前没有匹配的字符字典的新词条n编码：ni=字典索引n同LZ77，i=0 表示在字典中没有找到匹配的词条nc=下一字符的码字15LZ78举例字典：输入：wabbawabbawabbawabbawoowoo

9、woo输出：16LZ78举例(2)字典：输入：wabbawabbawabbawabbawoowoowoo输出：17LZ78举例(3)字典：输入：-abbawabbawabbawabbawoowoowoo输出：18LZ78举例(4)字典：输入：-bbawabbawabbawabbawoowoowoo输出：19LZ78举例(5)字典：输入：-bawabbawabbawabbawoowoowoo输出：20LZ78举例(6)字典：输入：-wabbawabbawabbawoowoowoo输出：21LZ78举例(7)字典：输入：-wabbawabbawabbawoowoowoo输出：22LZ78举例(8)

10、字典：输入：-bbawabbawabbawoowoowoo输出：23LZ78举例(9)字典：输入：-awabbawabbawoowoowoo输出：24LZ78举例(10)字典：输入：-wabbawabbawoowoowoo输出：25LZ78举例(11)字典：输入：-bawabbawoowoowoo输出：26LZ78举例(12)字典：输入：-wabbawoowoowoo输出：27LZ78举例(13)字典：输入：-awoowoowoo输出：28LZ78举例(14)字典：输入：-oowoowoo输出：29LZ78举例(15)字典：输入：-owoowoo输出：30LZ78举例(16)字典：输入：-wo

11、owoo输出：31LZ78举例(17)字典：输入：-owoo输出：32LZ78举例(18)字典：输入：-oo输出：33LZ78n观察：如果继续编码，字典将继续增长n实用的选择n停止增长字典n相当于从此成为一个静态字典策略n删除一些较早用过的项n如基于使用统计（但还没有好的算法决定哪些项该删）n将字典全部删除，从空字典开始重建字典n如果没有信源的特定知识，任何方法可能都不会工作得很好！34LZ78的变种：LZWnTerry Welch(1984)n基本思想：n只对i编码，而不是编码 n算法：n/初始化字典为包含所有字母 Seed dictionary with all alphabet lett

12、ers,p=null while(!done)a=get_next_symbolif(p a)is in dictionary /在字典中，继续用更长的字符串匹配p=p aelsesend out index of p /不在字典中，输出已匹配部分，从a 重新开始p.a is added to dictionary p=aendwhile35LZW编码字典：输出：输入：wabbawabbawabbawabbawoowoowoop=36LZW编码(2)字典：输出：输入：wabbawabbawabbawabbawoowoowoop=w 37LZW编码(3)字典：输出：5(w)输入：-abbawab

13、bawabbawabbawoowoowoop=wa38LZW编码(4)字典：输出：5(w)2(a)输入：-bbawabbawabbawabbawoowoowoop=ab39LZW编码(5)字典：输出：5(w)2(a)3(b)输入：-bawabbawabbawabbawoowoowoop=bb40LZW编码(6)字典：输出：5(w)2(a)3(b)3(b)输入：-awabbawabbawabbawoowoowoop=ba41LZW编码(7)字典：输出：5(w)2(a)3(b)3(b)2(a)输入：-wabbawabbawabbawoowoowoop=a42LZW编码(8)字典：输出：5(w)2(

14、a)3(b)3(b)2(a)1()输入：-wabbawabbawabbawoowoowoop=w43LZW编码(9)字典：输出：5(w)2(a)3(b)3(b)2(a)1()输入：-abbawabbawabbawoowoowoop=wa44LZW编码(10)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)输入：-bbawabbawabbawoowoowoop=wab45LZW编码(11)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)输入：-bawabbawabbawoowoowoop=bb46LZW编码(12)字典：输出：5(w)2(a)3(b)3(b

15、)2(a)1()6(wa)8(bb)输入：-awabbawabbawoowoowoop=bba47LZW编码(13)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)输入：-wabbawabbawoowoowoop=a48LZW编码(14)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)输入：-wabbawabbawoowoowoop=aw49LZW编码(15)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)输入：-abbawabbawoowoowoop=wa50LZW编码(16)字典：

16、输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)输入：-bbawabbawoowoowoop=wab51LZW编码(17)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)输入：-bawabbawoowoowoop=wabb52LZW编码(18)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)输入：-awabbawoowoowoop=ba53LZW编码(19)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wa

17、b)9(ba)输入：-wabbawoowoowoop=ba54LZW编码(20)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)输入：-wabbawoowoowoop=w55LZW编码(21)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)输入：-abbawoowoowoop=wa56LZW编码(22)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)输入：-bbawoowoowoop=

18、ab57LZW编码(23)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)输入：-bawoowoowoop=abb58LZW编码(24)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)输入：-awoowoowoop=ba59LZW编码(25)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)输入：-woowoowoop=ba60LZW编码(26)字

19、典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-woowoowoop=baw61LZW编码(27)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-oowoowoop=wo5(w)62LZW编码(28)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-owoowoop=oo5(w)4(o)63

20、LZW编码(29)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-woowoop=o5(w)4(o)4(o)64LZW编码(30)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-woowoop=w5(w)4(o)4(o)65LZW编码(31)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：

21、-oowoop=wo5(w)4(o)4(o)11(w)66LZW编码(32)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-owoop=oo5(w)4(o)4(o)11(w)67LZW编码(33)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-woop=oo5(w)4(o)4(o)11(w)21(oo)68LZW编码(34)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa

22、)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-woop=w5(w)4(o)4(o)11(w)21(oo)69LZW编码(35)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-oop=wo5(w)4(o)4(o)11(w)21(oo)70LZW编码(36)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-op=woo5(w)4(o)4(o)11(w)21

23、(oo)23(wo)71LZW编码(EOT)字典：输出：5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)12(wab)9(ba)11(w)7(ab)16(ba)输入：-p=o5(w)4(o)4(o)11(w)21(oo)23(wo)4(o)72LZW解码字典：输入：5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p=输出：73LZW解码(2)字典：输入：5 2 3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p=w 输出：w74LZW解码(3)字典：输入：-2 3 3 2 1 6

24、 8 10 12 9 11 7 16 5 4 4 11 21 23 4p=wa 输出：wa75LZW解码(4)输入：-3 3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p=ab 输出：wab字典：76LZW解码(5)输入：-3 2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p=bb 输出：wabb字典：77LZW解码(6)输入：-2 1 6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p=ba 输出：wabba字典：78LZW解码(7)输入：-1 6 8 10 12 9 11 7 16 5 4 4

25、11 21 23 4p=a 输出：wabba字典：79LZW解码(8)输入：-6 8 10 12 9 11 7 16 5 4 4 11 21 23 4p=wa 输出：wabbawa字典：80LZW解码(9)输入：-8 10 12 9 11 7 16 5 4 4 11 21 23 4p=wa 输出：wabbawa字典：81LZW解码(10)输入：-8 10 12 9 11 7 16 5 4 4 11 21 23 4p=wabb 输出：wabbawabb字典：82LZW解码(11)输入：-10 12 9 11 7 16 5 4 4 11 21 23 4p=bb 输出：wabbawabb字典：83L

26、ZW解码(12)输入：-10 12 9 11 7 16 5 4 4 11 21 23 4p=bba 输出：wabbawabba字典：84LZW解码(13)输入：-12 9 11 7 16 5 4 4 11 21 23 4p=bba 输出：wabbawabba字典：85LZW解码(14)输入：-12 9 11 7 16 5 4 4 11 21 23 4p=a 输出：wabbawabba字典：86LZW解码(15)输入：-12 9 11 7 16 5 4 4 11 21 23 4p=awab 输出：wabbawabbawab字典：87LZW解码(16)输入：-9 11 7 16 5 4 4 11

27、21 23 4p=wab 输出：wabbawabbawab字典：88LZW解码(16)输入：-9 11 7 16 5 4 4 11 21 23 4p=wab 输出：wabbawabbawab字典：89LZW解码(17)输入：-9 11 7 16 5 4 4 11 21 23 4p=wab 输出：wabbawabbawab字典：90LZW解码(18)输入：-9 11 7 16 5 4 4 11 21 23 4p=wabba 输出：wabbawabbawabba字典：91LZW解码(19)输入：-11 7 16 5 4 4 11 21 23 4p=ba 输出：wabbawabbawabba字典：9

28、2LZW解码(20)输入：-11 7 16 5 4 4 11 21 23 4p=baw 输出：wabbawabbawabbaw字典：93LZW解码(21)输入：-7 16 5 4 4 11 21 23 4p=w 输出：wabbawabbawabbaw 字典：最后得到与编码器输入一致的字符串94LZW特殊情况n上述解码器n简单、有效，但是，有时会出错n不过可以修复n例：nA=a,bn输入序列：abababab n开始字典95LZW特殊情况：编码字典：输出：输入：abababababab p=96LZW特殊情况：编码(2)输出：输入：abababababab p=a字典：97LZW特殊情况：编码(

29、3)输出：1(a)输入：-bababababab p=ab字典：98LZW特殊情况：编码(4)输出：1(a)2(b)输入：-ababababab p=ba字典：99LZW特殊情况：编码(5)输出：1(a)2(b)输入：-babababab p=ab字典：100LZW特殊情况：编码(6)输出：1(a)2(b)3(ab)输入：-abababab p=aba字典：101LZW特殊情况：编码(7)输出：1(a)2(b)3(ab)输入：-bababab p=ab字典：102LZW特殊情况：编码(8)输出：1(a)2(b)3(ab)输入：-ababab p=aba字典：103LZW特殊情况：编码(9)输出

30、：1(a)2(b)3(ab)5(aba)输入：-babab p=abab字典：104LZW特殊情况：解码输入：1 2 3 5 p=输出：字典：105LZW特殊情况：解码(2)输入：1 2 3 5 p=a 输出：a字典：索引在字典中存在：输出索引对应的词条前缀+当前词条的第一个字符字典的新词条106LZW特殊情况：解码(3)输入：-2 3 5 p=ab 输出：ab字典：107LZW特殊情况：解码(4)输入：-3 5 p=bab 输出：abab字典：108LZW特殊情况：解码(5)输入：-5 p=ab 输出：abab字典：109LZW特殊情况：解码(6)输入：-5 p=ab?输出：abab?字典

31、：110LZW特殊情况：解码(7)n第5个词条应该以 ab开始需将其加到 p 并继续解码输入：-5 p=ab?输出：abab?字典：111LZW特殊情况：解码(8)输入：-5 p=abab?输出：abab?字典：112LZW特殊情况：解码(9)输入：-5 p=ababa 输出：abab?字典：113LZW特殊情况：解码(10)输入：-p=aba 输出：abababan索引不在字典中：n前缀+前缀的的第一个字符字典的新词条n输出索引对应的词条字典：114LZW解码算法LZW译码算法可用伪码表示如下：nDictionaryj all n single-character,j=1，2，nn j

32、n+1ncW first code from CodestreamnCharstream DictionarycWnpW cWnWhile(cW next Code word)!=NULL)n If cW is in Dictionaryn Charstream DictionarycWn Prefix DictionarypWn cW first Character of DictionarycWn Dictionaryj Prefix.cWn j n+1n pW cWn elsen Prefix DictionarypWn cW first Character of Prefixn Cha

33、rstream Prefix.cWn Dictionaryj Prefix.cWn pW cWn j n+1115字典结构n字典越大，能存储更多的字符串，也就能匹配更长的字符串，但其代价是指针更长（标识需要的位数越多），搜索起来也更慢n对字典而言，最好的数据结构是树：trien 116字典结构n在编码时，编码器逐个输入字符并累积成字符串I（相当于伪代码中的Prefix）n只要在字典中能找到变量I的字符串，编码器就不断地输入字符并将其串接到I中，直到某个输入字符x与I连接后使搜索失败（字符串Ix不在字典中），然后将Ix加到字典中。n添加到字典中去的每个字符串仅有效增加了一个新字符x，即对每个不止

34、一个字符的字符串，字典中有一个比它只少一个字符的“母串”。117字典结构n用树trie表示时，树是动态建立的，且树中每个节点可能存在多个子节点。因此数据结构应该设计成一个节点可拥有任意个子节点，但无需为其预留空间：将树驻留在一个节点数组中，每个数据结构有两个字段：一个字符和指向母节点的指针n数据结构中没有指向子节点的指针，沿着树从一个节点到其子节点的操作可用一个散列过程实现，该过程把指向节点的指针和子节点的字符散列以生成一个新指针，因此需添加一个新字段：散列索引118字典结构n实用中，每个节点有3个字段：n树用数组dict表示，数组下标用pointer表示，所以dictpointer表示一个节

35、点ndictpointer.parentndictpointer.indexndictpointer.symbol119字典结构n例：字符串“ababab”(a:1 b:2)nStep 0：将从3个位置开始的所有字典位置标记为“未使用”n Step 1：将第一个字符a输入到变量I。“a”的码字为1，因此I=1。因为是第一个字符，编码器假定它已在字典中，故无需搜索nStep 2：将第二个字符b输入到J，所以J=2。编码器在字典中搜索字符串ab，执行 pointer:=hash(I,J)，假设结果为5。因为位置5仍然是空的，字段dictpointer.index标记为“未使用”，因此串ab不在字典

36、中，将其添加到字典中：ndictpointer.parent:=I;ndictpointer.index:=pointer;ndictpointer.symbol:=J;由于pointer=5，将J送入I，因此I=2。120字典结构nStep 3：将第3个字符a输入到J，所以J=1。编码器在字典中搜索字符串ba，执行 pointer:=hash(I,J)，假设结果为8。因为位置8仍然是空的，字段dictpointer.index标记为“未使用”，因此串ba不在字典中，将其添加到字典中：ndictpointer.parent:=I;ndictpointer.index:=pointer;ndic

37、tpointer.symbol:=J;由于pointer=8，将J送入I，因此I=1。nStep 4：将第4个字符b输入到J，这时J=2。编码器在字典中搜索字符串ab，执行 pointer:=hash(I,J)，由步骤2可知该结果为5。字段dictpointer.index中含有5，因此字符串ab在字典中，将指针的值送入I，因此I=5。121字典结构nStep 5：将第5个字符a输入到J，这时J=1。编码器在字典中搜索字符串aba，执行 pointer:=hash(I,J)，假定该值为8。在字段dictpointer.index中含有8，但dictpointer.parent为2，而非预期的5

38、，因此散列函数知道这是一个冲突且字符串aba不在字典第8项中。将指针+1，直到找到一个index=8且parent=5的词条或找到一个未使用的词条为止。前一种情况字符串aba在字典中，可以将其指针送入I；而后一种情况，aba不在字典中，编码器将其保存在所指的词条中，并将J送入I。122字典结构nLZW解码器所用的字典数组简单且无需散列n解码器首先将数组的前n个位置初始化为单个字符（如n=256），然后从输入流中读入一个码字，用每个指针来定位字典中的一个字符n第一步：读入第一个指针，用它检索字典的第I项，并把找到的字符I写入解码器输出流中。需要将Ix存入字典，但字符x此时仍未知，它将是下一个从字

39、典中取出的串的首字符n此后的每一步中，解码器输入下一个指针，用它从字典中取出下一个字符串J并记录到解码器输出流中。假设指针为8，则解码器检查dict8.index字段，如果它也是8，那么节点就是所要找的，否则解码器检查相继的数组位置，直到找到正确的节点123字典结构n一旦找到了所要的树节点，就利用parent字段返回到树的上层，并按相反顺序取出字符串中的单个字符，再将江这些字符按正常顺序置于J中。解码器把第一个字符x从字符串J中分离出来，并将字符串Ix存入下一个可用的数组单元中（字符串I是前面找到的，所以只需添加一个带有字符x的节点），然后解码器将J送入I，继续下一步解码n通过parent字段

40、追踪，实现对树的上行，无需散列函数124应用：compressnLZW的早期实现n自适应字典n开始字典有512词条（9比特码字）n当字典填满时，字典大小翻倍（码字长度增加1比特）n最大码字长度bmax=16n当字典达到2bmax 个词条n变成静态字典编码器n如果压缩率低于一个阈值，则重新初始化字典125应用：GIFn采用LZW机制，类似于 compress:nGIF文件定义了一个编码大小(Clear Code)，nb 比特/像素 2b 个clear codesn字典填满时，字典大小翻倍（码字长度增加1比特）n字典最大大小=4096 个词条（12比特）n对计算机合成图像和颜色小于256色的自然图像编码比较有效，而对照片类的自然图像编码效率不高126GIF 的性能127总结n字典编码技术n对文本、通讯协议等信源效率高n静态字典技术适合已知数据领域n自适应技术nLZ77：假设模式在局部重复出现nLZ78/LZW：不限于局部模式，从已观测到的信源动态构造字典n实际应用nGIF,zip，png,pdf,v.42128作业n作业：Sayood 3rd,pp.139-140n 7,8n下节课内容：n第8章：有损压缩的数学基础

展开阅读全文