第五讲无损数据压缩

1、第五讲无损数据压缩 压缩技术简史压缩技术简史 压缩技术基础压缩技术基础 Huffman编码编码 算术编码算术编码 LZ77和和LZW算法算法 JPEG算法算法 通用压缩工具比较通用压缩工具比较 第五讲无损数据压缩 压缩编码分类（信息） 无损压缩无损压缩 指使用压缩后的数据进行重构(或者叫做还原，解压缩)， 重构后的数据与原来的数据完全相同。 无损压缩算法一般压缩比24。 常用的无损压缩算法有霍夫曼(Huffman)算法和 LZW(Lenpel-Ziv & Welch)压缩算法。 有损压缩有损压缩 指使用压缩后的数据进行重构，重构后的数据与原来 的数据有所不同，但不影响人对原始资料表达的信息 造

2、成误解。 图像和声音的压缩就可以采用有损压缩，因为其中包 含的数据往往多于我们的视觉系统和听觉系统所能接 收的信息，丢掉一些数据而不至于对声音或者图像所 表达的意思产生误解，但可大大提高压缩比。 第五讲无损数据压缩 第五讲无损数据压缩 压缩技术的应用 电报、传真(CCITT) 通讯(Modem/网络协议) 存储(压缩池) 文件系统(压缩扇区) 图像(GIF/TIFF/JPEG) 音频(MP3) 视频(MPEG/RM) 数据库(B+树) 归档(TAR/ZIP) 密码学(消除数据的原始特征) 全文索引(倒排索引表) 编译(JAVA) 程序设计(算法/空间和时间效率) 人工智能(专家系统/知识树)

3、第五讲无损数据压缩 压缩编码分类（原理） 预测编码：PCM，DPCM，DM，LPC 统计编码：huffman，shannon，REL，词 典编码 模型编码 变换编码 子带编码 第五讲无损数据压缩 压缩编码分类（长度） 等长编码等长编码 ASCII编码编码 不等长编码不等长编码 编码长度是不等长的编码长度是不等长的 常见编码如常见编码如Huffman编码编码 第五讲无损数据压缩 等长与不等长编码 例如：符号序列x=“aa bb cccc dddd eeeeeeee 采用ASCII编码： a=01100001 b=01100010 c=01100011 d=01100100 e=01100101

4、空=00100000 等长编码：24*8=192bit 如用后3位进行编码 只需要3*24=72bit 压缩比为：压缩比为： 第五讲无损数据压缩 等长与不等长编码 不等长编码方法 字符 次数 概率 码字 字长 E81/301 D41/61003 C41/61013 空41/61103 A21/12 1110 4 B21/12 1111 4 需要空间： 1*8+3*4+3*4 +3*4+2*4+2* 4=60 平均码长平均码长=总 位数/字符出 现次数 =60/24=2.5 第五讲无损数据压缩 不等长码唯一性问题 字符码1码2码3 A000 B101001 C11011011 D1110 011

5、11 对序列010110译码 码1abc 码2daca或ddb或abca 第五讲无损数据压缩 压缩技术起源 信息压缩技术的起源 比计算机的发明早几千年 第五讲无损数据压缩 信息论 信息存在冗余信息存在冗余 通过采用一定通过采用一定 的模型和编码方法，的模型和编码方法， 可以降低这种冗余度可以降低这种冗余度 贝尔实验室的 Claude Shannon 和 MIT 的 R.M.Fano 几乎同时提出了最早的对符号进行有效编码 从而实现数据压缩的 Shannon-Fano 编码方法。 第五讲无损数据压缩 D.A.Huffman 1952 年 发表论文：“最小冗余度代码的构造方法” A Method

6、for the Construction of Minimum Redundancy Codes UNIX 系统上一个不太为现代人熟知的压缩程序 COMPACT 就是 Huffman 0 阶自适应编码的具体实现 80 年代初，Huffman 编码又在 CP/M 和 DOS 系统 中实现，其代表程序叫 SQ Huffman时代：时代：60 年代、年代、70 年代乃至年代乃至 80 年代的早期年代的早期 第五讲无损数据压缩 接近极限熵 80年代早期，数学家们设计出算术编码方法(Arithmetic Coding) 可以证明，算术编码得到的压缩效果可以最大地减小 信息的冗余度，用最少量的符号精确表达

7、原始信息内容 q 但是，在同样的计算机系统上，算术编码虽然可以得到 最好的压缩效果，却要消耗也许几十倍的计算时间 算术编码是部分匹配预测(Predication by Partial matching, PPM)技术的变体 第五讲无损数据压缩 以色列人 1978 年 发表论文：“通过可变比率编码的独立序列的压缩” Compression of Individual Sequences via Variable-Rate Coding 字典编码时代：字典编码时代：LZ77和和LZ78压缩算法压缩算法 1977 年 发表论文：“顺序数据压缩的一个通用算法” A Universal Algorith

8、m for Sequential Data Compression 第五讲无损数据压缩 LZW算法 Welch 实现了 LZ78 算法的一个变种 UNIX：使用 LZW 算法的 Compress 程序 MS-DOS：ARC 程序，以及PKWare、PKARC 等仿制品。 1984 年 发表论文：“高性能数据压缩技术” A Technique for High-Performance Data Compression 第五讲无损数据压缩 通用数据压缩 80年代中期以后，对LZ77算法进行改进 Haruyasu Yoshizaki(Yoshi) 的 LHarc Robert Jung 的 ARJ

9、从PKZip到WinZip： 通用数据压缩格式标准 ZIP LZ77、LZ78、LZW 一起垄断当今的通用数据压缩领域一起垄断当今的通用数据压缩领域 第五讲无损数据压缩 多媒体数据压缩 q国际电报电话咨询委员会( CCITT ) ：针对二值图像的一系列压缩标 准，如 CCITT Group3、CCITT Group4 等 (此外还包括CCITT与ISO共 同制订的JBIG标准) 。 q70 年代末 80 年代初：数学家们提出了损失压缩精度以换取压缩损失压缩精度以换取压缩 率的崭新思路率的崭新思路。国际标准化组织( ISO )和 CCITT 联合组成了两个 委员会：静态图像联合专家小组( JPE

10、G )和动态图像联合专家小组 ( MPEG )。诞生了 JPEG、MPEG-1、MPEG-2、MPEG-4、MPEG-7 等 系列标准。 qPostScript矢量图形格式：起源于 1976 年的 Evans & Sutherland 计算机 公司，当时的名字是 Design System。1978 年，John Warnock 和 Martin Newel 将其演变为 JAM 语言。1982 年，John Warnock 和 Chuck Geschke 创建了著名的 Adobe System 公司，第三次设计和实现 了这个语言，并称其为 PostScript。 第五讲无损数据压缩 无损压缩模

11、型 使用模型：得到字符或单词在信息中出现的概率 静态/半静态模型 自适应模型 静态字典模型 自适应字典模型 统计模型 字典模型 第五讲无损数据压缩 信息熵及基本概念 1信息量 信息量信息量是指从N个相等的可能事件中选出一个事件所需要的 信息度量或含量，也就是在辨识N个事件中特定的一个事件 的过程中所需要提问“是或否”的最少次数。 设从N个数中选定任一个数xj的概率为p（xj），假定选定任 意一个数的概率都相等，即p（ xj ）1/N，因此定义其信 息量为: )()(loglog/1log)( 222jjj xpIxpNNxI 式中，P(xj)是信源X发出xj的概率。I(xj)的含义是，信源X发

12、出 xj这个消息（随机事件）后，接收端收到信息量的量度。 第五讲无损数据压缩 信息熵 熵熵来源于40年代由Claude Shannon创立的信息论中的 一条定理，这一定理借用了热力学中的名词 “熵”( Entropy )来表示一条信息中真正需要编码的信息量。 信源S发出的xj（j=1,2,n）共n个随机事件的自信息统计 平均，即 H(X)称为信源X的“熵”，即信源X发出任意一个随机变 量的平均信息量。 其中：等概率事件的熵最大，为： n j jjj xPxPxIESH 1 2 )(log)()()( N NN SH N j 22 1 log 1 log 1 )( 当P(x1)1时，P(x2)P

13、(x3)P(xj)0，由（4-6）式得此时熵为 0)(log)()( 121 xPxPSH NSH 2 log)(0 由上可得熵的范围为：由上可得熵的范围为： 第五讲无损数据压缩 在编码中用熵值来衡量是否为最佳编码。若以Lc表示编 码器输出码字的平均码长，则当 LcH(S) 有冗余，不是最佳。 LcH(S) 不可能。 LcH(S) 最佳编码（Lc稍大于H(S)）。 熵值为平均码长Lc的下限。 平均码长Lc的计算公式为： n j jjc xLxPL 1 )()( （j=1,2,n） 其中：P(xj) 是信源X发出xj的概率，L(xj)为xj的编码长。 平均码长与熵关系 第五讲无损数据压缩 熵的计

14、算范例 例：对信息aabbaccbaa，字符串长度为 10，字符a、 b、c分别出现了5、3、2次，则 Ia=-log2(0.5)=1 Ib=-log2(0.3)=1.737 Ic=-log2(0.2)=2.322 H（S）= 0.5Ia +0. 3Ib +0. 2Ic =1.4855 如采用等长编码，则每个字符需要位； 总的码长: L=5*+3* +2* = 位 对比一下，我们用ASCII编码表示该信息需要80位 第五讲无损数据压缩 统计编码（熵） 统计编码是根据消息出现概率的分布特 性而进行的压缩编码 在消息和码字间找到明确的一一对应关 系，以便恢复时能准确无误再现出来 第五讲无损数据压缩

15、 技术准备：编码 通过模型，我们可以确定对某一个符号该用多少位二进制数进行编码。 现在的问题是，如何设计一种编码方案，使其尽量精确地用模型计算出 来的位数表示某个符号。 前缀编码规则：任何一个符号的编码都不是另一个符号编码的前缀。 最简单的前缀编码 字符字符编码编码 A0 B10 C110 D1110 E11110 11110111100010 D A B B D C E A A B 第五讲无损数据压缩 技术准备：压缩=模型+编码 输入模型编码输出 符号概率代码 第五讲无损数据压缩 Shannon-Fano编码 采用从上到下的方法进行编码。 仙农-范诺(Shannon- Fano)算法： 首先

16、按照符号出现的频度或概率排序， 使用递归方法分成两个部分，每一部分具有 近似相同的次数（概率） 当概率和为1，进行编码 第五讲无损数据压缩 Shannon-Fano编码例 有一幅40个象素组成的灰度图像，灰度共有5级，分别用 符号A、B、C、D和E表示，40个象素中出现灰度A的象素 数有15个，出现灰度B的象素数有7个，出现灰度C的象素 数有7个等等。如果用3个位表示5个等级的灰度值，也就 是每个象素用3位表示，编码这幅图像总共需要120位。 符 号ABCD E 出现的次数157765 H(S) = (15/40)* (40/15) + (7/40)* (40/7) + + (5/40) *

17、(40/5) =2.196 这就是说每个符号用2.196位表示，40个象素需用87.84位 第五讲无损数据压缩 Shannon-Fano编码例 符号出现的次 数( ) 分配的代 码 需要的位 数 A15 (0.375) 1.41500030 B7 (0.175)2.51450114 C7 (0.175)2.51451014 D6 (0.150)2.736911018 E5 (0.125)3.000011115 第五讲无损数据压缩 Shannon-Fano编码例 例题：例题：cabcedeacacdeddaaabaababaaabbacdebaceada 例子中的信息编码为：例子中的信息编码为：

18、 10 00 01 10 111 110 111 00 10 00 10 . 码长共码长共91位，而使用位，而使用ASCII编码表示上述信息共需要编码表示上述信息共需要240位位 a 16 b 7 c 6 d 6 e - 5 a 16 b 7 - c 6 - d 6 e - 5 a 00 b 01 c 10 d 110 e 111 root 0 01 0 1 1 1 abc de 0 第五讲无损数据压缩 Huffman编码 依据信源字符出现的概率大小来构造代 码，对出现概率较大的信源字符，给予 较短码长，而对于出现概率较小的信源 字符，给予较长的码长，最后使得编码 的平均码字最短。 第五讲无损

19、数据压缩 Huffman编码 第五讲无损数据压缩 例4-1：设输入图像的灰度级a1,a2,a3,a4,a5,a6出现的概 率分别是0.4、0.2、0.12、0.15、0.1、0.03。试进行哈夫曼 编码，并计算编码效率、压缩比、冗余度。 编码步骤：编码步骤： （1 1）初始化，根据符号概率的大小按由）初始化，根据符号概率的大小按由 大到小顺序对符号进行排序，如图大到小顺序对符号进行排序，如图4-24-2所示。所示。 （2 2）把概率小的两个符号组成一个节点，）把概率小的两个符号组成一个节点， 如图如图4-24-2中的中的a5a5、a6a6组成节点组成节点P1P1。 （3 3）重复步骤）重复步骤

20、2 2，得到节点，得到节点P2P2、P3P3、P4P4、 P5P5，形成一棵，形成一棵“树树”，其中，其中P5P5为根节点。为根节点。 （4 4）从根节点）从根节点P5P5开始到相应于每个符号开始到相应于每个符号 的的“树叶树叶”，从上到下标上，从上到下标上1 1（上枝）或者（上枝）或者0 0 （下枝），至于哪个为（下枝），至于哪个为1 1哪个为哪个为0 0则无关紧要，则无关紧要， 最后的结果仅仅是分配的代码不同，而代码最后的结果仅仅是分配的代码不同，而代码 的平均长度是相同的。的平均长度是相同的。 最终编码结果为：最终编码结果为：a1 =1, a2 =000 , a1 =1, a2 =000

21、 , a3 =011, a3 =011, a4 =001, a5 =0100, a4 =001, a5 =0100,a6 =0101a6 =0101 第五讲无损数据压缩 由公式可求得图像信源熵是： H(X)= =-（0.4log20.4+0.2log20.2+0.12log20.12+ 0.15log20.15+0.1log20.1+0.03log20.03） =2.25 bit n j jj xPxP 1 2 )(log)( 根据哈夫曼编码过程图给出的结果，由公式（4-7）可求出 它的平均码字长度： Lc=0.41+0.23+0.153+0.123+0.14+0.034 =2.33 压缩之前

22、8个符号需要3个比特量化，经过压缩之后的平均码 字长度为2.33，由公式（4-10）得其压缩比为： 2 . 1 33. 2 3 C 第五讲无损数据压缩 Huffman编码 例题例题2：cabcedeacacdeddaaabaababaaabbacdebaceada 例子中的信息编码为：例子中的信息编码为： 101 0 100 101 111 110 111 0 101 0 101 . 码长码长88位，比位，比Shannon-Fano编码略短一些编码略短一些 a 16 b 7 c 6 d 6 e - 5 a 0 b 100 c 101 d 110 e 111 root 0 0 1 1 1 a b

23、cde 0 01 第五讲无损数据压缩 整数位编码与信息熵 cabcedeacacdeddaaabaababaaabbacdebaceada 该信息的熵经计算可知为86.601位 符号符号理想位数理想位数 （熵）（熵） S-F编码需编码需 要位数要位数 Huffman编编 码需要位数码需要位数 a1.32221 b2.51523 c2.73723 d2.73733 e3.00033 总计总计86.6019188 第五讲无损数据压缩 采用哈夫曼编码时有两个问题值得注意：采用哈夫曼编码时有两个问题值得注意： （1）哈夫曼编码没有错误保护功能，在译码时，如果码 串中没有错误，那么就能一个接一个的正确译

24、出代码。但 如果码串中有错误，哪怕仅是1位出现错误，不但这个码 本身译错，更糟糕的是后面的译码可能全错，这种现象称 为错误传播（Error Propagation）。 （2）哈夫曼编码是可变长度码，因此很难随意查找或调 用压缩文件中间的内容，然后再译码，这就需要在存储代 码之前加以考虑。 与仙农-范诺编码相比，这两种方法都自含同步码同步码，在编 码之后的码串中都不须要另外添加标记符号，即在译码 时分割符号的特殊代码。 第五讲无损数据压缩 算术编码 假设某个字符的出现概率为 80%，该字符事实上只需要 -log2(0.8) = 0.322 个二进制位进行编码 难道真的能只输出 0.322 个 0

25、 或 0.322 个 1 吗？ 算术编码的输出是：一个小数算术编码的输出是：一个小数 算术编码对整条信息（无论信息有多么长），其输出仅仅 是一个数，而且是一个介于0和1之间的二进制小数。 例如算术编码对某条信息的输出为1010001111，那么 它表示小数0.1010001111，也即十进制数0.64 第五讲无损数据压缩 算术编码 算术编码（arithmetic coding AC）是利用0和1之间的 间隔来表示信源编码的一种方法，其编码值是间隔的上、 下限包含的相同二进制。编码过程中的间隔决定了符号 压缩后的输出。 算术编码用到两个基本的参数：符号的概率和它的编码 间隔。 信源符号的概率决定

26、压缩编码的效率，也决定编码过程 中信源符号的间隔，而这些间隔包含在0到1之间。 算术编码器的编码过程可用例4-2加以解释。 第五讲无损数据压缩 算术编码 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压 缩保存的原始信息为 bccb 第一步第一步：在没有开始压缩进程之前，假设我们对 a b c 三者在信息中 的出现概率一无所知（我们采用的是自适应模型），即认为三者的出现 概率相等，也就是都为1/3，我们将0-1区间按照概率的比例分配给三个 字符，即a从0.0000到0.3333，b从0.3333到0.6667，c从0.6667到 1.0000。用图形表示就是： 1.0000 0

27、.6667 0.3333 0.0000 Pc = 1/3 Pb = 1/3 Pa = 1/3 第五讲无损数据压缩 算术编码 第二步第二步：现在我们拿到第一个字符b，让我们把目光投向b对应的区间 0.3333-0.6667。这时由于多了字符b，三个字符的概率分布变成： Pa=1/4，Pb=2/4，Pc=1/4。好，让我们按照新的概率分布比例划分 0.3333-0.6667这一区间，划分的结果可以用图形表示为： 0.6667 0.5834 0.4167 0.3333 Pc = 1/4 Pb = 2/4 Pa = 1/4 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压 缩保存的原始

28、信息为 bccb 第五讲无损数据压缩 算术编码 第三步第三步：接着我们拿到字符c，我们现在要关注上一步中得到的c的区间 0.5834-0.6667。新添了c以后，三个字符的概率分布变成Pa=1/5， Pb=2/5，Pc=2/5。我们用这个概率分布划分区间0.5834-0.6667： 0.6667 0.6334 0.6001 0.5834 Pc = 2/5 Pb = 2/5 Pa = 1/5 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压 缩保存的原始信息为 bccb 第五讲无损数据压缩 算术编码 第四步第四步：现在输入下一个字符c，三个字符的概率分布为：Pa=1/6， Pb=

29、2/6，Pc=3/6。我们来划分c的区间0.6334-0.6667： 0.6667 0.6501 0.6390 0.6334 Pc = 3/6 Pb = 2/6 Pa = 1/6 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压 缩保存的原始信息为 bccb 第五讲无损数据压缩 算术编码 第五步第五步：输入最后一个字符b，因为是最后一个字符，不用再做进一步 的划分了，上一步中得到的b的区间为0.6390-0.6501，好，让我们在这 个区间内随便选择一个容易变成二进制的数，例如0.64，将它变成二进 制0.1010001111，去掉前面没有太多意义的0和小数点，我们可以输出 1

30、010001111，这就是信息被压缩后的结果，我们完成了一次最简单的算 术压缩过程 0.6667 0.6501 0.6390 0.6334 Pc = 3/6 Pb = 2/6 Pa = 1/6 例：考虑某条信息中可能出现的字符仅有 a b c 三种，我们要压 缩保存的原始信息为 bccb 输出输出:(0.64)10 = (0.1010001111)2 第五讲无损数据压缩 例2：假设信源符号为A, B, C, D，这些符号的概率分别为 0.1, 0.4, 0.2, 0.3 ，根据这些概率可把间隔0, 1分成4个子 间隔：0, 0.1, 0.1, 0.5, 0.5, 0.7, 0.7, 1，其中x

31、,y表示半开 放间隔，即包含x不包含y，如表4-1所示。 符号ABCD 概率 0.10.40.20.3 初始编码间隔 0,0.10.1,0.50.5,0.70.7,1 表表4-1 信源符号、概率和初始编码间隔信源符号、概率和初始编码间隔 如果消息序列的输入为：CADACDB，其编码过程如下： 首先输入的符号是C，找到它的编码范围是0.5, 0.7； 由于消息中第2个符号A的编码范围是0, 0.1，因此它的间隔就取0.5, 0.7的第一个1/10作为新间隔0.5, 0.52； 编码第3个符号D时取新间隔为0.514, 0.52； 编码第4个符号A时，取新间隔为0.514, 0.5146，。 第五

32、讲无损数据压缩 消息的编码输出可以是最后一个间隔中的任意数，整个编码过程如图4-3 所示。最后在0.5143876,0.51442中选择一个数作为编码输出值： 0.5143876。 解码时，解码器由编码输出值：0.5143876，可马上解得一个字符 为C，然后依次得到唯一解A,D,A,C,D,B。 第五讲无损数据压缩 在算术编码中需要注意的几个问题在算术编码中需要注意的几个问题： （1）由于实际的计算机的精度不可能无限长，运 算中出现溢出是一个明显的问题，但多数机器都有 16位、32位或者64位的精度，因此这个问题可使用 比例缩放方法解决。 （2）算术编码器对整个消息只产生一个码字，这 个码字

33、是在间隔0, 1)中的一个实数，因此译码器在 接受到表示这个实数的所有位之前不能进行译码。 （3）算术编码也是一种对错误很敏感的编码方法， 如果有一位发生错误就会导致整个消息译错。 第五讲无损数据压缩 行程长度编码 是一个针对包含有顺序排列的多次重复的数据 的压缩方案。其原理就是把一系列的重复值用 一个单独的值再加上一个计数值来取代，行程 长度就是连续且重复的单元数目。如果想得到 原始数据，只需展开这个编码就可以了。 例如，计算机制作图像中，常常具有许多颜色 相同的图块，而且在行上都具有相同的颜色， 或者在一行上有许多连续的像素都具有相同的 颜色值。这时，就不需要存储每一个像素的颜 色值，而仅

34、存储一个像素的颜色值以及具有相 同颜色的像素数目就可以，或者存储一个像素 的颜色值，以及具有相同颜色值的行数，这种 压缩编码称为行程编码。具有相同颜色的连续 的像素数目称为行程长度。 第五讲无损数据压缩 行程长度编码 如图所示，假定一幅灰度图像，第n行的像素值为： 用RLE编码方法得到的代码为：3150841160。代码斜黑 体表示的数字是行程长度，黑体字后面的数字代表像素 的颜色值。例如黑体字50代表有连续50个像素具有相同 的颜色值，它的颜色值是8。 对比RLE编码前后的代码数可以发现，在编码前要用73个代 码表示这一行的数据，而编码后只要用10个代码表示代表原来 的73个代码，压缩前后的

35、数据量之比约为7:1，即压缩比为7:1。 这说明RLE确实是一种压缩技术，而且编码技术实用。 第五讲无损数据压缩 行程编码 RLE的性能好坏主要取决于图像本身的特点。 RLE压缩编码尤其适用于计算机生成的图像， 对减少图像文件的存储空间非常有效。然而， 由于颜色丰富的自然图像在同一行上具有相同 颜色的连续像素往往很少，而连续几行都具有 相同颜色值的连续行数就更少，如果仍然使用 RLE编码方法，不仅不能压缩图像数据，反而 可能使原来的图像数据变得更大。 译码时按照与编码时采用的相同规则进行，还 原后得到的数据与压缩前的数据完全相同。因 此，RLE属于无损压缩技术。 第五讲无损数据压缩 词典编码属

36、于无损压缩技术，其根据是数据本身包含有 重复代码序列这个特性。词典编码的种类较多，归纳起来有 两类： 第一类词典编码的基本思想是查找正在压缩的字符序列 是否在前面输入的数据中出现过，如果是，则用指向早期出 现过的字符串的“指针”替代重复的字符串。这种编码思想 如图。 词典编码词典编码 第五讲无损数据压缩 词典编码词典编码 “词典”是指用以前处理过的数据来表示编码过程中遇到的重复部 分。这类编码中的所有算法都是以Abraham Lempel 和Jakob Ziv在 1977年开发和发表的称为LZ77算法为基础的，1982年由Storer和 Szymanski改进的称为LZSS算法。 第二类算法的

37、思想是从输入的数据中创建一个“短语词典” （dictionary of the phrases。编码数据过程中，遇到已经在词 典中出现的“短语”时，编码器就输出这个词典中该短语的 “索引号”，而不是短语本身。 第五讲无损数据压缩 词典编码词典编码 J.Ziv和A.Lempel在1978年首次发表了介绍这种编码方法的文章。 在他们研究的基础上，Terry A.Weltch在1984年发表了改进这种编 码算法的文章，因此把这种编码方法称为LZW（Lempel-Ziv Walch）压缩编码。这种算法首先在高速硬盘控制器上得到了应用。 在众多的压缩技术中，LZW算法时一种通用的、性能优良并得到 广泛应

38、用的压缩算法。LZW是一种完全可逆的算法，与其他算法 比较，往往具有更高的压缩效率，因此被广泛应用于多种流行的 压缩软件中。 第五讲无损数据压缩 LZ77算法 字典模型：现代汉语词典以及下面的例子 第五讲无损数据压缩 LZ77算法 几个术语：几个术语： 输入数据流(input stream)：要被压缩的字符序列。 字符(character)：输入数据流中的基本单元。 编码位置(coding position)：输入数据流中当前要编码 的字符位置，指前向缓冲存储器中的开始字符。 前向缓冲存储器(Lookahead buffer)：存放从编码位置 到输入数据流结束的字符序列的存储器。 窗口(win

39、dow)：指包含W个字符的窗口，字符是从编 码位置开始向后数也就是最后处理的字符数。 指针(pointer)：指向窗口中的匹配串且含长度的指针。 第五讲无损数据压缩 LZ77编码算法 编码算法的具体执行步骤如下： （）把编码位置设置到输入数据流的开始位 置。 （）查找窗口中最长的匹配串。 （）以“(Pointer, Length) Characters”的格式 输出，其中Pointer是指向窗口中匹配串的指针， Length表示匹配字符的长度，Characters是前 向缓冲存储器中的不匹配的第1个字符。 （）如果前向缓冲存储器不是空的，则把编 码位置和窗口向前移(Length+1)个字符，然

40、后 返回到步骤2。 第五讲无损数据压缩 编码举例 位置位置1 12 23 34 45 56 67 78 89 9 字符字符 A AA AB BC CB BB BA AB BC C 步骤位置匹配串 字符 输出 11-A(0,0) A 22AB(1,1) B 34-C(0,0) C 45BB(2,1) B 57A BC(5,2) C 第五讲无损数据压缩 LZ77编码算法 “步骤”栏表示编码步骤。 “位置”栏表示编码位置，输入数据流中的第1个字符 为编码位置1。 “匹配串”栏表示窗口中找到的最长的匹配串。 “字符”栏表示匹配之后在前向缓冲存储器中的第1个 字符。 “输出”栏以“(Back_chars

41、, Chars_length) Explicit_character”格式输出。其中，(Back_chars, Chars_length)是指向匹配串的指针，告诉译码器“在这 个窗口中向后退Back_chars个字符然后拷贝 Chars_length个字符到输出”，Explicit_character是真实 字符。例如，表4-10中的输出“(5,2) C”告诉译码器回 退5个字符，然后拷贝2个字符“AB” 第五讲无损数据压缩 LZSS编码 LZ77通过输出真实字符解决了在窗口中出现没 有匹配串的问题，但这个解决方案包含有冗余 信息。 冗余信息表现在两个方面，一是空指针，二是 编码器可能输出额外的字符，这种字符是指可 能包含在下一个匹配串中的字符。 LZSS算法以比较有效的方法解决这个问题，它 的思想是如果匹配串的长度比指针本身的长度 长就输出指针，否则就输出真实字符。 由于输出