第五章字典编码.ppt
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《第五章字典编码.ppt》由会员分享,可在线阅读,更多相关《第五章字典编码.ppt(128页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第五章 字典编码n迄今为止,我们大多假设符号是独立的n但这对许多常见数据类型来说是不对的n如:文本、图像和源代码文件n基本思想n标识经常出现的符号模式保存于字典中n对这些常出现的模式采用更有效的编码方式用其在字典中的索引作为码字n而对其它部分采用缺省(不太有效)的编码方式n以期总的编码效率更高n注意n这对如文本这样的信源是合理的n显然对(接近)随机数据不会有效1例n考虑某英文文本信源n26 字母和6个标点符号n单字符,定长码n5 比特/字符n4字符模式,定长码n20比特/模式(324=220=1,048,576)n假设为非均匀分布n字典:256个最常出现的模式,每个用8比特编码n对其它模式用2
2、0比特编码n再增加1比特用于指示是上述两种情况中的哪种2例(2)n若用p 表示使用字典的概率,则比特率为R=9p+21(1-p)=21-12pn压缩 21-12p p 0.084n还不太坏n在等概率假设下,p=0.00025n p越大,性能越好 选择最可能出现的模式存于字典中n为了达到好的性能,需要知道信源的结构信息n有足够的先验信息,静态字典n否则,在编码过程中获得信源的知识 自适应字典3静态字典n静态字典n对信源的结构有足够的先验知识时,利用先验知识构造字典n对特定应用特别有效n只对针对其设计的特定应用和数据有效n例:电话号码的区号n例:学校的学生信息表地地 区区长途区号长途区号北京市北京
3、市 010010上海市上海市021021天津市天津市022022重庆市重庆市023023沈阳市沈阳市024024南京市南京市025025乌鲁木齐市乌鲁木齐市09910991喀什市喀什市 09980998 4自适应字典n有许多场合,开始时不知道要编码数据的统计特性,也不一定允许事先知道它们的统计特性。n字典编码的思路:根据数据本身包含有重复代码的特性n例:吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮n如果用一些简单的代号代替这些字符串,就可以实现压缩,实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。n实用的字典编码算法的核心就是如何动态地形成字典,以及如何选择输出格式以减小冗余。5自
4、适应字典n开始nJacob Ziv/Abraham Lempeln1977(LZ77/LZ1),1978(LZ78/LZ2)n1984 Terry Welch(LZW)nLZ77 vs.LZ78n两种不同的方法n有很多变种n是很多主流压缩的基础6LZ77n基本方法:字典为先前已编码序列的一部分n搜索缓冲区为当前字典,通常为几千字节n机制:滑动窗口n搜索缓冲区(Search buffer)、前向(look ahead)缓冲区、搜索指针(search pointer)n目标:在搜索缓冲区中,寻找与搜索指针指向的字符串匹配的最长串,并对其进行编码n基本原理:如果某些模式在局部重复出现,能得到更有效的
5、表示7LZ77(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|=Wn定长码:log2S+log2W+log2ASearch pointer8LZ77 编码举例n序列ncabracadabrarrarradnW=13,S=7n|cabraca|dabrar|rarradn对d,没有匹配的字符串n发送 (可以做得更好?)n|abracad|abrarr|rarrad|abracad|abrarr|rarrad|abracad
6、|abrarr|rarrad|abracad|abrarr|rarradn发送 9LZ77 编码举例(2)n|cadabrar|rarrad|cadabrar|rarrad|cadabrar|rarrad|n发送 n可以做得更好?n发送!n总结:三种情况n没有匹配n匹配n匹配串超过了搜索缓冲区10LZ77 解码举例 n输入n n输出ncabracan解码:n增加一个 d:c|abracad|n解码:n从第一个a开始,拷贝4个字母,解码C(r)cabrac|adabrar|n解码:n从第一个r开始,拷贝3个字母 cabracada|brarrar|n再拷贝2个字母cabracadabr|arra
7、rar|n解码C(d):cabracadabrarrarard11LZ77编码小结n使用固定大小窗口进行词语匹配,而不是在所有已经编码的信息中匹配,是因为匹配算法的时间消耗往往很多,必须限制词典的大小才能保证算法的效率;n随着压缩的进程滑动词典窗口,使其中总包含最近编码过的信息,是因为对大多数信息而言,要编码的字符串往往在最近的上下文中更容易找到匹配串。nLZ77解码器比编码器简单得多(非对称压缩)n维持一个与编码器窗口大小相同的缓冲区,并在缓冲区中找出匹配串,将匹配串及第3个字段的字符写入输出流,同时移进缓冲区n在如文件压缩(一次压缩,多次还原)的场合很有用12LZ77的变种n迄今为止n自适
8、应模型,没有先验知识n渐近 接近知道信源统计知识的情况n但是,局部性起到了很大作用n改进n变长编码noffset:各数值基本均匀分布,一般用定长码nlength:可用Huffman码/Golomb码/Exp-Golomb码nPKZip,Zip,Lharcm ONG,gzip,ARJn可变缓冲区大小n需设计较完善的数据结构来实现对大缓冲区的快速搜索nLZSS:搜索缓冲区(字典)用对分查找树保持,前向缓冲区用循环队列表示n取消 nLZSS:只需增加1一个标记位,用于指示是否为单字符13LZ78nLZ77假设模式满足局部性nLZ78:n没有搜索缓冲区代之以显式的字典n编码器/解码器必须同步建立字典n
9、 如没有匹配,将字典原有词条+当前没有匹配的字符 字典的新词条n编码:ni=字典索引n同LZ77,i=0 表示在字典中没有找到匹配的词条nc=下一字符的码字14LZ78举例索引索引条目条目字典:输入:wabbawabbawabbawabbawoowoowoo输出:15LZ78举例(2)索引索引条目条目1 1w w字典:输入:wabbawabbawabbawabbawoowoowoo输出:16LZ78举例(3)索引索引条目条目1 1w w2 2a a字典:输入:-abbawabbawabbawabbawoowoowoo输出:17LZ78举例(4)索引索引条目条目1 1w w2 2a a3 3b
10、b字典:输入:-bbawabbawabbawabbawoowoowoo输出:18LZ78举例(5)索引索引条目条目1 1w w2 2a a3 3b b4 4baba字典:输入:-bawabbawabbawabbawoowoowoo输出:19LZ78举例(6)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 字典:输入:-wabbawabbawabbawoowoowoo输出:20LZ78举例(7)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa字典:输入:-wabbawabbawabbawoowoowoo输出:21LZ78举例(8)
11、索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb字典:输入:-bbawabbawabbawoowoowoo输出:22LZ78举例(9)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 字典:输入:-a wabbawabbawoowoowoo输出:23LZ78举例(10)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab字典:输入:-wabbawabbawoowoowoo输出:24LZ78举例(
12、11)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 字典:输入:-ba wabbawoowoowoo输出:25LZ78举例(12)索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 字典:输入:-wabbawoowoowoo输出:1111wabbwabb26LZ78举例(13)字典:输入:-a woowoowoo输出:1111wabbwabb1212a a w w索引索引条目条目1 1w w
13、2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 27LZ78举例(14)字典:输入:-oowoowoo输出:1111wabbwabb1212a a w w1313o o索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 28LZ78举例(15)字典:输入:-o woowoo输出:1111wabbwabb1212a a w w1313o o1414o o 索引索引条目条目1 1w w2 2a a3 3b b4 4baba5
14、 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 29LZ78举例(16)字典:输入:-woowoo输出:1111wabbwabb1212a a w w1313o o1414o o 1515wowo索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 30LZ78举例(17)字典:输入:-o woo输出:1111wabbwabb1212a a w w1313o o1414o o 1515wowo1616o o w w索引索引条目条目1 1w w2 2a a3 3b
15、 b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 31LZ78举例(18)字典:输入:-oo输出:1111wabbwabb1212a a w w1313o o1414o o 1515wowo1616o o w w1717oooo索引索引条目条目1 1w w2 2a a3 3b b4 4baba5 5 6 6wawa7 7bbbb8 8a a 9 9wabwab1010baba 32LZ78n观察:如果继续编码,字典将继续增长n实用的选择n停止增长字典n相当于从此成为一个静态字典策略n删除一些较早用过的项n如基于使用统计(但还没有好的算法决定
16、哪些项该删)n将字典全部删除,从空字典开始重建字典n如果没有信源的特定知识,任何方法可能都不会工作得很好!33LZ78的变种:LZWnTerry Welch(1984)n基本思想:n只对i编码,而不是编码 n算法:n/初始化字典为包含所有字母 Seed dictionary with all alphabet letters,p=null while(!done)a=get_next_symbolif(p a)is in dictionary /在字典中,继续用更长的字符串匹配p=p aelsesend out index of p /不在字典中,输出已匹配部分,从a 重新开始p.a is a
17、dded to dictionary p=aendwhile34LZW编码索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 67 78 89 91010字典:输出:输入:wabbawabbawabbawabbawoowoowoop=35LZW编码(2)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 67 78 89 91010字典:输出:输入:wabbawabbawabbawabbawoowoowoop=w 36LZW编码(3)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 78 89 91010字
18、典:输出:5(w)输入:-abbawabbawabbawabbawoowoowoop=wa37LZW编码(4)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 89 91010字典:输出:5(w)2(a)输入:-bbawabbawabbawabbawoowoowoop=ab38LZW编码(5)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 91010字典:输出:5(w)2(a)3(b)输入:-bawabbawabbawabbawoowoowoop=bb39LZW编码(6)
19、索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010字典:输出:5(w)2(a)3(b)3(b)输入:-awabbawabbawabbawoowoowoop=ba40LZW编码(7)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)输入:-wabbawabbawabbawoowoowoop=a41LZW编码(8)索引索引条目条目1 1 2 2a a3 3b b4 4o
20、 o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)1()输入:-wabbawabbawabbawoowoowoo索引索引条目条目1111 w w121213131414151516161717181819192020p=w42LZW编码(9)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)1()输入:-abbawabbawabbawoowoowoo索引索引条目
21、条目1111 w w121213131414151516161717181819192020p=wa43LZW编码(10)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)1()6(wa)输入:-bbawabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab13131414151516161717181819192020p=wab44LZW编码(11)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5
22、w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)1()6(wa)输入:-bawabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab13131414151516161717181819192020p=bb45LZW编码(12)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)输入:-a wabbawabbawo
23、owoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414151516161717181819192020p=bba46LZW编码(13)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)输入:-wabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414151516161717181819192020p=a47LZW编码(14)索
24、引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)输入:-wabbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w151516161717181819192020p=aw48LZW编码(15)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输
25、出:5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)输入:-abbawabbawoowoowoo索引索引条目条目1111 w w1212wabwab1313bbabba1414a a w w151516161717181819192020p=wa49LZW编码(16)索引索引条目条目1 1 2 2a a3 3b b4 4o o5 5w w6 6wawa7 7abab8 8bbbb9 9baba1010a a 字典:输出:5(w)2(a)3(b)3(b)2(a)1()6(wa)8(bb)10(a)输入:-bbawabbawoowoowoo索引索引条目条目1111 w
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 字典 编码
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内