1700506658
数据科学家养成手册 [:1700503565]
1700506659
数据科学家养成手册 9.5 编码与压缩
1700506660
1700506661
有了信息熵公式以后，信息学的发展就变得与原来大为不同。为了提高存储和传输的效率，越来越多的科学家致力于研究通过高效的编码算法和压缩算法来保证在不丢失信息的情况下使占用的空间或信道最少的问题。
1700506662
1700506663
早在20世纪50年代，美国的信息学教授戴维·哈夫曼(4)（如图9-6所示）还在麻省理工学院读博士的时候，在一篇名为A Method for the Construction of Minimum-Redundancy Codes的论文中就提出了一种编码方式，这就是著名的哈夫曼编码（Huffman Coding）。
1700506664
1700506665
在哈特莱提出的I=log2m的信息量计算公式中，通过信源种类m的数量可以得出使用多少位介质来表示一个信息。以1字节的二进制数据为例，它有8bit，最多可以表示m为256的情况。如果要传输1000字节，则需要在信道上传输1000组诸如01010101、10100111、11000110这样的8位编码，共8000bit。
1700506666
1700506667
1700506668
1700506669
1700506670
图9-6 戴维·哈夫曼
1700506671
1700506672
而根据香农的信息熵公式
1700506673
1700506674
1700506675
1700506676
1700506677
可以很快得出一个推论，那就是：只要每种信源产生的概率不均等，那么在刚刚这种场景中，传输1000组编码理论上肯定可以使用少于8000bit的数据，方法就是用比较短的编码来表示高频出现的字符。
1700506678
1700506679
我们以传输6种不同的字符信息为例（如表9-1所示）。
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