实用的无失真信源编码LZW压缩编码答案.ppt

实用的无失真信源编码 ——LZW压缩编码 信息理论与编码 工程技术学院 电气与电子信息系 郭堃 Page ? * 课程简介 寻找信息传输过程中的共同规律，以提高信息传输的有效性、可靠性和保密性，使信息传输系统达到最优化。 本次课内容概要 Page ? * 信源编码 LZW编码 1、LZW编码思想 2、LZW编码方法 LZW编码特点 莫尔斯电码 Page ? * 一、信源编码 信源编码简介 信源编码就是把信源符号变换到码符号的一种映射。 编码的目的就是将原始数据进行压缩，达到提高通信效率的目的。 信源编码分为：无失真压缩编码和限失真压缩编码两种。 Page ? * 常见的无失真信源编码方法 “游程编码”、“霍夫曼编码”、 “算术编码”、“LZW编码” 概率匹配压缩原理 根据信源的统计特性，用短码来代替频繁出现的原始数据，从而达到压缩的目的。 Page ? * 在70年代末以前，以霍夫曼编码为代表的概率匹配压缩模型在数据压缩领域一直占据着统治地位。 这类编码属于静态概率编码，需要预知原始消息的概率分布。但大多数信源的概率是很难预知，甚至概率分布是变动的。 二、LZW编码 Page ? * 1977 年，以色列人Ziv 和 Lempel提出了全新的一个压缩技术被称为 LZ77 算法。1985年由美国人Welch在LZ77算法基础上提出LZW编码算法并进入实用阶段。 它们的思路和字典颇为相似，因此，人们将基于这一思路的编码方法称作字典式编码。其在压缩效果上大大超过了霍夫曼编码，其压缩和解压缩的速度也异常惊人，打破了霍夫曼编码一统天下的局面。 Page ? * LZW编码实际应用 至今，几乎我们日常使用的所有通用压缩工具最终都归结为以LZW算法为核心。 （1）图像压缩：GIF、TIFF、PNG （2）计算机数据压缩：ZIP、RAR、7-ZIP Page ? * 1、LZW编码思想 绝大多数原始信息有很多重复数据，如文本文档、图片、程序代码等。如果用一些简单的编码代替这些数据，就可以实现压缩，编码与数据的对应表就是字典。 基本思想：构造一个字典，将原始信息中出现的字符串，以单词的形式存储在字典中，以索引形式给出编码。解码时对根据索引，通过查字典，转换为原始信息。 Page ? * 例如，对“Data Compression”进行编码 以牛津词典为例子，查词典发现“Data”出现在第271页第13个字；“Compression”出现在第213页第8个字。 Data Compression （271,13）（213,8） Page ? * Data Compression （271,13）（213,8） 牛津词典共1354页，每页不超过64字，页码用11位二进制数表示，每页第几个用6位二进制数表示，则2个单词用34位数据表示。而原始数据若用8位ASCII码表示，数据为16*8=128位。压缩比为128/34=3.8倍。 Page ? * LZW压缩有三个重要的对象：数据流、编码流和字典（编译表）。 2、LZW编码方法 编码器 数据流 编码流 字典 译码器 Page ? * 字典的产生 字典不是事先创建好的，而是根据原始文件数据动态创建的。提取原始文本文件数据中的不同字符，分成一段一段。将这些段存入字典，然后用字典中段的索引来替代原始文本文件数据中的相应分段，减少原始数据大小。 Page ? * 段号 短语 编码步骤： （1）新建一个字典，读取第一个符号作为第一段短语存入字典；取下一符号作为新的段起点继续分段。 A A C D B B A A C D D B 1 A 2 3 4 5 6 7 AC D B BA ACD DB 数据流 0A 1C 编码流 （2）若现有的段与字典中的短语相同时，再取紧跟后面的一个符号组成新的段，把该段作为短语存入字典。重复该过程直到编码结束。 0D 0B 4A 2D 3B 码字＝前缀的段号＋结束符号,对于单符号的短语，相应的段号为0。 Page ? * 无损压缩，适合压缩文本和程序代码 压缩率高，在无损压缩方法中出类拔萃 不需要预先扫描数据 对反复使用具有相同文字记录和图形的文件很有效 Page ? * 三、LZW编码特点 谢谢各位！