2010-5-14 计算机算法设计与分析 1
第十章
数据压缩算法
2010-5-14 计算机算法设计与分析 2
数据压缩
? 将信源所发出的信号用较少的数码表示，减少
容纳给定数据集合的信号空间。
? 所谓信号空间亦即被压缩的对象是指：
? ①物理空间，即数据存储介质的尺寸。
? ②时间区间，传输消息集合所需要的时间。
? ③电磁频谱区域，如为传输消息的带宽等。
? 信号空间的各种形式相互关联。减少存储空间
就能提高传输效率和节省带宽的占用。
2010-5-14 计算机算法设计与分析 3
可逆压缩和不可逆压缩
? 可逆压缩叫做无失真、无差错编码。压缩后的
数据可以精确地恢复为原来的数据。如 ZIP、
RAR,ARJ,CAB等文件，都是可逆压缩。
? 不可逆压缩叫做失真编码。压缩后的数据不可
能精确地恢复成原始数据。如在计算机中存储
的图片、声音、视频等文件。
? 人的感觉器官本身对于图片、声音、视频中的
某些信息的丢失，是难以察觉的。
? 不可逆压缩技术的标准有,JPEG,MPEG-1、
MPEG-2,MPEG-4等，均达到了很高的压缩比。
2010-5-14 计算机算法设计与分析 4
ASCII码压缩算法
? 数采用不同的基数来表示，长度不同。
一般来说，基数较大，长度较短。
例如，十进制的 1234是四位，需要四个
字节存储，用 16进制数表示为三位，
4D2,只需要两个字节。
? 如果采用 100为基数，即每两位十进制数
用一个字节存放，就可以压缩 50%。
例如，十进制的 1234表示为百进制数，
即 12 34,只需要两个字节。
? 但是数字 00~99只需要 7个比特，每个字
节还有一个比特闲置，因此还可以压缩。
? 把第八个数的 依次放到前 7个字节的最高
位上。 这样 可以压缩 62.5%。
2010-5-14 计算机算法设计与分析 5
ASCII码压缩算法
? 1、将原数据的每两位数字作为一组，其
值在 00~99之间；然后将它们转化为 16进
制，即 00~99分别对应于 00H~63H。
? 2,从第一个 16进制数开始，
? 3、每 8个 16进制数为一组，将第 8个数字
拆成 7个比特，把它们依次放到前面 7个
16进制数的最高位上。
? 4、重复第 3步，直至完成全部数据为止。
2010-5-14 计算机算法设计与分析 6
ASCII码压缩算法举例
? 原数据,1 2 3 4 5 6 7 8 9 1 9 2 9 3 9 4
? 按百进制分组,12 34 56 78 91 92 93 94
? 转换为 16进制,0C 22 38 4E 5B 5C 5D 5E
? 每 8个数为一组，将第 8个，即 5E = 01011110的
7个比特分别填到前 7个数的最高位。
00001100
0C
00100010
22
00111000
38
01001110
4E
01011011
5B
01011100
5C
01011101
5D
1
8
0 1
B8
1
CE
1
DB
1
DC
最后原数据压缩编码的结果为 7个 16进制的数
据,8C 22 B8 CE DB DC 5D
? 存储空间由原来的 16个字节变成了 7个字节。
2010-5-14 计算机算法设计与分析 7
哈夫曼编码
? 哈夫曼（ D.A.Huffman） 于 1952年提出一
种编码方法，它完全依据字符出现的概
率来构造平均长度最短的编码，也称之
为最佳编码。
? 哈夫曼树 为在权为 wl,w2,…, wn的 n个叶子
所构成的所有二叉树中，带权路径长度最小 (即
代价最小 )的二叉树称为哈夫曼树。
? 哈夫曼编码中各字符编码的长度不同，它的基
本理论基于下列定理：在变长编码中，若各码
字长度严格按照所对应的符号出现概率的大小
逆序排列，则其平均长度最小。
? 为了避免产生歧义，编码时必须使得任一字符
的编码都不是另外任意字符编码的前缀，这种
编码称为前缀编码。
2010-5-14 计算机算法设计与分析 8
哈夫曼编码的算法
? 1,将 n个频率为 {p1,p2,…,p n}的字符表示为 n个
结点，将每个结点看成二叉树 Ti,频率 pi为其
权值 wi,组成集合 F = {T1,T2,…,T n}。
? 2,在 F中选取两棵权值最小的树作为左、右子
树构造一棵新二叉树，令新二叉树的的权值为
其左、右子树的权值之和。
? 3,在 F中删除这两棵树，并加入新的二叉树。
? 4,重复 2和 3，直到 F中只有一棵树为止。
? 5,约定左、右分支分别为 0和 1。从根到叶子的
路径的 0和 1的序列，即该字符的哈夫曼编码。
2010-5-14 计算机算法设计与分析 9
字典法
? 基本思想是：构造一个字典，将信息中反复出
现的字符串，登记为较短的字符串，解码时对
这种字符串，通过查 字典,转换为原字符串。
? 该算法的原理很简单，但要真正实现却很困难，
因为它存在几个长期困扰着研究者的难点：
? 1、如何找到这些重复出现的字符串？
? 2、如何找到尽量长的字符串被替代，？
? 3、怎样选用较短的字符串？如何区分原始信
息中就已经存在的用于代替的字符串？
2010-5-14 计算机算法设计与分析 10
LZ算法
? 1977 年,Jacob Ziv 和 Abraham Lempel发表了
论文《顺序数据压缩的一个通用算法,。 1978
年，他们发表了该论文的续篇《通过可变比率
编码的独立序列的压缩,。
? 这两篇论文提出的两个压缩技术被称为 LZ77
和 LZ78算法。它们的思路和字典法颇为相似，
因此，人们将基于这一思路的编码方法称作字
典式编码。字典式编码不但在压缩效果上大大
超过了哈夫曼编码, 而且，对于好的实现，其
压缩和解压缩的速度也异常惊人。
2010-5-14 计算机算法设计与分析 11
LZ77算法
? LZ77 算法又称为“滑动窗口压缩”,如下图：
2010-5-14 计算机算法设计与分析 12
LZ77 算法的基本流程
? 重复进行以下处理，直至所有数据处理完毕：
? 1、从当前压缩位置开始，考察未编码的数据，
并试图在滑动窗口中找出最长的匹配字符串，
? 2、如果找到，输出三元符号组 (off,len,c),其
中 off为窗口中匹配字符串相对窗口边界的偏移，
len为可匹配的长度,c为下一个字符；将窗口
向后滑动 len + 1个字符。
? 3、如果未找到，输出三元符号组 (0,0,c),其
中 c为下一个字符；将窗口向后滑动 1个字符。
2010-5-14 计算机算法设计与分析 13
LZ77 算法的实例
? 假设窗口的大小为 10 个字符，我们刚编
码过的 10 个字符是,abcdbbccaa,即将
编码的字符为,abaeaaabaee。
a b c d b b c c a a a b a e a a a b a e e
窗口
首先发现，可以和要编码字符匹配的最
长串为 ab (off = 0,len = 2),ab 的下一个字
符为 a,我们输出三元组,(0,2,a)。
b
2010-5-14 计算机算法设计与分析 14
LZ77 算法的实例
? 现在将窗口向后滑动 3(2+1)个字符, 窗口
中的内容为,dbbccaaaba,剩余字符为
eaaabaee,下一个字符 e 在窗口中没有匹
配, 我们输出三元组,(0,0,e)。
a b c d b b c c a a a b a e a a a b a e e
2010-5-14 计算机算法设计与分析 15
LZ77 算法的实例
? 又将窗口向后滑动 1 个字符，其中内容
变为,bbccaaabae。 这时发现，要编码的
aaabae 在窗口中存在 (off = 4,len = 6),其
后的字符为 e,可以输出,(4,6,e)。
a b c d b b c c a a a b a e a a a b a e e
2010-5-14 计算机算法设计与分析 16
LZ77 算法的实例
a b c d b b c c a a a b a e a a a b a e e
? 最后又将窗口向后滑动 7 个字符。这样，
我们将可以匹配的字符串都变成了指向
窗口内的指针，并由此完成了对上述数
据的压缩。
2010-5-14 计算机算法设计与分析 17
LZ77 算法的解压缩
? LZ77 算法的解压缩的过程十分简单，只
要我们向压缩时那样维护好滑动的窗口，
随着三元组的不断输入，我们在窗口中
找到相应的匹配串，缀上后继字符 c 输
出（如果 off 和 len 都为 0 则只输出后继
字符 c ),即可还原出原始数据。
2010-5-14 计算机算法设计与分析 18
LZ77 算法的讨论
? 1、编码方法
? ⑴ 分量 off与窗口的大小有关，完全可以
用固定的位数来表示它。
? ⑵ 分量 len可以使用一种变长的编码方式
来表示该长度值。
? ⑶ 字符 c,用 8个二进制位对其编码。
2010-5-14 计算机算法设计与分析 19
LZ77 算法的讨论
? 2、输出方式
? 原始 LZ77 算法即使没有匹配，仍然需要
输出一个 len = 0的三元组来表示单个字符，
还可以设计出另外一种更为有效的输出
方式：将匹配串和不能匹配的单个字符
分别编码、分别输出，输出匹配串时不
同时输出后续字符。
2010-5-14 计算机算法设计与分析 20
LZ77 算法的讨论
? 3、如何查找匹配串
? ①限制可匹配字符串的最大长度（例如
20 个字节），按照大小顺序组织成二叉
有序树。在这样的二叉有序树中进行字
符串的查找，其效率是很高的。
? ②当然，也可以采用 KMP,KR,BM等
快速串匹配算法来依次进行长度为 20、
19,18…… 的模式匹配。
2010-5-14 计算机算法设计与分析 21
LZ78算法
? LZ78算法的基本思路与 LZ77算法类似，
也是利用已经处理过的编码信息，但它
发生匹配时，不是保存一个三元组，而
是一个二元组：匹配位置和不匹配的第
一个字符。同时，还要将这个字符串保
存到内存中，为此，它需要一个不断增
长的编码字串表（字典）。
2010-5-14 计算机算法设计与分析 22
LZ78算法的举例
? 如对符号串
,ababcbabaaaaaa
a”编码，需要右
边的字典：
原字符串 压缩码 序号
a 0a 1
b 0b 2
ab 1b 3
c 0c 4
ba 2a 5
baa 5a 6
aa 1a 7
aaa 7a 8
2010-5-14 计算机算法设计与分析 23
LZ78算法的 基本算法
? void LZ78(void) {将字典 D置空 ;
? while (还有字符未处理完 )
? {current= 0; goon = 1; read(w);
? while ( goon )
? { if (w ? D) {current = #w; read(k); w = w + k;}
? else goon = 0; }
? append(D,w); /*将字符串 w放到字典的尾部 */
? w = last_char(w); /* 取字符串 w的末尾字符 */
? write(current,w); /*输出匹配位置和不匹配字符 */
? }}
#w表示 w在字
典中的序号
2010-5-14 计算机算法设计与分析 24
LZW算法
? LZ78算法很难一次匹配到更长的字符串, 而且,
它所保存的信息量仍然有冗余, 因为如果每一
个字符都一定能匹配成功的话, 也可以不需要
保存匹配不成功的字符 。
? LZW算法的基本思路就是要尽量“拉长”这些
串，为此,它将 LZ78算法中的每一个被分割的
子串的最后一个字符作为下一个子串的开始 。
当然这么做肯定会增加字典的长度。而且需要
先将所有可能出现的单字符先放到字典中以保
证单字符一定能匹配成功。
2010-5-14 计算机算法设计与分析 25
LZW算法
? void LZW(void){
? 将所有单字符放入字典 D中；
? read(w);
? while(还有字符未处理完 ) { read(k);
? if ( w + k ? D) w = w + k;
? else {write(w在字典中的序号 );
append(dictionary,w + k); w = k;}
? }
2010-5-14 计算机算法设计与分析 26
LZW算法的举例
? 对于字符串
,ababcbaaaaaaaa”，
得到的字典如右,
a a 1
b b 2
c c 3
ab 1b 4
ba 2a 5
abc 4c 6
cb 3b 7
baa 5a 8
aa 1a 9
aaa 9a 10
aaaa 10a 11
原字符串 压缩码 序号
单字符ab的压缩码
为 1b,即第
一个字后面
跟符号 b。
前一个字的最
后字符是下一
个字的开始，
所以这里是 ba。
? 压缩后的编码为：
{a,b,c } +
{1,2,4,3,5,1,9,10}
? 单字符可事先约定，
从而无需传输。
2010-5-14 计算机算法设计与分析 27
LZW解压缩算法
? void unLZW(void){将所有单字符放入字典 D；
? orign_len = length(D);
? i = orign_len + 1;
? while (还有编码未处理完 ) { read(k);
? ch=first_char ( D[k] ); /*D中第 k行首字符 */
? if ( i > orign_len + 1)
? D[i – 1] =D[i – 1] + ch;
? D[i] = D[k]; /* 生成本行字符串的前一部分 */
? write(D[k] ); /* 输出还原后的数据 */
? i:=i+1; }}
2010-5-14 计算机算法设计与分析 28
LZW解压缩算法的举例
? 压缩码为：
{1,2,4,3,5,1,9,10}
? 首先将单字符放入字典。
a 1
b 2
c 3
? orign_len = length(D) = 3;
? i = orign_len + 1 = 4;
? read(k); k = 1;
? ch=first_char (D[k]) = a;
? ∵ i ? orign_len + 1
? ∴ D[4] = D[1]; i = i + 1 = 5
a 4
2010-5-14 计算机算法设计与分析 29
LZW解压缩算法的举例
? 压缩码为：
{1,2,4,3,5,1,9,10}
a 1
b 2
c 3
a 4
? i = 5
? read(k); k = 2;
? ch = first_char (D[k]) = b;
? ∵ i ? orign_len + 1
? ∴ D[i – 1] = D[i – 1] + ch，
即, D[4] = ab;
? D[5] = D[2] = b;
? i = i + 1 = 6;
b
b 5
2010-5-14 计算机算法设计与分析 30
LZW解压缩算法的举例
? 压缩码为：
{1,2,4,3,5,1,9,10}
a 1
b 2
c 3
ab 4
b 5
? i = 6
? read(k); k = 4;
? ch = first_char (D[4]) = a;
? ∵ i ? orign_len + 1
? ∴ D[i – 1] = D[i – 1] + ch，
即, D[5] = ba;
? D[6] = D[4] = ab;
? i = i + 1 = 7;
a
ab 6
? 剩下的以此类推。
第十章
数据压缩算法
2010-5-14 计算机算法设计与分析 2
数据压缩
? 将信源所发出的信号用较少的数码表示，减少
容纳给定数据集合的信号空间。
? 所谓信号空间亦即被压缩的对象是指：
? ①物理空间，即数据存储介质的尺寸。
? ②时间区间，传输消息集合所需要的时间。
? ③电磁频谱区域，如为传输消息的带宽等。
? 信号空间的各种形式相互关联。减少存储空间
就能提高传输效率和节省带宽的占用。
2010-5-14 计算机算法设计与分析 3
可逆压缩和不可逆压缩
? 可逆压缩叫做无失真、无差错编码。压缩后的
数据可以精确地恢复为原来的数据。如 ZIP、
RAR,ARJ,CAB等文件，都是可逆压缩。
? 不可逆压缩叫做失真编码。压缩后的数据不可
能精确地恢复成原始数据。如在计算机中存储
的图片、声音、视频等文件。
? 人的感觉器官本身对于图片、声音、视频中的
某些信息的丢失，是难以察觉的。
? 不可逆压缩技术的标准有,JPEG,MPEG-1、
MPEG-2,MPEG-4等，均达到了很高的压缩比。
2010-5-14 计算机算法设计与分析 4
ASCII码压缩算法
? 数采用不同的基数来表示，长度不同。
一般来说，基数较大，长度较短。
例如，十进制的 1234是四位，需要四个
字节存储，用 16进制数表示为三位，
4D2,只需要两个字节。
? 如果采用 100为基数，即每两位十进制数
用一个字节存放，就可以压缩 50%。
例如，十进制的 1234表示为百进制数，
即 12 34,只需要两个字节。
? 但是数字 00~99只需要 7个比特，每个字
节还有一个比特闲置，因此还可以压缩。
? 把第八个数的 依次放到前 7个字节的最高
位上。 这样 可以压缩 62.5%。
2010-5-14 计算机算法设计与分析 5
ASCII码压缩算法
? 1、将原数据的每两位数字作为一组，其
值在 00~99之间；然后将它们转化为 16进
制，即 00~99分别对应于 00H~63H。
? 2,从第一个 16进制数开始，
? 3、每 8个 16进制数为一组，将第 8个数字
拆成 7个比特，把它们依次放到前面 7个
16进制数的最高位上。
? 4、重复第 3步，直至完成全部数据为止。
2010-5-14 计算机算法设计与分析 6
ASCII码压缩算法举例
? 原数据,1 2 3 4 5 6 7 8 9 1 9 2 9 3 9 4
? 按百进制分组,12 34 56 78 91 92 93 94
? 转换为 16进制,0C 22 38 4E 5B 5C 5D 5E
? 每 8个数为一组，将第 8个，即 5E = 01011110的
7个比特分别填到前 7个数的最高位。
00001100
0C
00100010
22
00111000
38
01001110
4E
01011011
5B
01011100
5C
01011101
5D
1
8
0 1
B8
1
CE
1
DB
1
DC
最后原数据压缩编码的结果为 7个 16进制的数
据,8C 22 B8 CE DB DC 5D
? 存储空间由原来的 16个字节变成了 7个字节。
2010-5-14 计算机算法设计与分析 7
哈夫曼编码
? 哈夫曼（ D.A.Huffman） 于 1952年提出一
种编码方法，它完全依据字符出现的概
率来构造平均长度最短的编码，也称之
为最佳编码。
? 哈夫曼树 为在权为 wl,w2,…, wn的 n个叶子
所构成的所有二叉树中，带权路径长度最小 (即
代价最小 )的二叉树称为哈夫曼树。
? 哈夫曼编码中各字符编码的长度不同，它的基
本理论基于下列定理：在变长编码中，若各码
字长度严格按照所对应的符号出现概率的大小
逆序排列，则其平均长度最小。
? 为了避免产生歧义，编码时必须使得任一字符
的编码都不是另外任意字符编码的前缀，这种
编码称为前缀编码。
2010-5-14 计算机算法设计与分析 8
哈夫曼编码的算法
? 1,将 n个频率为 {p1,p2,…,p n}的字符表示为 n个
结点，将每个结点看成二叉树 Ti,频率 pi为其
权值 wi,组成集合 F = {T1,T2,…,T n}。
? 2,在 F中选取两棵权值最小的树作为左、右子
树构造一棵新二叉树，令新二叉树的的权值为
其左、右子树的权值之和。
? 3,在 F中删除这两棵树，并加入新的二叉树。
? 4,重复 2和 3，直到 F中只有一棵树为止。
? 5,约定左、右分支分别为 0和 1。从根到叶子的
路径的 0和 1的序列，即该字符的哈夫曼编码。
2010-5-14 计算机算法设计与分析 9
字典法
? 基本思想是：构造一个字典，将信息中反复出
现的字符串，登记为较短的字符串，解码时对
这种字符串，通过查 字典,转换为原字符串。
? 该算法的原理很简单，但要真正实现却很困难，
因为它存在几个长期困扰着研究者的难点：
? 1、如何找到这些重复出现的字符串？
? 2、如何找到尽量长的字符串被替代，？
? 3、怎样选用较短的字符串？如何区分原始信
息中就已经存在的用于代替的字符串？
2010-5-14 计算机算法设计与分析 10
LZ算法
? 1977 年,Jacob Ziv 和 Abraham Lempel发表了
论文《顺序数据压缩的一个通用算法,。 1978
年，他们发表了该论文的续篇《通过可变比率
编码的独立序列的压缩,。
? 这两篇论文提出的两个压缩技术被称为 LZ77
和 LZ78算法。它们的思路和字典法颇为相似，
因此，人们将基于这一思路的编码方法称作字
典式编码。字典式编码不但在压缩效果上大大
超过了哈夫曼编码, 而且，对于好的实现，其
压缩和解压缩的速度也异常惊人。
2010-5-14 计算机算法设计与分析 11
LZ77算法
? LZ77 算法又称为“滑动窗口压缩”,如下图：
2010-5-14 计算机算法设计与分析 12
LZ77 算法的基本流程
? 重复进行以下处理，直至所有数据处理完毕：
? 1、从当前压缩位置开始，考察未编码的数据，
并试图在滑动窗口中找出最长的匹配字符串，
? 2、如果找到，输出三元符号组 (off,len,c),其
中 off为窗口中匹配字符串相对窗口边界的偏移，
len为可匹配的长度,c为下一个字符；将窗口
向后滑动 len + 1个字符。
? 3、如果未找到，输出三元符号组 (0,0,c),其
中 c为下一个字符；将窗口向后滑动 1个字符。
2010-5-14 计算机算法设计与分析 13
LZ77 算法的实例
? 假设窗口的大小为 10 个字符，我们刚编
码过的 10 个字符是,abcdbbccaa,即将
编码的字符为,abaeaaabaee。
a b c d b b c c a a a b a e a a a b a e e
窗口
首先发现，可以和要编码字符匹配的最
长串为 ab (off = 0,len = 2),ab 的下一个字
符为 a,我们输出三元组,(0,2,a)。
b
2010-5-14 计算机算法设计与分析 14
LZ77 算法的实例
? 现在将窗口向后滑动 3(2+1)个字符, 窗口
中的内容为,dbbccaaaba,剩余字符为
eaaabaee,下一个字符 e 在窗口中没有匹
配, 我们输出三元组,(0,0,e)。
a b c d b b c c a a a b a e a a a b a e e
2010-5-14 计算机算法设计与分析 15
LZ77 算法的实例
? 又将窗口向后滑动 1 个字符，其中内容
变为,bbccaaabae。 这时发现，要编码的
aaabae 在窗口中存在 (off = 4,len = 6),其
后的字符为 e,可以输出,(4,6,e)。
a b c d b b c c a a a b a e a a a b a e e
2010-5-14 计算机算法设计与分析 16
LZ77 算法的实例
a b c d b b c c a a a b a e a a a b a e e
? 最后又将窗口向后滑动 7 个字符。这样，
我们将可以匹配的字符串都变成了指向
窗口内的指针，并由此完成了对上述数
据的压缩。
2010-5-14 计算机算法设计与分析 17
LZ77 算法的解压缩
? LZ77 算法的解压缩的过程十分简单，只
要我们向压缩时那样维护好滑动的窗口，
随着三元组的不断输入，我们在窗口中
找到相应的匹配串，缀上后继字符 c 输
出（如果 off 和 len 都为 0 则只输出后继
字符 c ),即可还原出原始数据。
2010-5-14 计算机算法设计与分析 18
LZ77 算法的讨论
? 1、编码方法
? ⑴ 分量 off与窗口的大小有关，完全可以
用固定的位数来表示它。
? ⑵ 分量 len可以使用一种变长的编码方式
来表示该长度值。
? ⑶ 字符 c,用 8个二进制位对其编码。
2010-5-14 计算机算法设计与分析 19
LZ77 算法的讨论
? 2、输出方式
? 原始 LZ77 算法即使没有匹配，仍然需要
输出一个 len = 0的三元组来表示单个字符，
还可以设计出另外一种更为有效的输出
方式：将匹配串和不能匹配的单个字符
分别编码、分别输出，输出匹配串时不
同时输出后续字符。
2010-5-14 计算机算法设计与分析 20
LZ77 算法的讨论
? 3、如何查找匹配串
? ①限制可匹配字符串的最大长度（例如
20 个字节），按照大小顺序组织成二叉
有序树。在这样的二叉有序树中进行字
符串的查找，其效率是很高的。
? ②当然，也可以采用 KMP,KR,BM等
快速串匹配算法来依次进行长度为 20、
19,18…… 的模式匹配。
2010-5-14 计算机算法设计与分析 21
LZ78算法
? LZ78算法的基本思路与 LZ77算法类似，
也是利用已经处理过的编码信息，但它
发生匹配时，不是保存一个三元组，而
是一个二元组：匹配位置和不匹配的第
一个字符。同时，还要将这个字符串保
存到内存中，为此，它需要一个不断增
长的编码字串表（字典）。
2010-5-14 计算机算法设计与分析 22
LZ78算法的举例
? 如对符号串
,ababcbabaaaaaa
a”编码，需要右
边的字典：
原字符串 压缩码 序号
a 0a 1
b 0b 2
ab 1b 3
c 0c 4
ba 2a 5
baa 5a 6
aa 1a 7
aaa 7a 8
2010-5-14 计算机算法设计与分析 23
LZ78算法的 基本算法
? void LZ78(void) {将字典 D置空 ;
? while (还有字符未处理完 )
? {current= 0; goon = 1; read(w);
? while ( goon )
? { if (w ? D) {current = #w; read(k); w = w + k;}
? else goon = 0; }
? append(D,w); /*将字符串 w放到字典的尾部 */
? w = last_char(w); /* 取字符串 w的末尾字符 */
? write(current,w); /*输出匹配位置和不匹配字符 */
? }}
#w表示 w在字
典中的序号
2010-5-14 计算机算法设计与分析 24
LZW算法
? LZ78算法很难一次匹配到更长的字符串, 而且,
它所保存的信息量仍然有冗余, 因为如果每一
个字符都一定能匹配成功的话, 也可以不需要
保存匹配不成功的字符 。
? LZW算法的基本思路就是要尽量“拉长”这些
串，为此,它将 LZ78算法中的每一个被分割的
子串的最后一个字符作为下一个子串的开始 。
当然这么做肯定会增加字典的长度。而且需要
先将所有可能出现的单字符先放到字典中以保
证单字符一定能匹配成功。
2010-5-14 计算机算法设计与分析 25
LZW算法
? void LZW(void){
? 将所有单字符放入字典 D中；
? read(w);
? while(还有字符未处理完 ) { read(k);
? if ( w + k ? D) w = w + k;
? else {write(w在字典中的序号 );
append(dictionary,w + k); w = k;}
? }
2010-5-14 计算机算法设计与分析 26
LZW算法的举例
? 对于字符串
,ababcbaaaaaaaa”，
得到的字典如右,
a a 1
b b 2
c c 3
ab 1b 4
ba 2a 5
abc 4c 6
cb 3b 7
baa 5a 8
aa 1a 9
aaa 9a 10
aaaa 10a 11
原字符串 压缩码 序号
单字符ab的压缩码
为 1b,即第
一个字后面
跟符号 b。
前一个字的最
后字符是下一
个字的开始，
所以这里是 ba。
? 压缩后的编码为：
{a,b,c } +
{1,2,4,3,5,1,9,10}
? 单字符可事先约定，
从而无需传输。
2010-5-14 计算机算法设计与分析 27
LZW解压缩算法
? void unLZW(void){将所有单字符放入字典 D；
? orign_len = length(D);
? i = orign_len + 1;
? while (还有编码未处理完 ) { read(k);
? ch=first_char ( D[k] ); /*D中第 k行首字符 */
? if ( i > orign_len + 1)
? D[i – 1] =D[i – 1] + ch;
? D[i] = D[k]; /* 生成本行字符串的前一部分 */
? write(D[k] ); /* 输出还原后的数据 */
? i:=i+1; }}
2010-5-14 计算机算法设计与分析 28
LZW解压缩算法的举例
? 压缩码为：
{1,2,4,3,5,1,9,10}
? 首先将单字符放入字典。
a 1
b 2
c 3
? orign_len = length(D) = 3;
? i = orign_len + 1 = 4;
? read(k); k = 1;
? ch=first_char (D[k]) = a;
? ∵ i ? orign_len + 1
? ∴ D[4] = D[1]; i = i + 1 = 5
a 4
2010-5-14 计算机算法设计与分析 29
LZW解压缩算法的举例
? 压缩码为：
{1,2,4,3,5,1,9,10}
a 1
b 2
c 3
a 4
? i = 5
? read(k); k = 2;
? ch = first_char (D[k]) = b;
? ∵ i ? orign_len + 1
? ∴ D[i – 1] = D[i – 1] + ch，
即, D[4] = ab;
? D[5] = D[2] = b;
? i = i + 1 = 6;
b
b 5
2010-5-14 计算机算法设计与分析 30
LZW解压缩算法的举例
? 压缩码为：
{1,2,4,3,5,1,9,10}
a 1
b 2
c 3
ab 4
b 5
? i = 6
? read(k); k = 4;
? ch = first_char (D[4]) = a;
? ∵ i ? orign_len + 1
? ∴ D[i – 1] = D[i – 1] + ch，
即, D[5] = ba;
? D[6] = D[4] = ab;
? i = i + 1 = 7;
a
ab 6
? 剩下的以此类推。
