数据压缩第4章_统计编码之二_sxq2.ppt

本章内容 4.3 算术编码 多元符号编码原理 二进制编码 二进制解码 Q(s)的确定与编码效率 算术码评述 本章内容 4.5 基于字典的编码 LZ码基本概念 LZW算法 通用编码评述 本章内容 一元码 ① 定义：非负整数n的一元码为n－1个1后跟1个0；或n－1个0后跟1个1 ② 特点： 满足惟一可译性 规则简单，生成方便 便于消除误码后的同步恢复 Golomb编码 ①特点： 无需使用霍夫曼算法，即可直接给出最佳变长码 可使服从几何分布的正整数数据链的平均码长最短 ②编码过程： Golomb编码 ②编码过程（续）： 整数n的Golomb码可由“前缀码＋尾码”组成 1977 年，以色列人 Jacob Ziv 和 Abraham Lempel 发表了论文“顺序数据压缩的一个通用算法”(A Universal Alogrithem for Sequential Data Compression)。 1978 年，他们发表了该论文的续篇“通过可变比率编码的独立序列的压缩”(Compression of Individual Sequences via Variable-Rate Coding)。 在这两篇论文中提出的两个压缩技术被称为LZ77和LZ78。 简单地说LZ码思路完全不同于从Shannon到Huffman到算术压缩的传统思路，人们将基于这一思路的编码方法称作“字典”式编码。 LZ码 字典式编码不但在压缩效果上大大超过了Huffman编码，而且易于实现，其压缩和解压缩的速度也异常惊人。 LZ编码一例 英文字母和符号串编码成12位码字的压缩字符串表。 16 0 17 00 18 000 19 0000 4095 $$$ … … 20 00001 15 空空空空空空 14 空空空空空 13 空空空空 12 空空空 11 空空 10 空 9 DO空 8 DO 7 D 6 Z 5 AD 4 AND 3 AN 2 AB 1 A 码字 符号串 表4.8 LZ码的特点 能有效地利用字符出现频率冗余度、字 符重复性和高使用率模式冗余度，但通 常不能有效地利用位置冗余度； 算法是自适应的，无需有关输入数据统 计量的先验信息，运算时间正比于消息 的长度； 对每一消息的起始端的压缩效果很差， 对整段消息压缩得更好。 如果信源非均匀且冗余度特性随消息而 变动，那么消息长度远大于算法实现的 自适应范围，压缩效率就会降低。 1984年，Terry Welch发表了名为“高性能数据压缩技术”(A Technique for High-Performance Data Compression)的论文，实现了LZ78算法的一个变种— LZW。 LZW保留了LZ码的自适应性能，压缩比也大致相同，其显著特点是逻辑简单、硬件实现廉价、运算速度快。 UNIX上出现了使用LZW算法的Compress程序，该程序性能优良，很快成为了UNIX世界的压缩程序标准。 紧随其后的是MS-DOS环境下的 ARC 程序，还有象 PKWare、PKARC 等仿制品。LZ78和LZW一时间统治了UNIX和DOS两大平台。 随后 LZW算法将输入字串映射成定长(通常为12位)的码字,其串表具有“前缀性”:表中任何一个字符串的前缀字符也在表中。 若由某个字符串ω和某个单字符K 所组成的字符串ωK 在表中，则ω 也在表中。 K 叫做前缀串ω的扩展字符。 LZW算法描述 初始化：将所有的单字符串放入串表 读第一个输入字符 ? 前缀串ω Step：读入下一个输入字符K If 没有这样的K(输入已穷尽): 码字(ω) ? 输出; 结束。 If ωK 已存在于串表中: ωK ? ω; repeat Step. else ωK不在串表中: 码字(ω) ? 输出;  ωK ? 串表; K ? ω; repeat Step. 图4.11 LZW编码算法流程 例4-12 对一个最简单的3字母字符串“ababcbababaaaaaaa”作LZW编码。 10a 11 aaa 11 11a 12 aaaa 12 1a 10 aa 10 8a