第4章无损数据压缩 冰水水冰本水冰水水水冰水水水本水冰本客*冰水水水水冰本水冰水水水水水水冰本冰客水冰水水水冰客水冰本水水水水水冰水水冰本水冰水水水水水水水*客 4.1仙农-范诺与赫夫曼编码 4.1.1仙农-范诺编码 4.1.2赫夫曼编码 4.2算术编码 4.3RLE编码 4.4词典编码 4.4.1词典编码的思想 4.4.2LZ77算法 4.4.3LZSS算法 4.4.4LZ78算法 4.4.5LZW算法 练习与思考题 参考文献和站点 水冰水水求水水水冰客水水水水水水水水本水水水水水水水客*客水水水水冰水水水水水水水客水水水水水冰水客水水水水水水冰*水水水水水水半水*水水冰水 数据压缩可分成两种类型,一种叫做无损压缩,另一种叫做有损压缩 无损压缩是指使用压缩后的数据进行重构(或者叫做还原,解压缩),重构后的数据与原 来的数据完全相同;无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见 的例子是磁盘文件的压缩。根据目前的技术水平,无损压缩算法一般可以把普通文件的数据 压缩到原来的1/2~1/4。一些常用的无损压缩算法有赫夫曼( Huffman)算法和 LZW( Lengel-Ziv& Welch)压缩算法 有损压缩是指使用压缩后的数据进行重构,重构后的数据与原来的数据有所不同,但不 影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完 全相同的场合。例如,图像和声音的压缩就可以采用有损压缩,因为其中包含的数据往往多 于我们的视觉系统和听觉系统所能接收的信息,丢掉一些数据而不至于对声音或者图像所表 达的意思产生误解,但可大大提高压缩比。 本章主要介绍目前用得最多和技术最成熟的无损压缩编码技术,包括包含赫夫曼编码、 算术编码、RLE编码和词典编码。对于不打算开发压缩技术和编写压缩程序的读者可不必深 究编译码的详细过程。 4.1仙农-范诺与赫夫曼编码 4.1.1仙农-范诺编码 仙农-范诺编码算法需要用到下面两个基本概念: 1. Entropy(熵)的概念 (1)熵是信息量的度量方法,它表示某一事件出现的消息越多,事件发生的可能性就 越小,数学上就是概率越小 2)某个事件的信息量用J1=-bog2P1表示,其中P,为第i个事件的概率, p 2.信源S的熵的定义 按照仙农( Shannon)的理论,信源S熵定义为 H(s)=7=∑pbog2(l/P) 其中P是符号S在出现的概率;bog2(/p1)表示包含在S中的信息量,也就是编码s所 需要的位数。例如,一幅用256级灰度表示的图像,如果每一个像素点灰度的概率均为 P1=1/256,编码每一个像素点就需要8比特。第4章 无损数据压缩 *************************************************************************** 4.1 仙农-范诺与赫夫曼编码 4.1.1 仙农-范诺编码 4.1.2 赫夫曼编码 4.2 算术编码 4.3 RLE编码 4.4 词典编码 4.4.1 词典编码的思想 4.4.2 LZ77算法 4.4.3 LZSS算法 4.4.4 LZ78算法 4.4.5 LZW算法 练习与思考题 参考文献和站点 *************************************************************************** 数据压缩可分成两种类型，一种叫做无损压缩，另一种叫做有损压缩。 无损压缩是指使用压缩后的数据进行重构(或者叫做还原，解压缩)，重构后的数据与原 来的数据完全相同；无损压缩用于要求重构的信号与原始信号完全一致的场合。一个很常见 的例子是磁盘文件的压缩。根据目前的技术水平，无损压缩算法一般可以把普通文件的数据 压缩到原来的 1/2 ～ 1/4 。一些常用的无损压缩算法有赫夫曼 (Huffman) 算法和 LZW(Lenpel-Ziv & Welch)压缩算法。 有损压缩是指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不 影响人对原始资料表达的信息造成误解。有损压缩适用于重构信号不一定非要和原始信号完 全相同的场合。例如，图像和声音的压缩就可以采用有损压缩，因为其中包含的数据往往多 于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表 达的意思产生误解，但可大大提高压缩比。 本章主要介绍目前用得最多和技术最成熟的无损压缩编码技术，包括包含赫夫曼编码、 算术编码、RLE编码和词典编码。对于不打算开发压缩技术和编写压缩程序的读者可不必深 究编译码的详细过程。 4.1 仙农-范诺与赫夫曼编码 4.1.1 仙农-范诺编码 仙农-范诺编码算法需要用到下面两个基本概念： 1. Entropy(熵)的概念 (1) 熵是信息量的度量方法，它表示某一事件出现的消息越多，事件发生的可能性就 越小，数学上就是概率越小。 (2) 某个事件的信息量用 i pi I 2 = −log 表示 ， 其中 i p 为第 i 个事件的概率， 0  pi 1 2. 信源S的熵的定义 按照仙农(Shannon)的理论，信源S的熵定义为 ( ) log (1/ ) 2 i i H s = =  pi p 其中 i p 是符号 i s 在S中出现的概率； log (1/ ) 2 pi 表示包含在 i s 中的信息量，也就是编码 i s 所 需要的位数。例如，一幅用256级灰度表示的图像，如果每一个像素点灰度的概率均为 pi =1/ 256 ，编码每一个像素点就需要8比特