美国留学

敖飞寺杨靖山恩

量子比特|公众号QbitAI

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

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

要么参加期末考试，要么写一篇论文来改进现有算法，您可以选择。

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

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

虽然伤害有点大，但这招确实管用。包括大卫·霍夫曼在内的这群学生一听到“交论文”就决定不考试写论文。

如果你不选择，你就不会知道。如果你选择，你会感到震惊。刚入门的霍夫曼很快意识到老师在卷子上挖了一个洞：——，这个洞太难解了。

这篇写作花了几个月的时间，尽管付出了艰辛的努力，霍夫曼仍然一无所获。

但命运有时就是很奇怪。正当霍夫曼终于放弃“逃考”，准备把纸条扔进垃圾桶时，他突然灵机一动！答案出现了！

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

他提出的想法比他老师的方法更有效。甚至在后来的发展中，以他命名的编码方法——霍夫曼编码直接改变了数据压缩范式。

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

传统编码方法效率低下1951年，在麻省理工学院任教的罗伯特·范诺（Robert Fanno）正在思考信息论中的一个难题：

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

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

例如，字母A可以表示为01000001，表示为00100001，每个八位数字对应一个字符。

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

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

这种方式会导致代码长度不同，使信息难以理解；传输时字符之间需要添加间隙，否则无法区分不同的字符组合。

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

他详尽地测试了每种排列以获得最大效率的可能性，最终得出了一种可行的情况：

每条消息按照频率分为两个分支，两边字母的使用频率尽可能基本一致。

这样，常用的字符将出现在较短、较不密集的分支上。

1948年，信息论之父香农在介绍信息论的文章《通信的数学理论》中提出了这一方法；不久之后，范诺也以技术报告的形式独立发表。因此，这种方法称为Shannon-Fano编码。

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

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

范诺教授灵光一闪，在一篇世纪论文中表示，他们的方法是从上到下构建一棵字符树，并在成对的分支之间保持尽可能多的对称性。

所以哈夫曼的方法直接颠覆了这个过程，自下而上构建二叉树。

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

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

以教室为例，O 出现四次，S、C、H、L、R、M 各出现一次。

Fanno的方法是先将O和另一个字母赋给左边的分支，这样两边总共使用了5次，生成的代码总共27位。

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

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

根据出现频率进行划分，重复前面的操作——，将两个不常见的选项分组，然后更新数树和频数图。

最终，“schoolroom”变为11101111110000110110000101，这比Fano 自上而下的方法少了1 位数字。

虽然1 位在这里并不算多，但当扩展到数十亿字节时，这是一个相当大的节省。

事实上，霍夫曼的方法已经被证明是非常强大的。据谷歌学术统计，该论文当年被引用了9570次。

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

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

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

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

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

这是我一生中最奇怪的时刻。我突然意识到这一点，就像闪电一样。

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

带着成就感和秩序感，用数学玩艺术的哈夫曼编码改变了数据压缩范式，为他赢得了许多荣誉和奖牌。

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

但即便如此，在他的一生中，与无损压缩方法的发明相比，他最引以为傲的还是这篇博士论文。标题：顺序开关电路的综合。

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

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

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

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

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

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

从20 世纪70 年代开始，霍夫曼对折纸产生了浓厚的兴趣。他同时学习数学和折纸艺术，创作了数百幅弯曲的折纸作品。他还发表了一篇分析弯曲折纸数学特性的论文，成为折纸数学领域的先驱。

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

最后，让我借用霍夫曼本人的一句话。

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

参考链接：[1]https://www.quantamagazine.org/how-lossless-data-compression-works-20230531[2]https://www.huffmancoding.com/my-uncle/scientific-american[3]https://www.nytimes.com/1999/10/13/us/d-a-huffman-computer-expert-dies-at-74.html

- 超过-

量子比特QbitAI·今日头条订阅关注我们，第一时间了解前沿技术动态