我受够了每篇论文不同的世界观与叙述方式。下文的所有公式与算法流程都将以Python代码的形式给出。人会犯错，语言有歧义，公式有隐藏条件，论证有先决假设，但计算机是最冷静的，输入永远对应着输出。一段程序，虽然人类可能没办法很容易判断正确性，但其含义是无可争议的。
霍夫曼编码是最优的熵编码，那什么是熵？
信息论中，熵（Entropy）描述的是一个元素消除不确定性的能力。假设，抛硬币若干次，落下时正面朝上记为1，反之记为0。如果这枚硬币正反面等重，输出的数据将会大约是1和0等分。如果正面更重，则输出的1会多于0。前一份数据的熵将会高于后一份。再打个比方，LPL打进S世界赛的总决赛的信息量将会远大于LCK夺冠。因为，LCK夺冠已经是司空见惯的事情了，LPL进总决赛是罕见的。人们常说，某人说了一句废话，就是说的话的熵太低了。
那么如何从数学上给出熵的定义呢？先思考一个问题。
Root________
/ \
0___ 1A___
/ \ / \
0 1 0 1B
/ \ / \ / \ / \
0 1 0 1 0 1 0 1C
从上图中的Root出发，引导一个盲人到达目标C，最少需要多少信息？很显然，在三次上下文无关的01等可能选择中，都要选1。一个二进制Bit，可以表达0或者1。因此，最少要3个Bit，才能引导盲人到达C，不妨计作111。任何描述这一过程的信息的大小下界就是3Bits。注意！熵并不等于信息大小。熵的单位是Bits/Symbol。111用了3个符号，所以111的熵是3Bits/3=1Bits/Symbol。日常生活中，说一个新闻信息量大，往往既可以指信息长度长，又可以指信息密度高。熵描述的是后者。
上面所说的是等可能的情况，那么其它情况呢？考虑一种极端情况。
root
|
1A
|
1B
|
1C
一条大路直通终点。那么，请问这时候描述盲人从Root到C的过程需要多少Bits的信息？0。因为，无论我们给信息或者不给，盲人只有一条路可走。从高数的角度形象的错误理解，这时候的熵将会是无穷大。
从这两种情况以及其它一些要求，香农很自然地推导出了信息与熵的公式。
info_per_symbol = lambda p: log2(1/p)
entropy = sum(p * info_per_symbol(p) for p in possibilities)
熵是所有压缩算法的极限。选择等可能的情况下，我们做不了任何压缩，n次选择就要n Bits。没有选择的情况下，我们几乎可以“无限压缩”，根本不用记录任何数据。
再来看，如果选择0有66%的可能性，选择1有33%的可能性，会发生什么？
root_____________________
/ \
0 66%_______ 1 33%______
/ \ / \
0 44% 1 22% 0 22% 1 11%
/ \ / \ / \ / \
0 29% 1 15% 0 14% 1 7% 0 15% 1 7% 0 7% 1 4%
你可能会说，什么都没改变啊？我还是可以用111来描述这一事件。确实，111依然可以很好地完成目标，但却不能再反映全局了。等可能选择中的111与其它终点的可能性是一样的，所以拿111进行讨论，不失一般性。现在，111则是一个特例。
使用公式计算路径1的信息量为log2(1/0.33)=1.6Bits，路径0的为log2(1/0.66)=0.6Bits。怎么理解呢？我们都知道无限猴子定理，所谓信息就是从所有可能的取值空间里，筛出出特定的点或区域。刚刚的计算结果表明，33%概率的路径1的表达信息的能力是50%概率的路径1的1.6倍。注意看下图：
Root_____________________________________________________
/ \ \
0________________ 0________________ 1________________
/ \ \ / \ \ / \ \
0___ 0___ 1___ 0___ 0___ 1___ 0___ 0___ 1___
/ \ \ / \ \ / \ \ / \ \ / \ \ / \ \ / \ \ / \ \ / \ \
0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1
我将不等概率的2选1问题转化为了等概率的3选1问题。假设，我们有一个三进制的系统，用{A,B,C}表示，A<B<C。路径0映射为A和B，路径1映射为C。那么我连续选择三次1，是不是可以记作CCC？熵是1单位的三进制Bits/Symbol。现在问题就剩下一个了。如何将三进制转化为二进制？log2(3)=1.6。如果不好理解，不妨换个角度，数学预期上，3次33%概率的选择可以得到一个路径1，p=1/27。50%概率的话，要几次才能得到同样的结果呢？log2(27)=4.8，单次的比例就是1:1.6了。
到此，我们应该明白信息的压缩是有极限的，并可以用熵来精确描述。一些理论往往一开始不能解释具体现象，而是先着眼于抽象概念。比如，我一开始引入的盲人走路问题，毫无实践意义嘛～香农是从电报编码开始推导出整个信息论的基础。科学最重要的是想象力，而非记忆力抑或做题之技巧。
霍夫曼编码是怎么压缩数据的？
不同出现频率的Symbol所包含的信息是不同的，换言之，最优化的编码应该是变长的。但大部分计算机领域所用的编码是定长的。比如，ASCII编码，每一个字符都要占用8Bits的空间，更通用的UTF-8编码，长度必须是8的整数倍。霍夫曼编码就是将高频次（低熵）的编码用较短的编码表示，低频次的用较长的编码表示。这个算法较为简单，我也写得累了，就不赘述了。
网友评论