案例库 · 工程与运营 · 技术决策 · 1951–1952
哈夫曼用一篇学期论文解决了一个编码领域的开放问题
1951年，一位麻省理工学院的研究生自底向上构建了一棵按频率排序的树，并证明了它的最优性。
麻省理工学院
那一手
1951年，大卫·哈夫曼和他的信息论同学们面临着学期论文或期末考试的选择。他们的教授罗伯特·法诺布置的学期论文题目是：找出最有效的二进制编码。哈夫曼无法证明任何编码是最有效的，他几乎要放弃，打算去准备考试。
就在这时，他想到自底向上构建一棵按频率排序的二叉树，反复合并出现频率最低的两个符号，并很快证明了结果是最优的。从最低频率端开始构建能保证最优性，而法诺和克劳德·香农开发的从上到下的方法则不能。
这种编码是一种前缀码：由于每个符号的编码都不是另一个编码的前缀，解码器可以无歧义地重建消息，而且最频繁的符号获得最短的表示，因此平均消息长度趋向于信息论极限。
为什么管用
- 首先合并两个出现频率最低的符号，使最频繁的符号离根节点最近，从而获得最短的编码。
- 该编码是前缀码，因此解码器无需分隔符即可分割比特流。
- 自底向上的构建使最优性的证明变得容易，而自顶向下的香农-法诺编码则无法保证这一点。
值了多少自底向上构建树聪明
可以搬走什么
遇到难题时，不妨尝试逆转他人尝试的方向；从最不常见的端开始构建，可以让看似无法证明的最优性变得一目了然。
后来呢
哈夫曼编码成为应用最广泛的数据压缩方法之一，支撑着JPEG、MP3以及gzip和PNG中的Deflate算法。哈夫曼的学期论文成果超越了他的教授，该方法至今仍是无损压缩的标准构建模块。
资料来源
发现哪里写错了？告诉我们。