LZ77算法的基本原理 ---png 图片数据块的压缩算法

让我们熟悉一下 LZ77 算法的基本流程。

1、从当前压缩位置开始，考察未编码的数据，并试图在滑动窗口中找出最长的匹配字符串，如果找到，则进行步骤 2，否则进行步骤 3。

2、输出三元符号组 ( off, len, c )。其中 off 为窗口中匹配字符串相对窗口边界的偏移，len 为可匹配的长度，c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。

3、输出三元符号组 ( 0, 0, c )。其中 c 为下一个字符。然后将窗口向后滑动 len + 1 个字符，继续步骤 1。

我们结合实例来说明。假设窗口的大小为 10 个字符，我们刚编码过的 10 个字符是：abcdbbccaa，即将编码的字符为：abaeaaabaee

我们首先发现，可以和要编码字符匹配的最长串为 ab ( off = 0, len = 2 ), ab 的下一个字符为 a，我们输出三元组：( 0, 2, a )

现在窗口向后滑动 3 个字符，窗口中的内容为：dbbccaaaba

下一个字符 e 在窗口中没有匹配，我们输出三元组：( 0, 0, e )

窗口向后滑动 1 个字符，其中内容变为：bbccaaabae

我们马上发现，要编码的 aaabae 在窗口中存在( off = 4, len = 6 )，其后的字符为 e，我们可以输出：( 4, 6, e )

这样，我们将可以匹配的字符串都变成了指向窗口内的指针，并由此完成了对上述数据的压缩。

解压缩的过程十分简单，只要我们向压缩时那样维护好滑动的窗口，随着三元组的不断输入，我们在窗口中找到相应的匹配串，缀上后继字符 c 输出（如果 off 和 len 都为 0 则只输出后继字符 c )即可还原出原始数据。

当然，真正实现 LZ77 算法时还有许多复杂的问题需要解决，下面我们就来对可能碰到的问题逐一加以探讨。

编码方法

我们必须精心设计三元组中每个分量的表示方法，才能达到较好的压缩效果。一般来讲，编码的设计要根据待编码的数值的分布情况而定。对于三元组的第一个分量——窗口内的偏移，通常的经验是，偏移接近窗口尾部的情况要多于接近窗口头部的情况，这是因为字符串在与其接近的位置较容易找到匹配串，但对于普通的窗口大小（例如 4096 字节）来说，偏移值基本还是均匀分布的，我们完全可以用固定的位数来表示它。

编码 off 需要的位数 bitnum = upper_bound( log2( MAX_WND_SIZE ))

由此，如果窗口大小为 4096，用 12 位就可以对偏移编码。如果窗口大小为 2048，用 11 位就可以了。复杂一点的程序考虑到在压缩开始时，窗口大小并没有达到 MAX_WND_SIZE，而是随着压缩的进行增长，因此可以根据窗口的当前大小动态计算所需要的位数，这样可以略微节省一点空间。

对于第二个分量——字符串长度，我们必须考虑到，它在大多数时候不会太大，少数情况下才会发生大字符串的匹配。显然可以使用一种变长的编码方式来表示该长度值。在前面我们已经知道，要输出变长的编码，该编码必须满足前缀编码的条件。其实 Huffman 编码也可以在此处使用，但却不是最好的选择。适用于此处的好的编码方案很多，我在这里介绍其中两种应用非常广泛的编码。

第一种叫 Golomb 编码。假设对正整数 x 进行 Golomb 编码，选择参数 m，令

b = 2m

q = INT((x - 1)/b)

r = x - qb - 1

则 x 可以被编码为两部分，第一部分是由 q 个 1 加 1 个 0 组成，第二部分为 m 位二进制数，其值为 r。我们将 m = 0, 1, 2, 3 时的 Golomb 编码表列出：

     值 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
从表中我们可以看出，Golomb 编码不但符合前缀编码的规律，而且可以用较少的位表示较小的 x 值，而用较长的位表示较大的 x 值。这样，如果 x 的取值倾向于比较小的数值时，Golomb 编码就可以有效地节省空间。当然，根据 x 的分布规律不同，我们可以选取不同的 m 值以达到最好的压缩效果。

对我们上面讨论的三元组 len 值，我们可以采用 Golomb 方式编码。上面的讨论中 len 可能取 0，我们只需用 len + 1 的 Golomb 编码即可。至于参数 m 的选择，一般经验是取 3 或 4 即可。

可以考虑的另一种变长前缀编码叫做 γ 编码。它也分作前后两个部分，假设对 x 编码，令 q = int( log2x )，则编码的前一部分是 q 个 1 加一个 0，后一部分是 q 位长的二进制数，其值等于 x - 2q 。γ编码表如下：

     值 x      γ编码
---------------------
      1         0
      2        10 0
      3        10 1
      4       110 00
      5       110 01
      6       110 10
      7       110 11
      8      1110 000
      9      1110 001
其实，如果对 off 值考虑其倾向于窗口后部的规律，我们也可以采用变长的编码方法。但这种方式对窗口较小的情况改善并不明显，有时压缩效果还不如固定长编码。

对三元组的最后一个分量——字符 c，因为其分布并无规律可循，我们只能老老实实地用 8 个二进制位对其编码。

根据上面的叙述，相信你一定也能写出高效的编码和解码程序了。

另一种输出方式

LZ77 的原始算法采用三元组输出每一个匹配串及其后续字符，即使没有匹配，我们仍然需要输出一个 len = 0 的三元组来表示单个字符。试验表明，这种方式对于某些特殊情况（例如同一字符不断重复的情形）有着较好的适应能力。但对于一般数据，我们还可以设计出另外一种更为有效的输出方式：将匹配串和不能匹配的单个字符分别编码、分别输出，输出匹配串时不同时输出后续字符。

我们将每一个输出分成匹配串和单个字符两种类型，并首先输出一个二进制位对其加以区分。例如，输出 0 表示下面是一个匹配串，输出 1 表示下面是一个单个字符。

之后，如果要输出的是单个字符，我们直接输出该字符的字节值，这要用 8 个二进制位。也就是说，我们输出一个单个的字符共需要 9 个二进制位。

如果要输出的是匹配串，我们按照前面的方法依次输出 off 和 len。对 off，我们可以输出定长编码，也可以输出变长前缀码，对 len 我们输出变长前缀码。有时候我们可以对匹配长度加以限制，例如，我们可以限制最少匹配 3 个字符。因为，对于 2 个字符的匹配串，我们使用匹配串的方式输出并不一定比我们直接输出 2 个单个字符（需要 18 位）节省空间（是否节省取决于我们采用何种编码输出 off 和 len）。

这种输出方式的优点是输出单个字符的时候比较节省空间。另外，因为不强求每次都外带一个后续字符，可以适应一些较长匹配的情况。