谁能想到，一个不想参加考试的学生的“任性”后来影响了整个互联网。

70年前，在麻省理工学院的信息论课上，老师为了给学生“减压”，提出了一道选择题。

要么参加期末考试，要么写一篇论文来改进现有算法，选择你自己的。

老师的名字叫罗伯特范诺。 他没有告诉学生的是，这个“现有算法”就是他和信息论创始人香农共同创作的香农-法诺码。 为了改进算法，他本人投入了大量的时间进行研究。

（老师内心OS：没想到。）

虽然有点破损，但这招确实管用。 这群学生一听到“交论文”就不需要考试，拍拍脑袋就决定写论文，其中就包括大卫霍夫曼。

如果你不选择，你就不知道。 如果你选择，你会感到震惊。 初出茅庐的霍夫曼很快意识到老师挖的坑——这篇论文太他妈难了。

这篇文章花了几个月的时间，费了很大力气，但霍夫曼仍然一无所获。

但命运，有时候就是很奇怪。 就在霍夫曼终于放弃“逃考”，准备把论文笔记扔进垃圾桶的时候，他突然灵光一闪！ 答案出现了！

霍夫曼放弃了对现有编码的研究，转向新的探索，最终找到了一种基于有序频率二叉树编码的方法。

他提出的想法在效率上成功超越了他老师的方法论。 甚至在后来的发展中，以他的名字命名的编码方式——霍夫曼编码，直接改变了数据压缩范式。

至于当时的结论报告，已经被引用了近万次。

传统编码方式效率低下

1951年，在麻省理工学院任教的罗伯特法诺正在思考信息论的一个难题：

如何用二进制代码高效地表示数字、字母或其他符号？

当时最常见、最直接的方法是为每个字符分配一个唯一的二进制数。

例如，字母 A 可能表示为，! 表达为，每个八位数字对应一个字符。

这使得代码易于解析，但效率极低。

还有另一种优化方法，类似于摩尔斯电码。 常见的字母E只用一个点来表示，但不太常见的Q则需要更长更费力的“—————”。

这样，代码的长度就会有所不同，信息不容易理解； 而且传输时字符之间需要添加间隙，否则无法区分不同的字符组合。

法诺意识到也许可以结合这两种方法的优点——用不同长度的二进制代码来表示字符。 进一步，为了避免代码“重叠”，他还构建了一棵二叉树。

他详尽地测试了每种排列可能性以获得最大效率，并最终提出了一个有效的案例：

每条消息按照频率分为两个分支，两侧字母的频率尽可能基本相同。

这样，常用的字符就位于较短、密度较低的分支上。

1948年，信息论之父香农在他的信息论导论《通信的数学理论》中提出了这一方法； 不久之后，法诺将其作为技术报告独立发表。 因此，这套方法被称为-Fano编码。

但这种方法并不总是有效。 当字母的概率为{0.35,0.17,0.17,0.16,0.15}时，无法给出理想的代码。

Fano 认为必须存在更好的压缩策略。 于是乎，这么重要的任务就交给了他的学生们。

灵光一现，世纪论文

如果说，法诺教授的方法就是从上到下构建一棵字符树，并尽可能保持成对分支之间的对称性。

那么哈夫曼的方法就直接颠覆了这个过程——自下而上构建二叉树。

他认为，无论发生什么，在有效的代码中，两个最不常见的字符应该具有两个最长的代码。

因此，首先确定两个最不常见的字符，将它们组合在一起作为分支对，然后重复该过程，然后从剩余的字符和刚刚构建的字符对中找到最不常见的字符（对）。

举例来说，O出现四次，S、C、H、L、R、M各出现一次。

Fano的方法是首先将O和另一个字母分配给左边的分支，这样两边总共有5次使用，得到的代码总共有27位。

相比之下，例如，霍夫曼的方法从不常见的 r 和 m 开始，并将它们组合成字母对。

组合后，可用的字符（对）包括：O（4次）、RM（2次）以及单个字母S、C、H和L。

除以频数，重复之前的操作——将两个不常见的选项分组，然后更新数树和频数图。

最终，“”变成0101，这比 Fano 自上而下的方法少了 1 位。

虽然 1 位在这里并不算多，但当扩展到数十亿字节时，它可以节省相当大的空间。

事实上，根据 的数据，霍夫曼的方法已被证明非常强大，以至于该论文当年被引用了 9,570 次。

至于他老师的方法，几乎​​没有再用过。

直到今天，几乎所有的无损压缩方法都全部或部分使用了霍夫曼的方法，它可以压缩图像、音频、表格等。它支持从PNG图像标准到无处不在的软件PKZip。

现代计算机科学先驱、图灵奖获得者高德纳曾这样形容霍夫曼的成就：

在计算机科学和数据通信中，霍夫曼编码是人们一直使用的基本思想。

后来，霍夫曼回忆起“突然亮光”的那一刻。 当时他正要把纸条扔进垃圾桶，突然思绪一汇聚，脑海中浮现出答案：

这是我一生中最奇怪的时刻。

我突然恍然大悟，就像闪电一样。

并表示，如果他知道他的教授法诺一直在努力解决这个问题，他可能永远不会尝试解决它，更不用说在 25 岁时尝百思特网试了。

成就感与秩序感，用数学玩艺术

霍夫曼编码改变了数据压缩范式，并为其赢得了无数荣誉和奖牌。

例如，1998年，霍夫曼获得了IEEE信息理论学会颁发的技术创新金禧奖，1999年获得了电气和电子工程师协会（IEEE）颁发的理查德汉明奖章（Medal）。

但即便如此，在他的一生中，相比无损压缩方法的发明，他最得意的还是这篇博士论文。

标题: 的.

霍夫曼在麻省理工学院攻读博士学位期间发表了这篇讨论顺序开关电路的重要论文。 当时，霍夫曼几百思特网乎是第一个解释如何设计异步顺序开关电路的学者，这一理论后来为计算机的发展提供了重要的逻辑支持。

这篇论文的发表不仅帮助他获得了富兰克林研究所的Louis E. Levy Medal，也让他获得了留校教授开关电路课程的资格。

在学校期间，霍夫曼还提出了一个创新的数学公式，可以将一个二进制数序列转换为另一个二进制数序列，而不会丢失任何信息。 这项研究在当时的密码学领域发挥了重要作用，也为他赢得了重要地位。

时任贝尔实验室研究副总裁的 O. Baker 招募他加入一个审查委员会，负责审查国家安全局未来的技术百思特网项目。 贝克博士曾担任艾森豪威尔、肯尼迪、约翰逊、尼克松和里根五位总统的科学顾问。

1967年，霍夫曼已经是一名正教授，他选择离开麻省理工学院，加入加州大学圣克鲁斯分校（UCSC）。 在此期间，他主导建立了计算机系并参与了学术课程的开发，为计算机系的发展奠定了重要基础。

数学可以说是霍夫曼一生的追求之一，以至于他从事艺术时都离不开数学。

自 20 世纪 70 年代以来，霍夫曼对折纸产生了兴趣。 他同时学习数学和折纸艺术。 他创作了数百幅折纸作品，并发表了分析折纸数学特性的论文。 他成为折纸数学领域的先驱。

回想起来，霍夫曼一生赢得了无数荣誉和嘉奖，但从未为他的任何发明申请过专利。

最后借用霍夫曼本人的一段话。

作为一名科学家和一名教师，我真的很依恋。 如果我觉得我还没有找到解决问题的最简单的解决方案，我会非常不满意，并且这种不满会持续下去，直到我找到最好的解决方案。 对我来说，这就是成为一名科学家的本质。

参考链接：