实用的无失真信源编码之LZW压缩编码

1、实用的无失真信源编码实用的无失真信源编码LZWLZW压缩编码压缩编码信息理论与编码工程技术学院工程技术学院电气与电子信息系电气与电子信息系郭堃郭堃Page 2课程简介课程简介 寻找信息传输过程中的共同规律，以寻找信息传输过程中的共同规律，以提高信息传输的提高信息传输的有效性有效性、可靠性可靠性和和保密性保密性，使信息传输系统达到最优化。使信息传输系统达到最优化。 本次课内容概要本次课内容概要Page 3信源编码信源编码LZWLZW编码编码1、LZW编码思想2、LZW编码方法LZWLZW编码特点编码特点 莫尔斯电码莫尔斯电码Page 4一、信源编码一、信源编码信源编码简介信源编码简介 信源编码就

2、是把信源符号变换到码符号的一种映射。 编码的目的就是将原始数据进行压缩，达到提高通信效率的目的。 信源编码分为：无失真压缩编码和限失真压缩编码两种。Page 5常见的无失真信源编码方法常见的无失真信源编码方法“游程编码”、“霍夫曼编码”、 “算术编码”、“LZW编码”概率匹配压缩原理概率匹配压缩原理 根据信源的统计特性，用短码来代替频繁出现的原始数据，从而达到压缩的目的。 Page 6 在70年代末以前，以霍夫曼编码霍夫曼编码为代表的概率匹配压缩模型在数据压缩领域一直占据着统治地位。这类编码属于静态概率编码，需要预知原始消息的概率分布。但大多数信源的概率是很难预知，甚至概率分布是变动的。二、二

3、、LZWLZW编码编码Page 71977 年，以色列人Ziv 和 Lempel提出了全新的一个压缩技术被称为 LZ77 算法。1985年由美国人Welch在LZ77算法基础上提出LZW编码算法并进入实用阶段。它们的思路和字典颇为相似，因此，人们将基于这一思路的编码方法称作字典式字典式编码编码。其在压缩效果上大大超过了霍夫曼编码，其压缩和解压缩的速度也异常惊人，打破了霍夫曼编码一统天下的局面。Page 8LZWLZW编码实际应用编码实际应用至今，几乎我们日常使用的所有通用压缩工具最终都归结为以LZW算法为核心。（1）图像压缩：GIF、TIFF、PNG（2）计算机数据压缩：ZIP、RAR、7-Z

4、IPPage 91 1、LZWLZW编码思想编码思想绝大多数原始信息有很多重复数据，如文本文档、图片、程序代码等。如果用一些简单的编码代替这些数据，就可以实现压缩，编码与数据的对应表就是字典。基本思想基本思想：构造一个字典，将原始信息中出现的字符串，以单词的形式存储在字典中，以索引形式给出编码。解码时对根据索引，通过查字典，转换为原始信息。Page 10例如，对“Data Compression”进行编码以牛津词典为例子，查词典发现“Data”出现在第271页第13个字；“Compression”出现在第213页第8个字。Data CompressionData Compression（271

5、,13271,13）（）（213,8213,8）Page 11Data CompressionData Compression（271,13271,13）（）（213,8213,8）牛津词典共1354页，每页不超过64字，页码用11位二进制数表示，每页第几个用6位二进制数表示，则2个单词用34位数据表示。而原始数据若用8位ASCII码表示，数据为16*8=128位。压缩比为128/34=3.8倍。Page 12 LZW压缩有三个重要的对象：数据流、编码流和字典（编译表）。2 2、LZWLZW编码方法编码方法编码器编码器数据流编码流字典译码器译码器Page 13字典的产生字典的产生字典不是事先创

6、建好的，而是根据原始文件数据动态创建的。提取原始文本文件数据中的不同字符，分成一段一段。将这些段存入字典，然后用字典中段的索引来替代原始文本文件数据中的相应分段，减少原始数据大小。Page 14段号段号 短语短语编码步骤：编码步骤：（1）新建一个字典，读取第一个符号作为第一段短语存入字典；取下一符号作为新的段起点继续分段。AACDBBAACDDB1A234567ACDBBAACDDB数据流数据流0A 1C编码流编码流（2）若现有的段与字典中的短语相同时，再取紧跟后面的一个符号组成新的段，把该段作为短语存入字典。重复该过程直到编码结束。0D 0B 4A 2D 3B码字前缀的段号结束符号,对于单符号的短语，相应的段号为0。Page 15n无损压缩，适