关于哈夫曼编码

哈夫曼编码是我在得到app中吴军老师的《信息论40讲》中了解到的，虽然是一个关于信息论的编码方法， 但是对于我们的生活和工作也是很有帮助的，所以记了下来。

关于哈夫曼编码，是从摩尔斯电码说起的，这种电码是用点（嘀）和长线（嗒）对英文的26个字母进行编码的，按照对信息度量的方法，如果对26个字母采用等长度析编码，比如进行进制编码就需要log26（这里的log函数是以2为底的），也就是约5比特信息，而采用摩尔斯电码的方法，平均只需要3比特，这样效率就高了很多，发报时间也节省了大约1/3左右。

在战争时期，能够节省发电报的时间对情报人员的安全是很重要的，因为谍战片里情报人员没法完电报就被别人闯进来带走的情形在现实中是真的很常见的，尤其是在二战时期欧洲的德占区。另外就算是除去战争的因素，能够节省1/3的发报成本也是一个很大的改进。

但是，如果按照哈夫曼编码的方法来看摩尔斯电码，就会发现虽然摩尔斯电码不自觉的采用了哈夫曼编码的方法，但还不是最简洁的编码方法，依然有改进的空间。

事实证明，越长出现的信息采用较短的编码，不常出现的信息采用较长的编码相比于所有信息都采用相同长度编码的方法更合算的。我们可以按照这样一个推倒步骤来看一下：

详细的推导步骤：

我们不妨看一个具体的例子。我们假定有32条信息，每条信息出现的概率分别为1/2、1/4、1/8、1/16……依次递减，最后31、32两个信息出现的概率是1/2^31、1/2^31（这样32个信息的出现概率加起来就是1了）。现在需要用二进制数对它们进行编码。等长度和不等长度两种编码方法，我们来对比一下：

方法一：采用等长度编码，码长为5。因为是log32=5比特。

方法二：不等长度编码，如果出现概率高就短一些，概率低就长一些。

我们把第一条信息用0编码，第二条用10编码，第三条用110编码……最后31、32两条出现概率相同，都很低，码长都是31。第31条信息就用1111……110（30个1加1个0）编码，第32条信息，就用1111……111（31个1）来编码。

这样的编码虽然大部分码的长度都超过了5，但是乘以出现概率后，平均码长只有2，也就是说节省了60%的码长。如果利用这个原理进行数据压缩，可以在不损失任何信息的情况下压缩掉60%。

（对于我个人来讲，虽然数学学得不怎么样，但是这种推导过程我还是很喜欢的，因为通过自己动手来将一个结论推导出来时间很开心的事。)

哈夫曼编码从本质上讲就是讲最宝贵的资源（最短的编码）给出现概率最大的信息。而至于如何分配，其中的一个原则就是一条信息编码的长度和出现概率的对数成正比。按我的理解就是出现的概率越大，投入的资源就越多。

那么哈夫曼编码的原则对于我们有什么用处呢？可以这样讲，只要是需要分配资源的工作，它都有指导意义。

课程中给我印象最深就是美国私立学校哈克学校的前校长尼科诺夫博士的一句话：在孩子小时候，要让他们尝试各种兴趣爱好，但是最终他们要在一个点上实现突破，就好比用圆规画圆，一方面有一个扎得很深的中心，另一方面有足够广的很浅的覆盖面。我觉得这是我能够听明白并且能够实践应用的最简单直接的方法。而且吴军老师就是用哈夫曼编码的方法来指导行动的，不排斥尝试新东西，但也对那些看样子不太能做成的事坚决停止投入，然后将更多的精力投入到成功率最高的事情上。

吴军老师有句话很好，“理论不在学得多，而在于学以致用”。而我们大多数人都是学得多，用得少，我也是一样。也许我可以从学着用哈夫曼编码开始，试着将学到的理论指导实践，踏踏实实的往前走。