五章字典编码.ppt
《五章字典编码.ppt》由会员分享,可在线阅读,更多相关《五章字典编码.ppt(128页珍藏版)》请在三一文库上搜索。
1、1,第五章 字典编码,迄今为止,我们大多假设符号是独立的 但这对许多常见数据类型来说是不对的 如:文本、图像和源代码文件 基本思想 标识经常出现的符号模式保存于字典中 对这些常出现的模式采用更有效的编码方式用其在字典中的索引作为码字 而对其它部分采用缺省(不太有效)的编码方式 以期总的编码效率更高 注意 这对如文本这样的信源是合理的 显然对(接近)随机数据不会有效,2,例,考虑某英文文本信源 26 字母和6个标点符号 单字符,定长码 5 比特/字符 4字符模式,定长码 20比特/模式 (324 = 220 = 1,048,576) 假设为非均匀分布 字典:256个最常出现的模式,每个用8比特编
2、码 对其它模式用20比特编码 再增加1比特用于指示是上述两种情况中的哪种,3,例 (2),若用p 表示使用字典的概率,则比特率为 R = 9p + 21(1-p) = 21 - 12p 压缩 21 - 12p p 0.084 还不太坏 在等概率假设下,p = 0.00025 p越大,性能越好 选择最可能出现的模式存于字典中 为了达到好的性能,需要知道信源的结构信息 有足够的先验信息, 静态字典 否则,在编码过程中获得信源的知识 自适应字典,4,静态字典,静态字典 对信源的结构有足够的先验知识时,利用先验知识构造字典 对特定应用特别有效 只对针对其设计的特定应用和数据有效 例:电话号码的区号 例
3、:学校的学生信息表,5,自适应字典,有许多场合,开始时不知道要编码数据的统计特性,也不一定允许事先知道它们的统计特性。 字典编码的思路:根据数据本身包含有重复代码的特性 例:吃葡萄不吐葡萄皮,不吃葡萄倒吐葡萄皮 如果用一些简单的代号代替这些字符串,就可以实现压缩,实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。 实用的字典编码算法的核心就是如何动态地形成字典,以及如何选择输出格式以减小冗余。,6,自适应字典,开始 Jacob Ziv / Abraham Lempel 1977 (LZ77/LZ1), 1978 (LZ78/LZ2) 1984 Terry Welch (LZW
4、) LZ77 vs. LZ78 两种不同的方法 有很多变种 是很多主流压缩的基础,7,LZ77,基本方法:字典为先前已编码序列的一部分 搜索缓冲区为当前字典,通常为几千字节 机制:滑动窗口 搜索缓冲区( Search buffer)、前向(look ahead)缓冲区、搜索指针(search pointer) 目标:在搜索缓冲区中,寻找与搜索指针指向的字符串匹配的最长串,并对其进行编码 基本原理:如果某些模式在局部重复出现,能得到更有效的表示,8,LZ77 (2),(o)ffset = search ptr - match ptr = 7 (l)ength = 连续匹配的字符数 = 4 (c)
5、odeword = C(r) 编码 = If |search buff| = S, |A| = A, S + |LA buff| = W 定长码:log2S + log2W + log2A,Search pointer,9,LZ77 编码举例,序列 cabracadabrarrarrad W = 13, S = 7 |cabraca|dabrar|rarrad 对d,没有匹配的字符串 发送 (可以做得更好?) |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad 发
6、送 ,10,LZ77 编码举例 (2),|cadabrar|rarrad| |cadabrar|rarrad| |cadabrar|rarrad| 发送 可以做得更好? 发送 ! 总结:三种情况 没有匹配 匹配 匹配串超过了搜索缓冲区,11,LZ77 解码举例,输入 输出 cabraca 解码: 增加一个 d: c|abracad| 解码: 从第一个a开始,拷贝4个字母,解码C(r) cabrac|adabrar| 解码: 从第一个r开始,拷贝3个字母 cabracada|brarrar| 再拷贝2个字母 cabracadabr|arrarar| 解码C(d):cabracadabrarrar
7、ard,12,LZ77编码小结,使用固定大小窗口进行词语匹配,而不是在所有已经编码的信息中匹配,是因为匹配算法的时间消耗往往很多,必须限制词典的大小才能保证算法的效率; 随着压缩的进程滑动词典窗口,使其中总包含最近编码过的信息,是因为对大多数信息而言,要编码的字符串往往在最近的上下文中更容易找到匹配串。 LZ77解码器比编码器简单得多(非对称压缩) 维持一个与编码器窗口大小相同的缓冲区,并在缓冲区中找出匹配串,将匹配串及第3个字段的字符写入输出流,同时移进缓冲区 在如文件压缩(一次压缩,多次还原)的场合很有用,13,LZ77的变种,迄今为止 自适应模型,没有先验知识 渐近 接近知道信源统计知识
8、的情况 但是,局部性起到了很大作用 改进 变长编码 offset: 各数值基本均匀分布,一般用定长码 length: 可用Huffman码/Golomb码/Exp-Golomb码 PKZip, Zip, Lharcm ONG, gzip, ARJ 可变缓冲区大小 需设计较完善的数据结构来实现对大缓冲区的快速搜索 LZSS:搜索缓冲区(字典)用对分查找树保持,前向缓冲区用循环队列表示 取消 LZSS:只需增加1一个标记位,用于指示是否为单字符,14,LZ78,LZ77假设模式满足局部性 LZ78: 没有搜索缓冲区代之以显式的字典 编码器/解码器必须同步建立字典 如没有匹配,将字典原有词条+当前没
9、有匹配的字符 字典的新词条 编码: i = 字典索引 同LZ77,i=0 表示在字典中没有找到匹配的词条 c = 下一字符的码字,15,LZ78举例,字典:,输入:wabbawabbawabbawabbawoowoowoo,输出:,16,LZ78举例 (2),字典:,输入: wabbawabbawabbawabbawoowoowoo,输出: ,17,LZ78举例 (3),字典:,输入: -abbawabbawabbawabbawoowoowoo,输出: ,18,LZ78举例 (4),字典:,输入: -bbawabbawabbawabbawoowoowoo,输出: ,19,LZ78举例 (5),
10、字典:,输入: -bawabbawabbawabbawoowoowoo,输出: ,20,LZ78举例 (6),字典:,输入: -wabbawabbawabbawoowoowoo,输出: ,21,LZ78举例 (7),字典:,输入: -wabbawabbawabbawoowoowoo,输出: ,22,LZ78举例 (8),字典:,输入: -bbawabbawabbawoowoowoo,输出: ,23,LZ78举例 (9),字典:,输入: -awabbawabbawoowoowoo,输出: ,24,LZ78举例 (10),字典:,输入: -wabbawabbawoowoowoo,输出: ,25,L
11、Z78举例 (11),字典:,输入: -bawabbawoowoowoo,输出: ,26,LZ78举例 (12),字典:,输入: -wabbawoowoowoo,输出: ,27,LZ78举例 (13),字典:,输入: -awoowoowoo,输出: ,28,LZ78举例 (14),字典:,输入: -oowoowoo,输出: ,29,LZ78举例 (15),字典:,输入: -owoowoo,输出: ,30,LZ78举例 (16),字典:,输入: -woowoo,输出: ,31,LZ78举例 (17),字典:,输入: -owoo,输出: ,32,LZ78举例 (18),字典:,输入: -oo,输出
12、: ,33,LZ78,观察:如果继续编码,字典将继续增长 实用的选择 停止增长字典 相当于从此成为一个静态字典策略 删除一些较早用过的项 如基于使用统计(但还没有好的算法决定哪些项该删) 将字典全部删除,从空字典开始重建字典 如果没有信源的特定知识,任何方法可能都不会工作得很好!,34,LZ78的变种:LZW,Terry Welch (1984) 基本思想: 只对i编码,而不是编码 算法: /初始化字典为包含所有字母 Seed dictionary with all alphabet letters, p = null while( !done) a = get_next_symbol if(
13、 p a) is in dictionary /在字典中,继续用更长的字符串匹配 p = p a else send out index of p /不在字典中,输出已匹配部分,从a 重新开始 p.a is added to dictionary p = a endwhile,35,LZW编码,字典:,输出:,输入: wabbawabbawabbawabbawoowoowoo,p =,36,LZW编码(2),字典:,输出:,输入: wabbawabbawabbawabbawoowoowoo,p = w,37,LZW编码(3),字典:,输出: 5 (w),输入: -abbawabbawabbaw
14、abbawoowoowoo,p = wa,38,LZW编码(4),字典:,输出: 5 (w) 2 (a),输入: -bbawabbawabbawabbawoowoowoo,p = ab,39,LZW编码(5),字典:,输出: 5 (w) 2 (a) 3 (b),输入: -bawabbawabbawabbawoowoowoo,p = bb,40,LZW编码(6),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b),输入: -awabbawabbawabbawoowoowoo,p = ba,41,LZW编码 (7),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (
15、a),输入: -wabbawabbawabbawoowoowoo,p = a,42,LZW编码 (8),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 (),输入: -wabbawabbawabbawoowoowoo,p = w,43,LZW编码 (9),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 (),输入: -abbawabbawabbawoowoowoo,p = wa,44,LZW编码 (10),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa),输入: -bbawabba
16、wabbawoowoowoo,p = wab,45,LZW编码 (11),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa),输入: -bawabbawabbawoowoowoo,p = bb,46,LZW编码 (12),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb),输入: -awabbawabbawoowoowoo,p = bba,47,LZW编码 (13),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb),输入:
17、 -wabbawabbawoowoowoo,p = a,48,LZW编码 (14),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb) 10 (a),输入: -wabbawabbawoowoowoo,p = aw,49,LZW编码 (15),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb) 10 (a),输入: -abbawabbawoowoowoo,p = wa,50,LZW编码 (16),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1
18、 () 6 (wa) 8 (bb) 10 (a),输入: -bbawabbawoowoowoo,p = wab,51,LZW编码 (17),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb) 10 (a) 12 (wab),输入: -bawabbawoowoowoo,p = wabb,52,LZW编码 (18),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb) 10 (a) 12 (wab),输入: -awabbawoowoowoo,p = ba,53,LZW编码 (1
19、9),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb) 10 (a) 12 (wab) 9 (ba),输入: -wabbawoowoowoo,p = ba,54,LZW编码 (20),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb) 10 (a) 12 (wab) 9 (ba),输入: -wabbawoowoowoo,p = w,55,LZW编码 (21),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb)
20、 10 (a) 12 (wab) 9 (ba) 11 (w),输入: -abbawoowoowoo,p = wa,56,LZW编码 (22),字典:,输出: 5 (w) 2 (a) 3 (b) 3 (b) 2 (a) 1 () 6 (wa) 8 (bb) 10 (a) 12 (wab) 9 (ba) 11 (w),输入: -bbawoowoowoo,p = ab,57,LZW编码 (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),输入: -bawo
21、owoowoo,p = abb,58,LZW编码 (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),输入: -awoowoowoo,p = ba,59,LZW编码 (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),输入: -woowoowoo,p = ba,60,LZW编码 (26),字典:,输出: 5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 字典 编码
链接地址:https://www.31doc.com/p-3223510.html