1700506708
1700506709
1700506710
1700506711
图9-7 LZ77算法的字符串匹配过程
1700506712
1700506713
1700506714
1700506715
1700506716
1700506717
1700506718
1700506719
LZ77算法从文件的起始处开始，一个字节一个字节地向后处理。定义整个字符串（文件）为S，长度为l(S)。其中，S(1, j)为S的前缀，并且。对于S(1, j)且i≤j，L(i)为满足的最大值，那么。这样，字符串就和匹配了，匹配长度为l。此时，定义一个p来记录最长匹配时的i值，并满足。
1700506720
1700506721
在这个计算模型中，一个固定大小的窗口随着处理的字节不断向后滑动。对于文件中的每个字节，用当前处理字节开始的串和窗口中的每个串进行匹配，以寻找最长的匹配串。窗口中的每个串是指窗口中以每个字节开始的子串。如果当前处理字节开始的串在窗口中有匹配串，就用
1700506722
1700506723
(之间的距离, 匹配长度)
1700506724
1700506725
这样一对信息来替换当前串。然后，从刚才处理完的串之后的那个字节开始继续处理。如果当前处理字节开始的串在窗口中没有匹配串，就不做改动地输出当前处理字节。
1700506726
1700506727
处理文件中第1个字节时，窗口在当前处理字节之前（也就是还没有滑到文件上时）没有任何内容，被处理的字节就会不做改动地输出。随着处理的不断向后，窗口滑入文件的部分越来越多。最后，整个窗口滑入文件，并在文件上向后滑动，直到文件结束。
1700506728
1700506729
为了在解压缩时可以区分“没有匹配的字节”和“(之间的距离, 匹配长度)对”，我们还需要在每个“没有匹配的字节”或者“(之间的距离, 匹配长度)对”之前，放上1位来避免混乱。例如，用0表示“没有匹配的字节”，用1表示“(之间的距离, 匹配长度)对”。
1700506730
1700506731
在实际使用中，需要固定“（之间的距离，匹配长度）对”中的“之间的距离”和“匹配长度”所使用的位数。因为要固定“之间的距离”所使用的位数，所以采用了固定大小的窗口。例如，窗口的大小为32KB，那么用15位（215=32K）就可以保存0～32K范围内的任何一个值。另外，需要限定最大的匹配长度，这样“匹配长度”所使用的位数也就固定了。
1700506732
1700506733
此外，在实际使用中，我们还将设定一个最小匹配长度，只有当两个串的匹配长度大于最小匹配长度时，我们才认为这是一个匹配。例如，“距离”使用15位，“长度”使用8位，那么“（之间的距离, 匹配长度）对”将使用23位，也就是差1位3字节。如果匹配长度小于3字节，用“（之间的距离, 匹配长度）对”进行替换的话，不但没有压缩，长度反而会增大，所以需要设置一个最小匹配长度。
1700506734
1700506735
解压缩的过程是这样的：从文件开始到文件结束，每次先读1位标志位，通过这个标志位来判断下面是一个“（之间的距离, 匹配长度）对”，还是一个没有改动的字节。如果是一个“（之间的距离, 匹配长度）对”，就读出固定位数的“（之间的距离, 匹配长度）对”，然后根据对中的信息将匹配串输出到当前位置。如果是一个没有改动的字节，就读出1字节，然后输出该字节。
1700506736
1700506737
可以看到，LZ77算法在压缩时需要做大量的匹配工作，而在解压缩时需要做的工作很少，也就是说，解压缩相对于压缩的速度要快得多。这对需要进行一次压缩、多次解压缩的场合是一个巨大的优势。而且，重复的内容越多，重复的字串越长，LZ77算法的压缩效果就越好——这也是不言而喻的。
1700506738
1700506739
虽然不是每个人都有机会去编写LZ77这样的压缩算法，但每个服务器开发人员每天都会和它“亲密接触”。LZ77算法是我们在Linux系统中使用的GZip算法的蓝本，真可谓“润物细无声”。
1700506740
1700506741
如果要测算LZ77算法的压缩率，可以找一些体积较大的文件来做压缩测试，效果总体来说还是不错的（尤其是文本文件）。
1700506742
1700506743
我用手边的文本文件做了一个简单的测试。
1700506744
1700506745
[root@ann char-rnn-master]# find /-type f-size +1000k-name “*.txt”/usr/lib/python2.7/site-packages/netaddr/eui/oui.txt/usr/share/perl5/Unicode/Collate/allkeys.txt/usr/share/libhangul/hanja/hanja.txt/usr/share/hwdata/iab.txt/usr/share/hwdata/oui.txt/ml/rnn/char-rnn-master/data/tinyshakespeare.1/input.txt
1700506746
1700506747
首先，用find命令找到本机上大于1000KB的 .txt文件，通过命令查看其中第1个文件。
1700506748
1700506749
[root@ann char-rnn-master]# ls-la /usr/lib/python2.7/site-packages/netaddr/eui/oui.txt-rw-r—r—. 1 root root 2249223 Sep 22 2010 /usr/lib/python2.7/site-packages/netaddr/eui/oui.txt
1700506750
1700506751
文件大小为2249223字节，即2.25MB左右。
1700506752
1700506753
[root@ann char-rnn-master]# gzip-9 /usr/lib/python2.7/site-packages/netaddr/eui/oui.txt
1700506754
1700506755
使用gzip命令将其压缩，参数-9表示使用压缩率最小的原则。
1700506756
1700506757
[root@ann char-rnn-master]# ll /usr/lib/python2.7/site-packages/netaddr/eui/oui.txt.gztotal 1572-rw-r—r—. 1 root root 673972 Sep 22 2010 oui.txt.gz