寻味经典|什么是神奇的无损压缩算法[1]

1.开场白

好久不见，我是挤牙膏号主大白。

已经有一个多月没有更新文章了，最近花了些时间想了下今年要写些什么，最终确定了两个系列：

• 寻味经典系列

寻味经典 ：揭秘经典算法、朴实功能背后闪闪发光的东西。

• 探索未知系列

探索未知 ：介绍多个领域最前沿、最有趣的新发现和新进展。

这两个系列背后的想法也很朴实：无论是做研究还是工作，都要经过长期积累，才能深刻理解存在的问题、解决方法、瓶颈所在、突破方向等。

我们都是站在前人的肩膀上来做事情的，在享受肩膀带来便利的同时，我们也要努力去提升肩膀的高度，哪怕只有一点点。

马上开始2021年第一篇文章的阅读之旅吧！

2.压缩算法的理论基础

任何适用于工程的算法都有它的数学和信息学理论基础， 就如同我们写论文要先做仿真，理论给实践提供了一定的方向和依据。

对于压缩算法来说，我们肯定会问：这是压缩极限了吗？还有提升空间吗？

2.1 信息学之父

聊到这里，不得不提到信息学之父 克劳德·艾尔伍德·香农 ，来简单看下他的履历简介：

克劳德·艾尔伍德·香农（Claude Elwood Shannon ，1916年4月30日—2001年2月24日）是美国数学家、信息论的创始人。

1936年获得密歇根大学学士学位，1940年在麻省理工学院获得硕士和博士学位，1941年进入贝尔实验室工作，1956年他成为麻省理工学院客座教授，并于1958年成为终生教授，1978年成为名誉教授。

香农提出了信息熵的概念，为信息论和数字通信奠定了基础，他也是一位著名的密码破译者，他在贝尔实验室破译团队主要追踪德国飞机和火箭。

相关论文：1938年的硕士论文《继电器与开关电路的符号分析》，1948年的《通讯的数学原理》和1949年的《噪声下的通信》，1949年的另外一篇重要论文《Communication Theory of Secrecy Systems》。

看完这段介绍，我感觉自己被秒成了粉末了，只能默默打开了网抑云，感受一下什么是：”生而为人，我很遗憾。”

2.3 信息熵entropy

熵本身是一个热力学范畴的概念，描述了一种混乱程度和无序性， 这是个特别有用的概念，因为自然界的本质就是无序和混乱。

举个不恰当的例子，我们经常看娱乐圈八卦新闻的时候，会说信息量很大，上热搜了等等，那么我们该如何去度量信息量呢？

香农大神解决了信息的度量问题，让一种无序不确定的状态有了数学语言的描述。

在1948年的论文《A Mathematical Theory of Communication》中作者将Entropy与Uncertainty等价使用的。

文中提出信息熵是信息不确定性（Uncertainty）的度量，不确定性越大，信息熵越大。

论文地址 ：http://people.math.harvard.edu/~ctm/home/text/others/shannon/entropy/entropy.pdf

在论文的第6章给出信息熵的几个属性以及信息熵和不确定性之间的联系：

简单翻译一下：

• 信息熵是随着概率连续变化的；

• 如果构成事件的各个因素的概率相等，那么信息熵随构成因素总数n的增加而增加，即选择越多，不确定性越大。

• 当一个选择可以分解为两个连续选择时，分解前后的熵值应该相等，不确定性相同。

我们假设一个事件有多种可能的选择，每个选择的概率分别记为p1,p2….pn，文章进一步给出了概率和信息熵的公式：

其中k为一个正常量， 经过前面的一些分析，我们基本上快懵圈了，太难了。 我们暂且记住一个结论： 信息是可度量的，并和内容中源字符串的概率分布密切相关。

3. 数据压缩的本质

既然有了理论的支持，那么我们来想一想 如何进行数据压缩呢？

压缩的前提是冗余的存在，消除冗余就是压缩，用更少的信息来完整表达信息，来看下百科的定义：

数据压缩是指在不丢失有用信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率，

需要按照一定的算法对数据进行重新组织，减少数据的冗余和存储的空间的一种技术方法。

举几个简单的例子：

• “北京交通大学的交通信息工程及控制专业不错”  和 “北交的交控专业不错”

在上述文本中”北京交通大学”可以用”北交”代替，”交通信息工程及控制专业”可以用”交控专业”代替。

• “aaaaaaaaxxxxxxkkkkkkzzzzzzzzzz” 和 “8a6x6k10z”

在上述文本中有比较明显的局部重复，比如a出现了8次，z出现了10次，如果我们在分析了输入字符的分布规律之后，确定了”重复次数+字符”的规则，就可以进行替换了。

3.1 概率分布和数据编码

本质上来说， 数据压缩就是找到待压缩内容的概率分布，再按照一定的编码算法，将那些出现概率高的部分代替成更短的形式 。

所以输入内容重复的部分越多，就可以压缩地越小，压缩率越高，如果内容几乎没有重复完全随机，就很难压缩。

这个和我们平时优化代码性能的思路非常相似，热点代码的优化才能带来更大的收益。