點(diǎn)擊上方“LiveVideoStack”關(guān)注我們

作者 | Alex

技術(shù)審校 | 趙軍

霍夫曼

聲影傳奇

#004#

作為一名科學(xué)家和老師，我真的非常執(zhí)著。如果我覺(jué)得自己還沒(méi)有找到問(wèn)題的最簡(jiǎn)單解決方法，我會(huì)非常不滿意，這種不滿會(huì)一直持續(xù)，直到我找到最佳方法為止。對(duì)我來(lái)說(shuō)，這就是科學(xué)家的本質(zhì)。——David Albert Huffman

“那是我生命中最奇特的時(shí)刻”

1951年，麻省理工大學(xué)的Robert M. Fano教授留給學(xué)生一道選擇題：學(xué)生們可以選擇通宵達(dá)旦地復(fù)習(xí)功課，參加期末考試；或者交出一份學(xué)期論文，逃過(guò)考試一劫。在學(xué)期論文中，Fano教授布置了一個(gè)看似很簡(jiǎn)單的問(wèn)題：找到使用二進(jìn)制代碼表示數(shù)字、字母或者其他符號(hào)的最佳編碼方法。學(xué)生們不知道的是，這其實(shí)是Fano教授自己正在研究的課題。

Robert M. Fano（圖片來(lái)自ETHW）

注：在這里要介紹一下Robert M. Fano教授，Fano教授出生于意大利的一個(gè)猶太家庭，父親是意大利數(shù)學(xué)家、有限幾何創(chuàng)始人Gino Fano；兄長(zhǎng)Ugo Fano是一位物理學(xué)家，對(duì)理論物理做出過(guò)諸多貢獻(xiàn)；堂兄Giulio Racah也是一位優(yōu)秀的物理學(xué)家和數(shù)學(xué)家。Fano教授本人更是以信息論方面的工作聞名，他與香農(nóng)一起合作開(kāi)發(fā)了香農(nóng)-法諾編碼（ Shannon–Fano coding），并推導(dǎo)出法諾不等式（ Fano inequality）。他還發(fā)明了Fano 算法（Fano algorithm）并假設(shè)了Fano 度量（Fano metrics）。

一個(gè)名叫David Albert Huffman的年輕人因?yàn)椴幌雲(yún)⒓悠谀┛荚?#xff0c;而選擇了攻堅(jiān)論文。他為了完成這篇論文，花費(fèi)了數(shù)月時(shí)間，研究了多種方法，但沒(méi)有一種方法可以證明是最有效的。他對(duì)發(fā)現(xiàn)解決方案感到絕望，開(kāi)始灰心喪氣，并打算放棄這篇論文，轉(zhuǎn)而準(zhǔn)備期末考試。

一天，正當(dāng)他準(zhǔn)備將論文筆記扔到垃圾桶中時(shí)，突然靈光一現(xiàn)！答案出現(xiàn)了！他想到了最佳編碼方法！“那是我生命中最奇特的時(shí)刻，”Huffman回顧這個(gè)時(shí)刻時(shí)說(shuō)。“突然恍然大悟，猶如閃電一般 ?。”

這種方法實(shí)現(xiàn)了平均碼長(zhǎng)最短的編碼，比Fano教授的方法還要好。

1952年，這位年輕人發(fā)表了他的學(xué)期論文A Method for the Construction of Minimum-Redundancy Codes。

這篇論文所描述的編碼方法改變了數(shù)據(jù)壓縮的進(jìn)程，進(jìn)而改變了現(xiàn)代人類(lèi)的生活，傳真機(jī)、調(diào)制解調(diào)器、高清電視等到處都有它的身影，這種編碼方法由創(chuàng)造它的年輕人的名字命名，被稱(chēng)為霍夫曼編碼（Huffman Coding）。

David A. Huffman

霍夫曼說(shuō)，如果他一早知道自己的導(dǎo)師Fano和信息論之父香農(nóng)都曾在最佳編碼問(wèn)題上“掙扎”過(guò)，他絕無(wú)可能在25歲的年紀(jì)就解決這個(gè)問(wèn)題，或者去嘗試解決這個(gè)問(wèn)題。“我很幸運(yùn)能在正確的時(shí)間出現(xiàn)在那里，而且我的教授沒(méi)有告訴過(guò)我其他優(yōu)秀的人也曾苦困惱于這個(gè)問(wèn)題，從而使我感到氣餒。”

? ?什么是霍夫曼編碼？

著名計(jì)算機(jī)科學(xué)家、《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》的作者高德納曾經(jīng)說(shuō)過(guò)：“在計(jì)算機(jī)科學(xué)和數(shù)據(jù)通信領(lǐng)域，霍夫曼編碼是人們一直在使用的基本思想。”

霍夫曼編碼是一種經(jīng)典的數(shù)據(jù)壓縮方法，可以壓縮圖像、音頻、表格等。這種壓縮方案主要用于JPEG和MPEG-2。

讓我們來(lái)看下方的字符串：

A DEAD DAD CEDED A BAD BABE A BEADED ABACA BED

這里一共有46個(gè)字符，每個(gè)字符占8個(gè)比特，所以一共有46*8=368個(gè)比特。如果我們使用霍夫曼編碼的話，可以將這368個(gè)比特壓縮到更小的尺寸。

在上面的字符串中，如果我們使用等長(zhǎng)編碼（Equal Length Code），將每個(gè)字符設(shè)計(jì)成長(zhǎng)度為3的二進(jìn)制編碼，將會(huì)得到46*3=138個(gè)比特（長(zhǎng)度為138）。但等長(zhǎng)編碼有一個(gè)弊端，即所有字符的長(zhǎng)度相同導(dǎo)致編碼結(jié)果太長(zhǎng)，占用了太多計(jì)算機(jī)空間和網(wǎng)絡(luò)帶寬。

所以變長(zhǎng)編碼（Variable Length Code）應(yīng)運(yùn)而生，但同時(shí)也帶來(lái)一個(gè)問(wèn)題：二進(jìn)制編碼中，只有0和1，如果每個(gè)字符的位數(shù)不固定，則很難確定從哪里開(kāi)始，以及到哪里停止，這就很容易產(chǎn)生歧義。雖然可以使用分隔符，但是這樣一來(lái)卻增加了消息長(zhǎng)度。

這時(shí)，霍夫曼編碼出現(xiàn)了。霍夫曼編碼所使用的基本策略是：出現(xiàn)頻率高的字符使用較短的編碼，出現(xiàn)頻率低的字符則使用較長(zhǎng)的編碼。霍夫曼編碼使用前綴碼（Prefix code）解決了前述的歧義問(wèn)題，前綴碼，即表示某些特定符號(hào)的位串永遠(yuǎn)不是代表任何其他符號(hào)的位串的前綴。

注：前綴碼（Prefix code）, 有時(shí)稱(chēng)為“無(wú)前綴碼（Prefix-free code）”。

這種方式通過(guò)構(gòu)建霍夫曼樹(shù)（Huffman tree）來(lái)完成。

一開(kāi)始所有節(jié)點(diǎn)都是葉子節(jié)點(diǎn)，包含一個(gè)字符和對(duì)應(yīng)的權(quán)重——代表字符在整個(gè)字符串中出現(xiàn)的頻率。出現(xiàn)頻率最高的字符，距離樹(shù)的根節(jié)點(diǎn)最近。兩個(gè)最小權(quán)重的節(jié)點(diǎn)創(chuàng)建一個(gè)新節(jié)點(diǎn)，新節(jié)點(diǎn)的權(quán)重為其子節(jié)點(diǎn)的權(quán)重之和，然后我們?cè)僭谶@個(gè)新節(jié)點(diǎn)和剩余節(jié)點(diǎn)上應(yīng)用此過(guò)程，直到剩下最后一個(gè)節(jié)點(diǎn)，而這就是霍夫曼樹(shù)的根節(jié)點(diǎn)。

我們從根節(jié)點(diǎn)開(kāi)始，然后沿著霍夫曼樹(shù)像要編碼的字符前進(jìn)。如果走了左側(cè)路徑，則標(biāo)記為 0，走了右側(cè)路徑，我們則標(biāo)記為 1。這樣就完成了整個(gè)霍夫曼樹(shù)的構(gòu)建。整個(gè)字符串編碼后的結(jié)果如下圖步驟8所示。

最終需要消耗115比特，比368比特整整少了253比特，比138比特少了23比特。

圖片來(lái)自http://math.oxford.emory.edu/

作為對(duì)后世影響深遠(yuǎn)的編碼方法的創(chuàng)造者，霍夫曼擁有怎樣的一生呢？

早年動(dòng)蕩的生活

霍夫曼出生于美國(guó)俄亥俄州，他的童年并不幸福：一系列的家庭變故導(dǎo)致了父母的離婚，之后霍夫曼跟隨母親一起生活。據(jù)他母親告訴他，他學(xué)會(huì)說(shuō)話要比其他同齡孩子整整晚了兩年，這使得大家都以為他是一個(gè)發(fā)育遲緩的孩子（霍夫曼曾將自己“遲鈍”的童年歸結(jié)于家庭的一系列變故和父母的離婚）。為了能讓霍夫曼被學(xué)校錄取，他的母親成為了一家問(wèn)題兒童學(xué)校的數(shù)學(xué)老師。但是經(jīng)過(guò)一系列的測(cè)試，他的母親和老師們驚奇地發(fā)現(xiàn)，霍夫曼在智力方面不僅沒(méi)有任何問(wèn)題，而且還超出同齡人很多。

原來(lái)是霍夫曼的沉默掩蓋了他的早慧。

18歲時(shí)，霍夫曼獲得了俄亥俄州立大學(xué)電氣工程學(xué)士學(xué)位。隨后加入美國(guó)海軍，并成為一名雷達(dá)維修官，在一艘?guī)椭宄毡竞椭袊?guó)水域水雷的驅(qū)逐艦上服役。但這艘驅(qū)逐艦的船長(zhǎng)經(jīng)常讓霍夫曼做很多額外的工作，這些工作與他接受過(guò)的雷達(dá)、聲納、對(duì)抗措施和其他工程訓(xùn)練完全無(wú)關(guān)，從而引起了霍夫曼的不滿。

“一盒 35 毫米電影膠片從上層甲板掉下來(lái)，砸傷了我的頭，這是我在戰(zhàn)爭(zhēng)中唯一一次受傷。”

兩年后，霍夫曼退役，進(jìn)入俄亥俄州立大學(xué)繼續(xù)攻讀電氣工程碩士學(xué)位。但那段時(shí)間，霍夫曼常常感到非常迷茫，他看不清自己未來(lái)的方向，感覺(jué)像是被困住了一樣，只能通過(guò)旅行和登山來(lái)排遣苦悶和壓抑。

麻省理工學(xué)院（MIT）是霍夫曼的脫困之路。雖然對(duì)于申請(qǐng)MIT沒(méi)有抱任何希望，但霍夫曼還是幸運(yùn)地被錄取了。MIT的電氣工程學(xué)院的課程豐富且廣泛，霍夫曼終于找到了歸屬，也對(duì)自己的職業(yè)目標(biāo)有了清晰的認(rèn)識(shí)。

當(dāng)然，也是因?yàn)檫M(jìn)入MIT學(xué)習(xí)，才有了后來(lái)聞名于世的霍夫曼編碼。

霍夫曼曾說(shuō)過(guò)，這種早年動(dòng)蕩不安的生活使他愛(ài)上了數(shù)學(xué)。“我喜歡整潔的東西，”他說(shuō)，可能是因?yàn)槲以缒晟顒?dòng)蕩的緣故，我很喜歡以一個(gè)明確的答案來(lái)總結(jié)發(fā)生的事情。正是這種明確的秩序感驅(qū)使著霍夫曼不斷努力，最終獲得了輝煌的成就。

霍夫曼的教學(xué)生涯

1953年，霍夫曼在麻省理工學(xué)院獲得了電氣工程理學(xué)博士學(xué)位。同年，他入職MIT，成為一名大學(xué)老師。

霍夫曼能夠留校，主要得益于他的一篇博士論文，這也是他最引以為傲的論文（出乎意料，筆者以為會(huì)是霍夫曼編碼那篇論文），題目是The Synthesis of Sequential Switching Circuits，而他在MIT所教授的課程，正是開(kāi)關(guān)電路。

霍夫曼編碼的成功使得霍夫曼備受矚目，同時(shí)也吸引了時(shí)任貝爾實(shí)驗(yàn)室研究副總裁的William O. Baker的注意。Baker博士曾擔(dān)任過(guò)艾森豪威爾、肯尼迪、約翰遜、尼克松和里根五位總統(tǒng)的科學(xué)顧問(wèn)，他將霍夫曼招納入了一個(gè)審查委員會(huì)，該委員會(huì)主要負(fù)責(zé)為國(guó)家安全局審查未來(lái)科技計(jì)劃。

1967年，已經(jīng)是正教授的霍夫曼離開(kāi)了MIT，加入了加利福尼亞大學(xué)圣克魯茲分校（UCSC，University of California，Santa Cruz）。在UCSC，霍夫曼幫助創(chuàng)立了計(jì)算機(jī)科學(xué)系并在1970~1973年期間擔(dān)任系主任，他在開(kāi)發(fā)該系學(xué)術(shù)課程以及教師人員招聘方面，發(fā)揮了重要作用。

1994年，霍夫曼退休。

退休后的霍夫曼并沒(méi)有遠(yuǎn)離校園，作為一名榮譽(yù)退休教授，他依然活躍在課堂，教授信息論和信號(hào)分析等課程。

?情迷折紙

圖片來(lái)自https://www.huffmancoding.com/my-uncle/scientific-american

從上世紀(jì)70年代開(kāi)始，霍夫曼對(duì)折紙（Paperfolding）產(chǎn)生了濃厚的興趣。正如他所開(kāi)發(fā)的無(wú)損壓縮方法聞名于計(jì)算機(jī)科學(xué)領(lǐng)域一樣，霍夫曼在折紙領(lǐng)域也成就非凡。

作為曲痕折紙（Curved-crease Paperfolding）的先驅(qū)人物，霍夫曼制作了幾百件曲痕折紙作品，這些作品代表了1970~1990間該領(lǐng)域的大部分成就，他的工作啟發(fā)了后世對(duì)曲痕折紙的進(jìn)一步研究。

霍夫曼同時(shí)研究數(shù)學(xué)和折紙藝術(shù)，他的主要興趣之一就是通過(guò)精確計(jì)算，使折疊出來(lái)的結(jié)構(gòu)避免給紙張施加壓力。通過(guò)數(shù)學(xué)計(jì)算，霍夫曼試圖理解，當(dāng)幾個(gè)折痕同時(shí)出現(xiàn)在一點(diǎn)的時(shí)候，什么樣的角度關(guān)系才不會(huì)使紙張拉伸或者撕裂。

他曾經(jīng)在論文Curvature and creases: A primer on paper中分析了曲痕折紙的數(shù)學(xué)性質(zhì)，并制作了雕塑來(lái)研究這種特殊的折疊方式。

為了普及折紙知識(shí)，霍夫曼曾在麻省理工學(xué)院和斯坦福等大學(xué)講授過(guò)折紙的理論和實(shí)踐課程并多次面向公眾發(fā)表折紙藝術(shù)的演講。在1979年一次面向科學(xué)家和藝術(shù)家的演講中，他表示科學(xué)和藝術(shù)這兩個(gè)群體中的人相互交流太少。

從70年代到90年代，霍夫曼創(chuàng)作了大量折紙，其中既有曲痕折紙，也有直痕折紙，這些折紙優(yōu)雅、美麗，堪稱(chēng)藝術(shù)品。麻省理工學(xué)院博物館收錄了一系列霍夫曼的折紙模型。

下面是霍夫曼的一些作品展示。

以上圖片來(lái)自http://erikdemaine.org/papers/Huffman_Origami5/paper.pdf

霍夫曼說(shuō)：“我從來(lái)沒(méi)有聲稱(chēng)自己是藝術(shù)家，我甚至不確定該如何定義藝術(shù)。但我發(fā)現(xiàn)折紙背后的優(yōu)雅數(shù)學(xué)定理很自然地使折紙呈現(xiàn)出一種優(yōu)雅的視覺(jué)效果。”

除了折紙以外，霍夫曼還擁有很多其他愛(ài)好。

早年他從香農(nóng)那里學(xué)會(huì)了騎獨(dú)輪車(chē)。離開(kāi)MIT加入加州大學(xué)圣克魯茲分校以后，因?yàn)檫@里距離西部山區(qū)很近，所以霍夫曼經(jīng)常徒步背包旅行和露營(yíng)。65歲時(shí)，他又愛(ài)上了浮潛和人體沖浪。

?成就非凡

霍夫曼的成就為他贏得了無(wú)數(shù)獎(jiǎng)項(xiàng)和榮譽(yù)。1999年，他獲得了電氣和電子工程師協(xié)會(huì) (IEEE) 頒發(fā)的理查德·漢明獎(jiǎng)?wù)?#xff08;Richard Hamming Medal），以表彰他對(duì)信息科學(xué)的杰出貢獻(xiàn)。他因其關(guān)于時(shí)序開(kāi)關(guān)電路的博士論文獲得了富蘭克林研究所的 Louis E. Levy Medal，他還獲得了俄亥俄州立大學(xué)的杰出校友獎(jiǎng)和 W. Wallace McDowell Award。1981年， IEEE 計(jì)算機(jī)學(xué)會(huì)為他頒發(fā)了計(jì)算機(jī)先鋒獎(jiǎng)；1998年，霍夫曼獲得了 IEEE 信息理論學(xué)會(huì)頒發(fā)的技術(shù)創(chuàng)新金禧獎(jiǎng)。

1999年10月7日，經(jīng)過(guò)與癌癥長(zhǎng)達(dá)10個(gè)月的斗爭(zhēng)，霍夫曼離開(kāi)了這個(gè)世界。

在霍夫曼的一生中，他從來(lái)沒(méi)為自己的任何一項(xiàng)發(fā)明創(chuàng)造申請(qǐng)過(guò)專(zhuān)利，雖然與億萬(wàn)富翁擦肩而過(guò)，但他似乎并沒(méi)有多么失望，畢竟霍夫曼編碼還幫他逃過(guò)期末考試一劫。

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

最后感謝趙軍老師推薦本期聲影傳奇人物——霍夫曼。

---

掃描圖中二維碼或點(diǎn)擊閱讀原文

了解大會(huì)更多信息

喜歡我們的內(nèi)容就點(diǎn)個(gè)“在看”吧！

總結(jié)

以上是生活随笔為你收集整理的灵光一现的创造——霍夫曼编码的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。