初探信息论

这篇文章是我在 Lean Cloud的内部分享。信息论是个很有意思的东西,我选择这个主题的原因 主要是为了防止某些人看到第一张 ppt 就一眼望到底,现在看来这个目的还是达到了。 其实信息论的应用主要是在通信领域,在信息学中一般就只能给个下界,还很 ideal。 去 Google 上搜 Information Theory in Computer Science 的话确实能找到那么几个学校开了这门课, 但是课的内容还是比较偏通信,压缩这几个领域的。反正这篇文章大家就当理性愉悦看着玩吧, 这大概是最水的理性愉悦了。

信息熵

信息论的核心是一个信息熵的概念。熵在物理里面反映的是一个系统的混乱程度, 在信息论里边有时候说熵反映了一个信息的度量,即事件 X 的信息熵反映的是当 X 确定之后能得到的信息量的多少,与 X 的真实值没有关系。

听起来还是很玄乎,总之对于一个随机事件 X,我们希望有这样一个量 H(X) 来反映他的某些属性:

  • H(X) ≥0
  • X 的概率密度越分散,H(X) 越大
  • 对于两个独立随机事件 X,Y,有 H(X,Y) = H(X) + H(Y)
  • H(X Y) + H(Y) = H(X,Y)

然后香农就证出来满足上面条件的式子是:

  • H(X) = - ∑ P_i * lb(P_i)

有时间的同学可以自己验证一下。这里最重要的是最后一个式子, 它意味着信息熵可以直接进行加减操作。有时候我们也会把式子中的 H(X|Y) 和 H(Y) 叫做信息量。得到上面这个表达式之后,可以推出一些显而易见的性质:

  • 当 X 的取值有 n 种可能时,H(X) ≤lb(n), 当且仅当 X 是 uniform 的时候取等号

一个非常经典的问题是,你手里有九个硬币和一个天平,九个硬币中有八个重量是一样的, 另外有一个假币重量比其他的轻,问你最少秤几次可以找出假币。九个硬币的情况都是套路了, 如果用信息论的视角来看的话,第一次分成三堆,恰好使这次比较的信息量达到最大值 lb(3), 第二次同理。知道了这个原理,很容易就可以推广到 n 个硬币的情况,假币不知道轻重的情况, m 个假币的情况,只要让每次秤得到的信息量最大即可。

排序

我们知道,基于比较的排序算法时间复杂度下限是 O(nlogn) 的,用信息论的观点来看, 每次比较只有两种结果,得到的信息量肯定小于 1,而排序问题有 n! 种解法,如果每个解的可能性一样的话, 它的信息量就是 lb(n!) 的,把这两个数字除一下就可以得到 nlog(n) 的复杂度下界了。

信息论的思考方式还告诉我们,要使每次比较的信息量尽量接近 1, 就要使被比较的结果是大于的概率尽量接近 0.5,这也为随机版快排为什么这么快找到了一个合理的解释: 我们随机选取的中间数跟数组其他元素比较,得到两种结果的概率基本上是一样的,因此在平均情况下, 快排所需要的比较次数是最少的。相比之下,堆排的效率就显得比较低了:每次把堆顶 pop 出来, 用堆底元素下沉的方法更新堆的过程中,堆底元素跟上层元素进行比较的结果几乎总是大于的, 这直接导致了堆排的比较次数明显大于快排。建议实现堆排的时候,不用堆底元素下沉来更新堆, 而是递归直接比较当前节点的两个儿子,选择较小者上浮。这个事情忘记是从哪里看来的了, 算法导论似乎还为它布置了一个练习题。

以前还做过一个交互式竞赛题,要用最坏情况下最少的比较次数,给一个数组排序, 这个东西思路和上边秤硬币是一样的,就不多说了。给 n 个元素排序所需的最小的最坏情况下比较次数, 还是一道颇有难度的算法难题,有兴趣的同学可以 google 一下。

我们都知道,有一些排序算法是线性的,这些算法凭什么能突破复杂度的下界呢? 最简单的线性排序算法就是计数排序了,计数排序速度快的关键就在于, 它巧妙的利用了数组下标,让每一次的计数操作的信息量达到了 lb(m) 的量级, 其中 m 是用于计数的数组大小。其他的线性排序算法,如基数排序, 也都利用了类似的方式来加快速度。所以说数组真是个好东西,下面还可以看到数组的妙用。

数据结构

我以前学数据结构的时候有过一个疑问:平衡树为什么要搞成二叉的, 不搞成 100 叉的,你看人家 B+ 树树高多小怎么不学着点。后面我大学同学跟我解释过一次, 这里我想用信息论来解释一下。

多叉树会增加修改操作的编程复杂度不必多说,儿子更多显然也不会让修改操作更快, 所以只要考虑查询操作即可。比如说查询第一个比 k 大的元素这个操作,答案的信息熵是 O(log(n)) 级别的,而你在每个结点想定位到下个儿子,再快也逃不过基于比较的二分吧。 好了,查询操作的下界是 O(log(n))。当然,在查询的时候多叉树还是会快一丁点的, 在数组上二分肯定比在平衡树上二分快一些。在查询操作特别多的情况下或许值得做一个 trade off。

既然多叉树快不了多少,为啥 B+ 树要设计成多叉的?实际上,B 树和 B+ 树都是为了减少硬盘 IO 设计的。 硬盘 IO 一个重要的特点是一次取一页,管你取多取少都至少取一页的数据给你,另外一个特点是非常慢, 慢到研究硬盘数据结构的时候可以假设数据在内存的操作是光速的。 知道这两件事情就知道 B 树/B+ 树设计成多叉的意义了:为了尽量利用一页的空间,让一次硬盘 IO 能得到更多信息。这也能解释为什么 B 树/B+ 树的结点基本上都设计成刚好装满一页的大小,而不是两页或着半页。

Clojure 中的 vector 也是用函数式多叉树实现的,跟平衡树不同的是,vector 中元素的 key 是数组的下标, 于是在每个结点可以用位运算 O(1) 的定位它的儿子,因此 vector 的查询复杂度是 O(log_32(n)) 的。 考虑到儿子越多修改的时候就越慢,Clojure 在设计的时候跑了几个程序做了个 trade off 决定给每个结点 32 个儿子, 于是在大多数情况下,我们都可以将 Clojure 中的 vector 当成常数较大的数组来用了。 这个事情再次告诉我们:数组是个好东西。

压缩

以前好像有个公司宣称发明了一种能压缩任何文件的算法,然后被各种喷。实际上除了有损压缩外, 各种压缩算法都没法减少被压缩文件的信息熵,顶多只能在被压缩文件的一些特殊性质上作文章, 增加每一个比特位的信息量而已。

举个例子,我们知道字符集中每个字符的出现频率,怎样用 01 对这个字符集编码,让编码期望长度尽量短? 考虑最长的两个编码,这两个编码肯定是前面都一样,靠最后一位来区分。要让最后一位信息量尽量大, 就要让这两个编码对应的字符出现率尽量接近。另外因为是最长的编码,所以对应的字符要尽量少出现, 贪心的想法就是取出现最少的两个字符对应到这两个编码上面去,然后把这两个字符当成一个新字符继续处理。 看起来是不是很像哈夫曼编码。要注意的是,每位信息量尽量大并不一定等价于编码的期望长度尽量短, 以上的说法只能说 just for fun。如果哪位大佬证明了上面两个东西是等价的也欢迎打脸。。。。 基于信息论的编码方式也是有的,不过好像打不赢哈夫曼编码,大家有兴趣的话自己搜吧。

另外,以信息论的观点看,ASC II编码效率很低,大半字符基本上用不到。不过这东西好处是方便, 对性能要求不高还是可以用。对性能要求高的话就要考虑直接传二进制数据甚至设计特殊的编码方式了。 据我所知有些游戏就是这么弄的。

总结

其实上面的问题,不用信息论的知识也能解决,信息论之于这些解法,犹如解方程组之于解鸡兔同笼, 这是完整的理论的好处。信息论的缺点是实际问题中信息熵的准确值基本上算不出来,上面的很多分析大部分都是定性的, 基本上没用到信息熵的公式。对我个人而言,看了一点信息论的东西,最大的益处还是建立了一个信息熵的概念。 可以说,信息熵是随机事件的固有属性,利用信息熵分析一些问题可以化繁为简,省去不少力气。