lz77.txt

LZ777压缩原理

   值 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）。

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

如何查找匹配串

在滑动窗口中查找最长的匹配串，大概是 LZ77 算法中的核心问题。容易知道，LZ77 算法中空间和时间的消耗集中于对匹配串的查找算法。每次滑动窗口之后，都要进行下一个匹配串的查找，如果查找算法的时间效率在 O(n2) 或者更高，总的算法时间效率就将达到 O(n3)，这是我们无法容忍的。正常的顺序匹配算法显然无法满足我们的要求。事实上，我们有以下几种可选的方案。

1、限制可匹配字符串的最大长度（例如 20 个字节），将窗口中每一个 20 字节长的串抽取出来，按照大小顺序组织成二叉有序树。在这样的二叉有序树中进行字符串的查找，其效率是很高的。树中每一个节点大小是 20(key) + 4(off) + 4(left child) + 4(right child) = 32。树中共有 MAX_WND_SIZE - 19 个节点，假如窗口大小为 4096 字节，树的大小大约是 130k 字节。空间消耗也不算多。这种方法对匹配串长度的限制虽然影响了压缩程序对一些特殊数据（又很长的匹配串）的压缩效果，但就平均性能而言，压缩效果还是不错的。

2、将窗口中每个长度为 3 （视情况也可取 2 或 4）的字符串建立索引，先在此索引中匹配，之后对得出的每个可匹配位置进行顺序查找，直到找到最长匹配字符串。因为长度为 3 的字符串可以有 2563 种情况，我们不可能用静态数组存储该索引结构。使用 Hash 表是一个明智的选择。我们可以仅用 MAX_WND_SIZE - 1 的数组存储每个索引点，Hash 函数的参数当然是字符串本身的 3 个字符值了，Hash 函数算法及 Hash 之后的散列函数很容易设计。每个索引点之后是该字符串出现的所有位置，我们可以使用单链表来存储每一个位置。值得注意的是，对一些特殊情况比如 aaaaaa...之类的连续字串，字符串 aaa 有很多连续出现位置，但我们无需对其中的每一个位置都进行匹配，只要对最左边和最右边的位置操作就可以了。解决的办法是在链表节点中纪录相同字符连续出现的长度，对连续的出现位置不再建立新的节点。这种方法可以匹配任意长度的字符串，压缩效果要好一些，但缺点是查找耗时多于第一种方法。

3、使用字符树( trie )来对窗口内的字符串建立索引，因为字符的取值范围是 0 - 255，字符树本身的层次不可能太多，3 - 4 层之下就应该换用其他的数据结构例如 Hash 表等。这种方法可以作为第二种方法的改进算法出现，可以提高查找速度，但空间的消耗较多。

如果对窗口中的数据进行索引，就必然带来一个索引位置表示的问题，即我们在索引结构中该往偏移项中存储什么数据：首先，窗口是不断向后滑动的，我们每次将窗口向后滑动一个位置，索引结构就要作相应的更新，我们必须删除那些已经移动出窗口的数据，并增加新的索引信息。其次，窗口不断向后滑动的事实使我们无法用相对窗口左边界的偏移来表示索引位置，因为随着窗口的滑动，每个被索引的字符串相对窗口左边界的位置都在改变，我们无法承担更新所有索引位置的时间消耗。

解决这一问题的办法是，使用一种可以环形滚动的偏移系统来建立索引，而输出匹配字符串时再将环形偏移还原为相对窗口左边界的真正偏移。让我们用图形来说明，窗口刚刚达到最大时，环形偏移和原始偏移系统相同：

偏移：     0 1 2 3 4 ......                                              Max
          |--------------------------------------------------------------|
环形偏移： 0 1 2 3 4 ......                                              Max
窗口向后滑动一个字节后，滑出窗口左端的环形偏移 0 被补到了窗口右端：

偏移：     0 1 2 3 4 ......                                              Max
          |--------------------------------------------------------------|
环形偏移： 1 2 3 4 5 ......                                           Max 0
窗口再滑动 3 个子节后，偏移系统的情况是：

偏移：     0 1 2 3 4 ......                                              Max
          |--------------------------------------------------------------|
环形偏移： 4 5 6 7 8......                                      Max 0 1 2 3
依此类推。

我们在索引结构中保存环形偏移，但在查找到匹配字符串后，输出的匹配位置 off 必须是原始偏移（相对窗口左边），这样才可以保证解码程序的顺利执行。我们用下面的代码将环形偏移还原为原始偏移：

// 由环形 off 得到真正的off(相对于窗口左边)
// 其中 nLeftOff 为当前与窗口左边对应的环形偏移值
int GetRealOff(int off)
{
    if (off >= nLeftOff)
        return off - nLeftOff;
    else
        return (_MAX_WINDOW_SIZE - (nLeftOff - off));
}
这样，解码程序无需考虑环形偏移系统就可以顺利高速解码了。

资源

结合上面的讨论，典型的 LZ77 算法应当不难实现，我们本章给出的源码是一个较为特殊的实现。

示例程序 lz77.exe 使用对匹配串和单个字符分类输出的模型，输出匹配串时，off 采用定长编码，len 采用γ编码。索引结构采用 2 字节长字符串的索引，使用 256 * 256 大小的静态数组存储索引点，每个索引点指向一个位置链表。链表节点考虑了对 aaaaa... 之类的重复串的优化。

示例程序的独特之处在于使用了 64k 大小的固定长度窗口，窗口不做滑动（因此不需要环形偏移系统，也节省了删除索引点的时间）。压缩函数每次只对最多 64k 长的数据进行压缩，主函数将原始文件分成 64k 大小的块逐个压缩存储。使用这种方法首先可以增大匹配的概率，字符串可以在 64k 空间内任意寻找最大匹配串，以此提高压缩效率。其次，这种方法有利于实现解压缩的同步。也就是说，利用这种方法分块压缩的数据，很容易从原始文件中间的任何一个位置开始解压缩，这尤其适用于全文检索系统中全文信息的保存和随机读取。

结合上述示例程序，王笨笨开发了可压缩多个文件并可同步（随机）解压缩的文件级接口，但此接口并非自由代码(free code)。如果需要可以和王笨笨联系。

示例程序 lz77 的所有源文件被包装在文件 lz77.zip 中，由王笨笨编写，在 Visual C++ 5.0 环境下编译通过。其使用方法是：

压缩： lz77 c 源文件名 压缩文件名

解压缩： lz77 d 压缩文件名 源文件名