灵光一现的创造——霍夫曼编码
霍夫曼
声影传奇
#004#
作为一名科学家和老师，我真的非常执着。如果我觉得自己还没有找到问题的最简单解决方法，我会非常不满意，这种不满会一直持续，直到我找到最佳方法为止。对我来说，这就是科学家的本质。——David Albert Huffman
“那是我生命中最奇特的时刻”
1951年，麻省理工大学的Robert M. Fano教授留给学生一道选择题：学生们可以选择通宵达旦地复习功课，参加期末考试；或者交出一份学期论文，逃过考试一劫。在学期论文中，Fano教授布置了一个看似很简单的问题：找到使用二进制代码表示数字、字母或者其他符号的最佳编码方法。学生们不知道的是，这其实是Fano教授自己正在研究的课题。
Robert M. Fano（图片来自ETHW）
注：在这里要介绍一下Robert M. Fano教授，Fano教授出生于意大利的一个犹太家庭，父亲是意大利数学家、有限几何创始人Gino Fano；兄长Ugo Fano是一位物理学家，对理论物理做出过诸多贡献；堂兄Giulio Racah也是一位优秀的物理学家和数学家。Fano教授本人更是以信息论方面的工作闻名，他与香农一起合作开发了香农-法诺编码（ Shannon–Fano coding），并推导出法诺不等式（ Fano inequality）。他还发明了Fano 算法（Fano algorithm）并假设了Fano 度量（Fano metrics）。
一个名叫David Albert Huffman的年轻人因为不想参加期末考试，而选择了攻坚论文。他为了完成这篇论文，花费了数月时间，研究了多种方法，但没有一种方法可以证明是最有效的。他对发现解决方案感到绝望，开始灰心丧气，并打算放弃这篇论文，转而准备期末考试。
一天，正当他准备将论文笔记扔到垃圾桶中时，突然灵光一现！答案出现了！他想到了最佳编码方法！“那是我生命中最奇特的时刻，”Huffman回顾这个时刻时说。“突然恍然大悟，犹如闪电一般 。”
这种方法实现了平均码长最短的编码，比Fano教授的方法还要好。
1952年，这位年轻人发表了他的学期论文A Method for the Construction of Minimum-Redundancy Codes。
这篇论文所描述的编码方法改变了数据压缩的进程，进而改变了现代人类的生活，传真机、调制解调器、高清电视等到处都有它的身影，这种编码方法由创造它的年轻人的名字命名，被称为霍夫曼编码（Huffman Coding）。
David A. Huffman
霍夫曼说，如果他一早知道自己的导师Fano和信息论之父香农都曾在最佳编码问题上“挣扎”过，他绝无可能在25岁的年纪就解决这个问题，或者去尝试解决这个问题。“我很幸运能在正确的时间出现在那里，而且我的教授没有告诉过我其他优秀的人也曾苦困恼于这个问题，从而使我感到气馁。”
什么是霍夫曼编码？
著名计算机科学家、《计算机程序设计艺术》的作者高德纳曾经说过：“在计算机科学和数据通信领域，霍夫曼编码是人们一直在使用的基本思想。”
霍夫曼编码是一种经典的数据压缩方法，可以压缩图像、音频、表格等。这种压缩方案主要用于JPEG和MPEG-2。
让我们来看下方的字符串：
A DEAD DAD CEDED A BAD BABE A BEADED ABACA BED这里一共有46个字符，每个字符占8个比特，所以一共有46*8=368个比特。如果我们使用霍夫曼编码的话，可以将这368个比特压缩到更小的尺寸。
在上面的字符串中，如果我们使用等长编码（Equal Length Code），将每个字符设计成长度为3的二进制编码，将会得到46*3=138个比特（长度为138）。但等长编码有一个弊端，即所有字符的长度相同导致编码结果太长，占用了太多计算机空间和网络带宽。
所以变长编码（Variable Length Code）应运而生，但同时也带来一个问题：二进制编码中，只有0和1，如果每个字符的位数不固定，则很难确定从哪里开始，以及到哪里停止，这就很容易产生歧义。虽然可以使用分隔符，但是这样一来却增加了消息长度。
这时，霍夫曼编码出现了。霍夫曼编码所使用的基本策略是：出现频率高的字符使用较短的编码，出现频率低的字符则使用较长的编码。霍夫曼编码使用前缀码（Prefix code）解决了前述的歧义问题，前缀码，即表示某些特定符号的位串永远不是代表任何其他符号的位串的前缀。
注：前缀码（Prefix code）, 有时称为“无前缀码（Prefix-free code）”。
这种方式通过构建霍夫曼树（Huffman tree）来完成。
一开始所有节点都是叶子节点，包含一个字符和对应的权重——代表字符在整个字符串中出现的频率。出现频率最高的字符，距离树的根节点最近。两个最小权重的节点创建一个新节点，新节点的权重为其子节点的权重之和，然后我们再在这个新节点和剩余节点上应用此过程，直到剩下最后一个节点，而这就是霍夫曼树的根节点。
我们从根节点开始，然后沿着霍夫曼树像要编码的字符前进。如果走了左侧路径，则标记为 0，走了右侧路径，我们则标记为 1。这样就完成了整个霍夫曼树的构建。整个字符串编码后的结果如下图步骤8所示。
最终需要消耗115比特，比368比特整整少了253比特，比138比特少了23比特。
图片来自http://math.oxford.emory.edu/
作为对后世影响深远的编码方法的创造者，霍夫曼拥有怎样的一生呢？
早年动荡的生活
霍夫曼出生于美国俄亥俄州，他的童年并不幸福：一系列的家庭变故导致了父母的离婚，之后霍夫曼跟随母亲一起生活。据他母亲告诉他，他学会说话要比其他同龄孩子整整晚了两年，这使得大家都以为他是一个发育迟缓的孩子（霍夫曼曾将自己“迟钝”的童年归结于家庭的一系列变故和父母的离婚）。为了能让霍夫曼被学校录取，他的母亲成为了一家问题儿童学校的数学老师。但是经过一系列的测试，他的母亲和老师们惊奇地发现，霍夫曼在智力方面不仅没有任何问题，而且还超出同龄人很多。
原来是霍夫曼的沉默掩盖了他的早慧。
18岁时，霍夫曼获得了俄亥俄州立大学电气工程学士学位。随后加入美国海军，并成为一名雷达维修官，在一艘帮助清除日本和中国水域水雷的驱逐舰上服役。但这艘驱逐舰的船长经常让霍夫曼做很多额外的工作，这些工作与他接受过的雷达、声纳、对抗措施和其他工程训练完全无关，从而引起了霍夫曼的不满。
“一盒 35 毫米电影胶片从上层甲板掉下来，砸伤了我的头，这是我在战争中唯一一次受伤。”
两年后，霍夫曼退役，进入俄亥俄州立大学继续攻读电气工程硕士学位。但那段时间，霍夫曼常常感到非常迷茫，他看不清自己未来的方向，感觉像是被困住了一样，只能通过旅行和登山来排遣苦闷和压抑。
麻省理工学院（MIT）是霍夫曼的脱困之路。虽然对于申请MIT没有抱任何希望，但霍夫曼还是幸运地被录取了。MIT的电气工程学院的课程丰富且广泛，霍夫曼终于找到了归属，也对自己的职业目标有了清晰的认识。
当然，也是因为进入MIT学习，才有了后来闻名于世的霍夫曼编码。
霍夫曼曾说过，这种早年动荡不安的生活使他爱上了数学。“我喜欢整洁的东西，”他说，可能是因为我早年生活动荡的缘故，我很喜欢以一个明确的答案来总结发生的事情。正是这种明确的秩序感驱使着霍夫曼不断努力，最终获得了辉煌的成就。
霍夫曼的教学生涯
1953年，霍夫曼在麻省理工学院获得了电气工程理学博士学位。同年，他入职MIT，成为一名大学老师。
霍夫曼能够留校，主要得益于他的一篇博士论文，这也是他最引以为傲的论文（出乎意料，笔者以为会是霍夫曼编码那篇论文），题目是The Synthesis of Sequential Switching Circuits，而他在MIT所教授的课程，正是开关电路。
霍夫曼编码的成功使得霍夫曼备受瞩目，同时也吸引了时任贝尔实验室研究副总裁的William O. Baker的注意。Baker博士曾担任过艾森豪威尔、肯尼迪、约翰逊、尼克松和里根五位总统的科学顾问，他将霍夫曼招纳入了一个审查委员会，该委员会主要负责为国家安全局审查未来科技计划。
1967年，已经是正教授的霍夫曼离开了MIT，加入了加利福尼亚大学圣克鲁兹分校（UCSC，University of California，Santa Cruz）。在UCSC，霍夫曼帮助创立了计算机科学系并在1970~1973年期间担任系主任，他在开发该系学术课程以及教师人员招聘方面，发挥了重要作用。
1994年，霍夫曼退休。
退休后的霍夫曼并没有远离校园，作为一名荣誉退休教授，他依然活跃在课堂，教授信息论和信号分析等课程。
情迷折纸
图片来自https://www.huffmancoding.com/my-uncle/scientific-american
从上世纪70年代开始，霍夫曼对折纸（Paperfolding）产生了浓厚的兴趣。正如他所开发的无损压缩方法闻名于计算机科学领域一样，霍夫曼在折纸领域也成就非凡。
作为曲痕折纸（Curved-crease Paperfolding）的先驱人物，霍夫曼制作了几百件曲痕折纸作品，这些作品代表了1970~1990间该领域的大部分成就，他的工作启发了后世对曲痕折纸的进一步研究。
霍夫曼同时研究数学和折纸艺术，他的主要兴趣之一就是通过精确计算，使折叠出来的结构避免给纸张施加压力。通过数学计算，霍夫曼试图理解，当几个折痕同时出现在一点的时候，什么样的角度关系才不会使纸张拉伸或者撕裂。
他曾经在论文Curvature and creases: A primer on paper中分析了曲痕折纸的数学性质，并制作了雕塑来研究这种特殊的折叠方式。
为了普及折纸知识，霍夫曼曾在麻省理工学院和斯坦福等大学讲授过折纸的理论和实践课程并多次面向公众发表折纸艺术的演讲。在1979年一次面向科学家和艺术家的演讲中，他表示科学和艺术这两个群体中的人相互交流太少。
从70年代到90年代，霍夫曼创作了大量折纸，其中既有曲痕折纸，也有直痕折纸，这些折纸优雅、美丽，堪称艺术品。麻省理工学院博物馆收录了一系列霍夫曼的折纸模型。
下面是霍夫曼的一些作品展示。
以上图片来自http://erikdemaine.org/papers/Huffman_Origami5/paper.pdf
霍夫曼说：“我从来没有声称自己是艺术家，我甚至不确定该如何定义艺术。但我发现折纸背后的优雅数学定理很自然地使折纸呈现出一种优雅的视觉效果。”
除了折纸以外，霍夫曼还拥有很多其他爱好。
早年他从香农那里学会了骑独轮车。离开MIT加入加州大学圣克鲁兹分校以后，因为这里距离西部山区很近，所以霍夫曼经常徒步背包旅行和露营。65岁时，他又爱上了浮潜和人体冲浪。
成就非凡
霍夫曼的成就为他赢得了无数奖项和荣誉。1999年，他获得了电气和电子工程师协会 (IEEE) 颁发的理查德·汉明奖章（Richard Hamming Medal），以表彰他对信息科学的杰出贡献。他因其关于时序开关电路的博士论文获得了富兰克林研究所的 Louis E. Levy Medal，他还获得了俄亥俄州立大学的杰出校友奖和 W. Wallace McDowell Award。1981年， IEEE 计算机学会为他颁发了计算机先锋奖；1998年，霍夫曼获得了 IEEE 信息理论学会颁发的技术创新金禧奖。
1999年10月7日，经过与癌症长达10个月的斗争，霍夫曼离开了这个世界。
在霍夫曼的一生中，他从来没为自己的任何一项发明创造申请过专利，虽然与亿万富翁擦肩而过，但他似乎并没有多么失望，毕竟霍夫曼编码还帮他逃过期末考试一劫。
References:
https://www.huffmancoding.com/my-uncle/scientific-american
https://en.wikipedia.org/wiki/David_A._Huffman
https://en.wikipedia.org/wiki/Huffman_coding
https://www.techiedelight.com/huffman-coding/
http://math.oxford.emory.edu/site/cs171/huffmanCoding/
http://erikdemaine.org/papers/Huffman_Origami5/paper.pdf
最后感谢赵军老师推荐本期声影传奇人物——霍夫曼。