Ziv和Lempel于1977年发表题为“顺序数据压缩的一个通用算法（A Universal Algorithm for Sequential Data Compression ）”的论文，论文中描述的算法被后人称为LZ77算法。值得说的是，LZ77严格意义上来说不是一种算法，而是一种编码理论。同Huffman编码一样，只定义了原理，并没有定义如何实现。基于这种理论来实现的算法才称为LZ77算法，或者人们更愿意称为LZ77变种。实际上这类算法已经有很多了，比如LZSS、LZB、LZH等。至今，几乎我们日常使用的所有通用压缩工具，象ARJ，PKZip，WinZip，LHArc，RAR，GZip，ACE，ZOO，TurboZip，Compress，JAR??甚至许多硬件如网络设备中内置的压缩算法，无一例外，都可以最终归结为这两个以色列人的杰出贡献。

LZ77是一种基于字典的算法，它将长字符串（也称为短语）编码成短小的标记，用小标记代替字典中的短语，从而达到压缩的目的。也就是说，它通过用小的标记来代替数据中多次重复出现的长串方法来压缩数据。其处理的符号不一定是文本字符，可以是任意大小的符号。

不同的基于字典的算法使用不同的方法来维护它们的字典。LZ77使用的是一个前向缓冲区和一个滑动窗口。

LZ77首先将一部分数据载入前向缓冲区。为了便于理解前向缓冲区如何存储短语并形成字典，我们将缓冲区描绘成S₁，...，S_n的字符序列，P_b是由字符组成的短语集合。从字符序列S₁，...，S_n，组成n个短语，定义如下：

P_b = {(S₁),(S₁,S₂),...,(S₁,...,S_n)}

例如，如果前向缓冲区包含字符(A,B,D)，那么缓冲区中的短语为{(A),(A,B),(A,B,D)}。

一旦数据中的短语通过前向缓冲区，那么它将移动到滑动窗口中，并变成字典的一部分。为理解短语是如何在滑动窗口中表示的，首先，把窗口想象成S₁，...，S_m的字符序列，且P_w是由这些字符组成的短语集合。从序列S₁，...，S_m产生短语数据集合的过程如下：

P_w = {P₁,P₂,...,P_m}，其中P_i = {(S_i),(S_i,S_i+1),...,(S_i,S_i+1,...,S_m)}

例如，如果滑动窗口中包含符号(A,B,C)，那么窗口和字典中的短语为{(A),(A,B),(A,B,C),(B),(B,C),(C)}。

LZ77算法的主要思想就是在前向缓冲区中不断寻找能够与字典中短语匹配的最长短语。以上面描述的前向缓冲区和滑动窗口为例，其最长的匹配短语为(A,B)。

前向缓冲区和滑动窗口之间的匹配有两种情况：要么找到一个匹配短语，要么找不到匹配的短语。当找到最长的匹配时，将其编码成短语标记。

短语标记包含三个部分：1、滑动窗口中的偏移量（从头部到匹配开始的前一个字符）；2、匹配中的符号个数；3、匹配结束后，前向缓冲区中的第一个符号。

当没有找到匹配时，将未匹配的符号编码成符号标记。这个符号标记仅仅包含符号本身，没有压缩过程。事实上，我们将看到符号标记实际上比符号多一位，所以会出现轻微的扩展。

一旦把n个符号编码并生成相应的标记，就将这n个符号从滑动窗口的一端移出，并用前向缓冲区中同样数量的符号来代替它们。然后，重新填充前向缓冲区。这个过程使滑动窗口中始终有最新的短语。滑动窗口和前向缓冲区具体维护的短语数量由它们自身的容量决定。

下图（1）展示了用LZ77算法压缩字符串的过程，其中滑动窗口大小为8个字节，前向缓冲区大小为4个字节。在实际中，滑动窗口典型的大小为4KB（4096字节）。前向缓冲区大小通常小于100字节。

图（1）：使用LZ77算法对字符串ABABCBABABCAD进行压缩

我们通过解码标记和保持滑动窗口中符号的更新来解压缩数据，其过程类似于压缩过程。当解码每个标记时，将标记编码成字符拷贝到滑动窗口中。每当遇到一个短语标记时，就在滑动窗口中查找相应的偏移量，同时查找在那里发现的指定长度的短语。每当遇到一个符号标记时，就生成标记中保存的一个符号。下图（2）展示了解压缩图（1）中数据的过程。

图（2）：使用LZ77算法对图（1）中压缩的字符串进行解压缩

用LZ77算法压缩的程度取决于很多因素，例如，选择滑动窗口的大小，为前向缓冲区设置的大小，以及数据本身的熵。最终，压缩的程度取决于能匹配的短语的数量和短语的长度。大多数情况下，LZ77比霍夫曼编码有着更高的压缩比，但是其压缩过程相对较慢。

用LZ77算法压缩数据是非常耗时的，国为要花很多时间寻找窗口中的匹配短语。然而在通常情况下，LZ77的解压缩过程要比霍夫曼编码的解压缩过程耗时要少。LZ77的解压缩过程非常快是因为每个标记都明确地告诉我们在缓冲区中哪个位置可以读取到所需要的符号。事实上，我们最终只从滑动窗口中读取了与原始数据数量相等的符号而已。

lz77_compress

int lz77_compress(const unsigned char *original, unsigned char **compressed, int size);

返回值：如果数据压缩成功，返回压缩后数据的字节数；否则返回-1；

描述：  用LZ77算法压缩缓冲区original中的数据，original包含size个字节的空间。压缩后的数据存入缓冲区compressed中。lz77_compress需要调用malloc来动态的为compressed分配存储空间，当这块空间不再使用时，由调用者调用函数free来释放空间。

复杂度：O(n)，其中n是原始数据中符号的个数。

lz77_uncompress

int lz77_uncompress(const unsigned char *compressed, unsigned char **original);

返回值：如果解压缩数据成功，返回恢复后数据的字节数；否则返回-1；

描述：  用LZ77算法解压缩缓冲区compressed中的数据。假定缓冲区包含的数据之前由lz77_compress压缩。恢复后的数据存入缓冲区original中。lz77_uncompress函数调用malloc来动态的为original分配存储空间。当这块存储空间不再使用时，由调用者调用函数free来释放空间。

复杂度：O（n）其中n是原始数据中符号的个数。

LZ77算法，通过一个滑动窗口将前向缓冲区中的短语编码成相应的标记，从而达到压缩的目的。在解压缩的过程中，将每个标记解码成短语或符号本身。要做到这些，必须要不断地更新窗口，这样，在压缩过程中的任何时刻，窗口都能按照规则进行编码。在本节所有的示例中，原始数据中的一个符号占一个字节。

lz77_compress

lz77_compress操作使用LZ77算法来压缩数据。首先，它将数据中的符号写入压缩数据的缓冲区中，并同时初始化滑动窗口和前向缓冲区。随后，前向缓冲区将用来加载符号。

压缩发生在一个循环中，循环会持续迭代直到处理完所有符号。使用ipos来保存原始数据中正在处理的当前字节，并用opos来保存向压缩数据缓冲区写入的当前位。在循环的每次迭代中，调用compare_win来确定前向缓冲区与滑动窗口中匹配的最长短语。函数compare_win返回最长匹配串的长度。