第五课字典编码.ppt

第五章 字典编码 迄今为止，我们大多假设符号是独立的 但这对许多常见数据类型来说是不对的 如：文本、图像和源代码文件 基本思想 标识经常出现的符号模式—保存于字典中 对这些常出现的模式采用更有效的编码方式—用其在字典中的索引作为码字 而对其它部分采用缺省（不太有效）的编码方式 以期总的编码效率更高 注意 这对如文本这样的信源是合理的 显然对（接近）随机数据不会有效 例 考虑某英文文本信源 26 字母和6个标点符号 单字符，定长码 5 比特/字符 4字符模式，定长码 20比特/模式 (324 = 220 = 1,048,576) 假设为非均匀分布 字典：256个最常出现的模式，每个用8比特编码 对其它模式用20比特编码 再增加1比特用于指示是上述两种情况中的哪种 例 (2) 若用p 表示使用字典的概率，则比特率为 R = 9p + 21(1-p) = 21 - 12p 压缩 = 21 - 12p 20 = p 0.084 还不太坏 在等概率假设下，p = 0.00025 p越大，性能越好 ? 选择最可能出现的模式存于字典中 为了达到好的性能，需要知道信源的结构信息 有足够的先验信息，? 静态字典 否则，在编码过程中获得信源的知识 ? 自适应字典 静态字典 静态字典 对信源的结构有足够的先验知识时，利用先验知识构造字典 对特定应用特别有效 只对针对其设计的特定应用和数据有效 例：电话号码的区号 例：学校的学生信息表 自适应字典 有许多场合，开始时不知道要编码数据的统计特性，也不一定允许事先知道它们的统计特性。 字典编码的思路：根据数据本身包含有重复代码的特性 例：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮 如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是字典。 实用的字典编码算法的核心就是如何动态地形成字典，以及如何选择输出格式以减小冗余。 自适应字典 开始 Jacob Ziv / Abraham Lempel 1977 (LZ77/LZ1), 1978 (LZ78/LZ2) 1984 Terry Welch (LZW) LZ77 vs. LZ78 两种不同的方法 有很多变种 是很多主流压缩的基础 LZ77 基本方法：字典为先前已编码序列的一部分 有哪些信誉好的足球投注网站缓冲区为当前字典，通常为几千字节 机制：滑动窗口 有哪些信誉好的足球投注网站缓冲区( Search buffer)、前向（look ahead）缓冲区、有哪些信誉好的足球投注网站指针(search pointer) 目标：在有哪些信誉好的足球投注网站缓冲区中，寻找与有哪些信誉好的足球投注网站指针指向的字符串匹配的最长串，并对其进行编码 基本原理：如果某些模式在局部重复出现，能得到更有效的表示 LZ77 (2) (o)ffset = search ptr - match ptr = 7 (l)ength = 连续匹配的字符数 = 4 (c)odeword = C(‘r’) 编码 o, l, c = 7, 4, C(‘r’) If |search buff| = S, |A| = A, S + |LA buff| = W 定长码：?log2S? + ?log2W? + ?log2A? LZ77 编码举例 序列 cabracadabrarrarrad W = 13, S = 7 |cabraca|dabrar|rarrad 对d，没有匹配的字符串 发送 0, 0, C(d) (可以做得更好?) |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad |abracad|abrarr|rarrad 发送 7, 4, C(r) LZ77 编码举例 (2) |cadabrar|rarrad| |cadabrar|rarrad| |cadabrar|rarrad| 发送 3, 3, C(r) 可以做得更好? 发送 3, 5, C(d)! 总结：三种情况 没有匹配 匹配 匹配串超过了有哪些信誉好的足球投注网站缓冲区 LZ77 解码举例 输入 0, 0, C(d) 7, 4, C(r) 3, 5, C(d) 输出 cabraca 解码：0, 0, C(d) 增加一个 ‘d’: c|abracad| 解码： 7, 4, C(r) 从第一个‘a’开始，拷贝4个字母，解码C(r) cabrac|adabrar| 解码： 3, 5, C(d) 从第一个‘r’开始，拷贝3个字母 cabracada|brarrar| 再拷贝2个字母 cabracadabr|arrarar| 解码C(d)：cabracadabrarrarard LZ77编码小结 使用固定大小窗口进行词语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往