谁曾想，一次学生不想参加考试的“固执”，后来竟影响了整个互联网。

70年前MIT的一堂信息论课上，一位教师为了给学生“减压”，摆出一道挑选题。

要么参加期末考试，要么写篇论文改善现有算法，自己挑。

这位教师名叫罗伯特·范诺，他没告知学生们的是，这个“现有算法”，正是他和信息论创始人香农合著的香农-范诺编码。而为了改善算法缺乏，他自己现已投入很多时间进行研讨。

尽管有点损，但这招还真管用。这票学生一听“交篇论文”就不必考试，拍脑袋就决议写论文，包含大卫•哈夫曼。

不选不知道，一选吓一跳。初出茅庐的哈夫曼很快认识到了教师挖的坑——这论文也太难搞了。

这一写，便是好几个月，并且苦苦挣扎中，哈夫曼依然一无所得。

但命运，有时分便是十分美妙。就在哈夫曼总算抛弃“逃考”，预备将论文笔记扔到垃圾桶中时，忽然灵光一现！答案呈现了！

哈夫曼抛弃对已有编码的研讨，转向新的探究，终究发现了根据有序频率二叉树编码的办法。

他提出的这一主意，功率成功逾越他教师的办法论。甚至在之后的开展中，以他命名的编码办法——哈夫曼编码，直接改变了数据紧缩范式。

至于其时那篇结题陈述，已引证近万次。

低效的传统编码办法

1951年，正在MIT任教的罗伯特·范诺正在考虑一道信息论的难题：怎么用二进制代码高效表明数字、字母或许其他符号？

其时最常见、也是最直接的办法，便是为每个字符分配一个*的二进制数。

比方，字母A或许表明为01000001，！表明为 00100001，每个八位数的数字都对应一个字符。

这样一来代码简略解析，但功率极低。

别的还有种优化办法，类似于摩尔斯电码。常用字母E仅由一个点表明，但不常见的Q需求更长且更吃力的“—— —— · ——”。

这种办法，会导致代码长度纷歧， 信息不简略被了解；并且传输中还需求在字符间参加空隙，不然就无法区别不同的字符组合。

范诺认识到，或许这两种办法的优势能够吞并之——以不同长度的二进制代码表明字符。进一步地，为防止代码“堆叠”，他还构建了二叉树。

他翔实地测试了每一种摆放的或许性以取得*功率，终究得到了一种有用状况：每条音讯依照频率分为两个分支，并尽或许让两头字母运用频率根本相同。

这样，常用的字符就会在更短、密度更低的分支上。

1948年，信息论之父香农在介绍信息理论的文章“通讯数学理论”中提出了这一办法；不久之后，范诺也独登时以技能陈述方式将其发布。故而这套办法被称作是香农-范诺编码。

但这个办法并非总是有用。像字母呈现概率分别为{0.35，0.17，0.17，0.16，0.15}这种状况时，就不能给出抱负编码。

范诺以为必定存在更好紧缩战略。于是乎，这样的重担就交到了他的学生手里。

一次灵光乍现，一篇世纪论文

假如说，范诺教授他们的办法是从上到下构建字符树，并在成对的树枝之间尽或许坚持对称。

那么哈夫曼的办法，是直接推翻了这一进程——自下而上构建二叉树。

他以为，不管发生什么状况，在一段有用的代码中，两个最不常见的字符应该有两个最长的代码。

因而首先就确认两个最不常见的字符，将它们组合在一起作为一个分支对，然后再重复该进程，再从剩下字符中与刚刚构建的字符对中寻觅最不常见的字符（对）。

以schoolroom为例，其间O呈现了四次，S、C、H、L、R、M各呈现一次。

范诺的办法，便是首先将O与另一个字母分配给左边分支，这样一来两头都是5次总运用量，生成的编码一共27位。

比较之下，哈夫曼的办法，比方就从不常见的r和m开端，将其组合成一个字母对。

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

依照呈现频率区分，重复上一操作——将两个不常见的选项分组，然后更新数树和频率图。

终究，“schoolroom”变成了 11101111110000110110000101，比Fano 自上而下的办法少了1位。

尽管1位在这儿并不多，但要是当扩展到数十亿字节时分，这便是一次不小的节约。

事实上，哈夫曼的办法现已被证明十分强壮，据谷歌学术计算，当年论文现已被引证9570次。

至于他教师的办法，却简直没有再被运用过。

直至今日，简直全部无损紧缩办法都悉数或部分运用了哈夫曼的办法，能够紧缩图画、音频、表格等。它支撑从PNG图画规范到无处不在的软件PKZip 的全部。

现代计算机科学前驱、图灵奖得主高德纳曾这样描述哈夫曼的成果：

在计算机科学和数据通讯范畴，哈夫曼编码是人们一向在运用的根本思维。

后来哈夫曼再回忆起那个「灵光乍现」时间，其时他正预备将论文笔记扔进垃圾桶，成果忽然思维会聚，答案在脑海里呈现了：

那是我生命中最独特的时间。

忽然茅塞顿开，犹如闪电一般。

并表明，假如他知道自己的教授范诺(Fano)曾与这个问题作过奋斗，他或许永久都不会测验处理这个问题，更不必说在25岁的时分就斗胆去测验。

成果与次序感，用数学玩艺术

哈夫曼编码改变了数据紧缩范式，也为其赢得了很多荣誉与奖章。

比方，1998年哈夫曼取得 IEEE 信息理论学会颁布的技能创新金禧奖、1999年取得电气和电子工程师协会 (IEEE) 颁布的理查德·汉明奖章（Richard Hamming Medal）。

不过即便如此，在他终身进程中，比较创造无损紧缩办法这件事儿，最让他引以为傲的反而是这篇博士论文。

标题：The Synthesis of Sequential Switching Circuits。

哈夫曼在MIT读博期间，发布这篇评论时序开关电路的重要论文。在其时，哈夫曼简直是*论述怎么规划异步次序开关电路的学者，而这一理论后来也为计算机开展供给了重要逻辑支撑。

这篇论文的发布，不只协助他取得富兰克林研讨所的Louis E. Levy Medal，也水到渠成让他取得留校任职资历，教授关于开关电路的课程。

在校期间，哈夫曼还提出一种改造的数学公式，能够在不丢掉任何信息的状况下将一个二进制数序列转换成另一个二进制数序列，这项研讨在其时密码学中发挥了重要作用，也为其谋得了一份重要职位。

时任贝尔实验室研讨副总裁的William O. Baker将其招纳入了一个检查委员会，首要担任为国家安全局检查未来科技方案。Baker博士曾担任过艾森豪威尔、肯尼迪、约翰逊、尼克松和里根五位总统的科学参谋。

1967年已是正教授的霍夫曼挑选脱离MIT，参加加利福尼亚大学圣克鲁兹分校(UCSC)，期间主导创立了计算机科学系，并参加学术课程开发作业，为之后计算机科学系开展奠定重要根底。

数学能够说是哈夫曼终身寻求之一，以至于后来在搞艺术时，也离不开数学。

70年代开端，哈夫曼对折纸发生浓厚兴趣，一起研讨数学和折纸艺术，制作了上百件曲痕折纸著作，还专门宣布论文剖析曲痕折纸的数学性质，成为折纸数学范畴的前驱人物。

回过头看，哈夫曼的终身赢得过很多荣誉与赞誉，却从未为自己任何一项创造申请过专利。

最终，借用哈夫曼自己的一段话。

作为一名科学家和教师，我真的十分执着。假如我觉得自己还没有找到问题的最简略处理办法，我会十分不满意，这种不满会一向继续，直到我找到*办法停止。对我来说，这便是科学家的实质。

参阅链接：[1]