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
1700506758
1700506759
压缩完成后，文件为637972字节，压缩率约为28.36％，效率还是很高的。这类使用统计方法来动态规划字典的算法，应用非常普遍。
1700506760
1700506761
数据科学家养成手册 [:1700503567]
1700506762
9.5.2 有损压缩
1700506763
1700506764
比起无损压缩，有损压缩更是一种每个人每天都在被动接触的一大类算法。这种压缩中允许有一定损失的场景多见于模拟信号的处理。
1700506765
1700506766
人类通过自身的视觉、听觉等感知到的模拟信号多为连续不断的信号。例如，有一个在时域上连续的声音信号，在以数字信号的形式对其进行记录时，需要对每个时间段中波形的波幅进行描述。用这种以离散方式记录波形的波幅，使得取样时间越宽，记录内容就与原始内容相差越大；取样时间越窄，记录内容就与原始内容相差越小。但是，要想采用数字信号对这些信息进行记录，势必无法避开从连续的模拟信号到离散的数字信号的转换过程（如图9-8所示）。从无限和连续，到有限和离散，无论怎么做，损失在这个环节都是无法避免的。
1700506767
1700506768
1700506769
1700506770
1700506771
图9-8 连续信号和离散信号
1700506772
1700506773
人类的视觉和听觉的敏感程度是有限的，也就是说，人类可以天然地容纳一些视听方面的信息损失，这也给多媒体信息的压缩带来了可能——只要使取样细密到一定程度，人类就不容易感知到其中的信息损失，所以，很多情况下也就没有必要去无限地追求这种取样的细密度。下面我们来认识一下这方面的应用。
1700506774
1700506775
1．音频
1700506776
1700506777
WAV文件格式是由微软研发的一种声音文件格式。标准格式的WAV文件和音乐CD使用的格式一样，都采用44.1K的采样频率，也就是在1秒之内进行44100次采样，最后生成的每一秒的声音信息都有44100个点的波幅来描述。这种采样频率已经非常高了，超出这个范围，人的耳朵就很难感知其中的变化了。
1700506778
1700506779
以人声为例，将这种声波的波形画出来，由于线条堆叠在一起，所以无法看出其形状（如图9-9所示）。但是，我们可以把它看成一个f(t)函数，每一瞬间都是在0点上下往复抖动的周期为60～4000Hz的波幅不断变化的曲线。