1700506680
1700506681
表9-1 6种不同的信源字符
1700506682
1700506683
1700506684
1700506685
1700506686
如果要传输1000组3bit定长编码信息，那就是需要传输3000bit的数据。但是，如果按照出现的概率不同，把大概率的数字换成较短的编码，情况会有所不同。
1700506687
1700506688
1700506689
1700506690
1700506691
在以上场景中，通过更换编码，可以把原先需要用3000bit传完信息用2300bit传完，起到了一定的压缩作用。
1700506692
1700506693
哈夫曼编码要保证一个叫作“前缀编码”的原则，即任何一个编码不能是另一个编码的前缀。原因在于，这种方式在接收到编码后进行解码时，由于无法判断当前接收到的编码是否为一个信息的结束标志，所以会产生困惑。
1700506694
1700506695
由于消息中产生的冗余信息会导致存储和传输效率低下，所以涌现出了一大批着力解决这方面问题的优秀算法。根据算法压缩时所涉及的场景，可以分为两大类，一类是无损压缩，另一类是有损压缩。
1700506696
1700506697
数据科学家养成手册 [:1700503566]
1700506698
9.5.1 无损压缩
1700506699
1700506700
刚刚提到的对哈夫曼编码的应用就是无损压缩的一个最简单的雏形范例。无损压缩用于在压缩过程中不允许出现信息丢失的情况。例如，个人办公电脑中的各种客户资料，以及服务器中的日志、交易信息等，无论以什么理由、使用什么压缩算法对其进行压缩，都不能以丢失信息为代价。
1700506701
1700506702
一些无损压缩基于字典压缩原理（Dictionary Compression）。字典压缩的原理和刚刚说的哈夫曼编码的思路类似，只不过它所统计的对象通常不是以单一字符为基础，而是以整个“单词”为基础。这里的“单词”是一个广义的概念，可以理解为连续出现的字符串。字典压缩的算法很多，例如1977年出现的LZ77算法、1993年出现的DEFLATE算法及1996年出现的LZO算法等，到现在的应用仍然非常广泛。
1700506703
1700506704
以LZ77算法为例，围绕这个“字典”应该如何建立的问题，算法的作者下了一番苦功，要找出一段字符串中的重复结构信息，并根据它们来动态规划这个字典的建立规则。
1700506705
1700506706
LZ77算法使用“滑动窗口”的方法来寻找文件中的相同部分，即匹配串（如图9-7所示）。这个串理论上可以是任意的串，并不局限于文字或文本信息。
1700506707
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表示“(之间的距离, 匹配长度)对”。