📄 chapter5.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type"
content="text/html; charset=gb_2312-80">
<meta name="GENERATOR" content="Microsoft FrontPage Express 2.0">
<title>笨笨数据压缩教程</title>
</head>
<body bgcolor="#FFFFFF">
<p align="right"><a href="http://www.contextfree.net/">返回断章取义堂</a> <a href="http://www.contextfree.net/wangyg/">返回咏刚的家</a></p>
<p style="background-color:#AAEEFF;font-size:14px;color:#0000AA">《笨笨数据压缩教程》是我在1998年因工作需要研究压缩算法时写的文章（算是一种工作笔记吧，其中难免有许多疏漏），1999年初随着项目变迁，就把压缩技术的研究暂时搁置了。从那以后，一是工作太忙，二是自己懒惰，总之是没能把半部压缩教程补全。非常对不住大家。——王咏刚，2003年3月</p>
<p><img src="benben.jpg"
alt="笨笨数据压缩教程(Benben's Data Compression Guide)"
width="370" height="129"></p>
<h2>第五章 聪明的以色列人(上)：LZ77</h2>
<div align="right">
<address>
<a href="chapter4.htm">第四章</a> <a href="chapter6.htm">第六章</a>
</address>
</div>
<p><strong>全新的思路</strong></p>
<p>我们在第三和第四章中讨论的压缩模型都是基于对信息中单个字符出现频率的统计而设计的，直到
70 年代末期，这种思路在数据压缩领域一直占据着统治地位。在我们今天看来，这种情形在某种程度上显得有些可笑，但事情就是这样，一旦某项技术在某一领域形成了惯例，人们就很难创造出在思路上与其大相径庭的哪怕是更简单更实用的技术来。</p>
<p>我们敬佩那两个在数据压缩领域做出了杰出贡献的以色列人，因为正是他们打破了
Huffman 编码一统天下的格局，带给了我们既高效又简便的“字典模型”。至今，几乎我们日常使用的所有通用压缩工具，象
ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR……甚至许多硬件如网络设备中内置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。</p>
<p>说起来，字典模型的思路相当简单，我们日常生活中就经常在使用这种压缩思想。我们常常跟人说“奥运会”、“IBM”、“TCP”之类的词汇，说者和听者都明白它们指的是“奥林匹克运动会”、“国际商业机器公司”和“传输控制协议”，这实际就是信息的压缩。我们之所以可以顺利使用这种压缩方式而不产生语义上的误解，是因为在说者和听者的心中都有一个事先定义好的缩略语字典，我们在对信息进行压缩（说）和解压缩（听）的过程中都对字典进行了查询操作。字典压缩模型正是基于这一思路设计实现的。</p>
<p>最简单的情况是，我们拥有一本预先定义好的字典。例如，我们要对一篇中文文章进行压缩，我们手中已经有一本《现代汉语词典》。那么，我们扫描要压缩的文章，并对其中的句子进行分词操作，对每一个独立的词语，我们在《现代汉语词典》查找它的出现位置，如果找到，我们就输出页码和该词在该页中的序号，如果没有找到，我们就输出一个新词。这就是静态字典模型的基本算法了。</p>
<p>你一定可以发现，静态字典模型并不是好的选择。首先，静态模型的适应性不强，我们必须为每类不同的信息建立不同的字典；其次，对静态模型，我们必须维护信息量并不算小的字典，这一额外的信息量影响了最终的压缩效果。所以，几乎所有通用的字典模型都使用了自适应的方式，也就是说，将已经编码过的信息作为字典，如果要编码的字符串曾经出现过，就输出该字符串的出现位置及长度，否则输出新的字符串。根据这一思路，你能从下面这幅图中读出其中包含的原始信息吗？</p>
<p><img src="putao.gif" width="440" height="57"></p>
<p>啊，对了，是“吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮”。现在你该大致明白自适应字典模型的梗概了吧。好了，下面就让我们来深入学习字典模型的第一类实现——LZ77
算法。</p>
<p><strong>滑动的窗口</strong></p>
<p>LZ77
算法在某种意义上又可以称为“滑动窗口压缩”，这是由于该算法将一个虚拟的，可以跟随压缩进程滑动的窗口作为术语字典，要压缩的字符串如果在该窗口中出现，则输出其出现位置和长度。使用固定大小窗口进行术语匹配，而不是在所有已经编码的信息中匹配，是因为匹配算法的时间消耗往往很多，必须限制字典的大小才能保证算法的效率；随着压缩的进程滑动字典窗口，使其中总包含最近编码过的信息，是因为对大多数信息而言，要编码的字符串往往在最近的上下文中更容易找到匹配串。</p>
<p>参照下图，让我们熟悉一下 LZ77
算法的基本流程。</p>
<p><img src="lz77.gif" width="440" height="130"></p>
<p>1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤
2，否则进行步骤 3。</p>
<p>2、输出三元符号组 ( off, len, c )。其中 off
为窗口中匹配字符串相对窗口边界的偏移，len
为可匹配的长度，c 为下一个字符。然后将窗口向后滑动
len + 1 个字符，继续步骤 1。</p>
<p>3、输出三元符号组 ( 0, 0, c )。其中 c
为下一个字符。然后将窗口向后滑动 len + 1
个字符，继续步骤 1。</p>
<p>我们结合实例来说明。假设窗口的大小为 10
个字符，我们刚编码过的 10 个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee</p>
<p>我们首先发现，可以和要编码字符匹配的最长串为
ab ( off = 0, len = 2 ), ab 的下一个字符为 a，我们输出三元组：(
0, 2, a )</p>
<p>现在窗口向后滑动 3
个字符，窗口中的内容为：dbbccaaaba</p>
<p>下一个字符 e
在窗口中没有匹配，我们输出三元组：( 0, 0, e )</p>
<p>窗口向后滑动 1 个字符，其中内容变为：bbccaaabae</p>
<p>我们马上发现，要编码的 aaabae 在窗口中存在(
off = 4, len = 6 )，其后的字符为 e，我们可以输出：(
4, 6, e )</p>
<p>这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。</p>
<p>解压缩的过程十分简单，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符
c 输出（如果 off 和 len 都为 0 则只输出后继字符 c
)即可还原出原始数据。</p>
<p>当然，真正实现 LZ77
算法时还有许多复杂的问题需要解决，下面我们就来对可能碰到的问题逐一加以探讨。</p>
<p><strong>编码方法</strong></p>
<p>我们必须精心设计三元组中每个分量的表示方法，才能达到较好的压缩效果。一般来讲，编码的设计要根据待编码的数值的分布情况而定。对于三元组的第一个分量——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况，这是因为字符串在与其接近的位置较容易找到匹配串，但对于普通的窗口大小（例如
4096
字节）来说，偏移值基本还是均匀分布的，我们完全可以用固定的位数来表示它。</p>
<p>编码 off 需要的位数 bitnum = upper_bound( log<sub>2</sub>(
MAX_WND_SIZE ))</p>
<p>由此，如果窗口大小为 4096，用 12
位就可以对偏移编码。如果窗口大小为 2048，用 11
位就可以了。复杂一点的程序考虑到在压缩开始时，窗口大小并没有达到
MAX_WND_SIZE，而是随着压缩的进行增长，因此可以根据窗口的当前大小动态计算所需要的位数，这样可以略微节省一点空间。</p>
<p>对于第二个分量——字符串长度，我们必须考虑到，它在大多数时候不会太大，少数情况下才会发生大字符串的匹配。显然可以使用一种变长的编码方式来表示该长度值。在前面我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实
Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我在这里介绍其中两种应用非常广泛的编码。</p>
<p>第一种叫 Golomb 编码。假设对正整数 x 进行
Golomb 编码，选择参数 m，令 </p>
<p>b = 2<sup>m</sup></p>
<p>q = INT((x - 1)/b)</p>
<p>r = x - qb - 1</p>
<p>则 x 可以被编码为两部分，第一部分是由 q 个 1
加 1 个 0 组成，第二部分为 m
位二进制数，其值为 r。我们将 m = 0, 1, 2, 3 时的
Golomb 编码表列出：</p>
<pre> 值 x m = 0 m = 1 m = 2 m = 3
-------------------------------------------------------------
1 0 0 0 0 00 0 000
2 10 0 1 0 01 0 001
3 110 10 0 0 10 0 010
4 1110 10 1 0 11 0 011
5 11110 110 0 10 00 0 100
6 111110 110 1 10 01 0 101
7 1111110 1110 0 10 10 0 110
8 11111110 1110 1 10 11 0 111
9 111111110 11110 0 110 00 10 000</pre>
<p>从表中我们可以看出，Golomb
编码不但符合前缀编码的规律，而且可以用较少的位表示较小的
x 值，而用较长的位表示较大的 x 值。这样，如果
x 的取值倾向于比较小的数值时，Golomb
编码就可以有效地节省空间。当然，根据 x
的分布规律不同，我们可以选取不同的 m
值以达到最好的压缩效果。</p>
<p>对我们上面讨论的三元组 len 值，我们可以采用
Golomb 方式编码。上面的讨论中 len 可能取 0，我们只需用
len + 1 的 Golomb 编码即可。至于参数 m 的选择，一般经验是取
3 或 4 即可。</p>
<p>可以考虑的另一种变长前缀编码叫做 γ
编码。它也分作前后两个部分，假设对 x 编码，令
q = int( log<sub>2</sub>x )，则编码的前一部分是 q 个 1
加一个 0，后一部分是 q
位长的二进制数，其值等于 x - 2<sup>q</sup>
。γ编码表如下：</p>
<pre> 值 x γ编码
---------------------
1 0
2 10 0
3 10 1
4 110 00
5 110 01
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -