誰(shuí)曾想，一次學(xué)生不想?yún)⒓涌荚嚨摹叭涡浴?，后?lái)竟影響了整個(gè)互聯(lián)網(wǎng)。
70 年前 MIT 的一堂信息論課上，一位老師為了給學(xué)生“減壓”，擺出一道選擇題。
要么參加期末考試，要么寫篇論文改進(jìn)現(xiàn)有算法，自己挑。
這位老師名叫羅伯特?范諾，他沒(méi)告訴學(xué)生們的是，這個(gè)“現(xiàn)有算法”，正是他和信息論創(chuàng)始人香農(nóng)合著的香農(nóng)-范諾編碼。而為了改進(jìn)算法不足，他本人已經(jīng)投入大量時(shí)間進(jìn)行研究。
（老師內(nèi)心 OS：沒(méi)想到吧。）
雖然有點(diǎn)損，但這招還真管用。這票學(xué)生一聽“交篇論文”就不用考試，拍腦袋就決定寫論文，包括大衛(wèi)?哈夫曼。
不選不知道，一選嚇一跳。初出茅廬的哈夫曼很快意識(shí)到了老師挖的坑 —— 這論文也太 ** 難搞了。
這一寫，就是好幾個(gè)月，并且苦苦掙扎中，哈夫曼仍然一無(wú)所獲。
但命運(yùn)，有時(shí)候就是十分奇妙。就在哈夫曼終于放棄“逃考”，準(zhǔn)備將論文筆記扔到垃圾桶中時(shí)，突然靈光一現(xiàn)！答案出現(xiàn)了！
哈夫曼放棄對(duì)已有編碼的研究，轉(zhuǎn)向新的探索，最終發(fā)現(xiàn)了基于有序頻率二叉樹編碼的方法。
他提出的這一想法，效率成功超越他老師的方法論。甚至在之后的發(fā)展中，以他命名的編碼方法 —— 哈夫曼編碼，直接改變了數(shù)據(jù)壓縮范式。
至于當(dāng)時(shí)那篇結(jié)題報(bào)告，已引用近萬(wàn)次。
低效的傳統(tǒng)編碼方法
1951 年，正在 MIT 任教的羅伯特?范諾正在思考一道信息論的難題：
如何用二進(jìn)制代碼高效表示數(shù)字、字母或者其他符號(hào)？
當(dāng)時(shí)最常見、也是最直接的方法，就是為每個(gè)字符分配一個(gè)獨(dú)一無(wú)二的二進(jìn)制數(shù)。
比如，字母 A 可能表示為 01000001，！表示為 00100001，每個(gè)八位數(shù)的數(shù)字都對(duì)應(yīng)一個(gè)字符。
這樣一來(lái)代碼容易解析，但效率極低。
另外還有種優(yōu)化方法，類似于摩爾斯電碼。常用字母 E 僅由一個(gè)點(diǎn)表示，但不常見的 Q 需要更長(zhǎng)且更費(fèi)力的“—— ——?——”。
這種方式，會(huì)導(dǎo)致代碼長(zhǎng)度不一，信息不容易被理解；而且傳輸中還需要在字符間加入間隙，否則就無(wú)法區(qū)分不同的字符組合。
范諾意識(shí)到，或許這兩種方法的優(yōu)勢(shì)可以兼并之 —— 以不同長(zhǎng)度的二進(jìn)制代碼表示字符。進(jìn)一步地，為避免代碼“重疊”，他還構(gòu)建了二叉樹。
他詳盡地測(cè)試了每一種排列的可能性以獲得最大效率，最終得到了一種有效情況：
每條消息按照頻率分為兩個(gè)分支，并盡可能讓兩邊字母使用頻率基本相同。
這樣，常用的字符就會(huì)在更短、密度更低的分支上。
1948 年，信息論之父香農(nóng)在介紹信息理論的文章“通信數(shù)學(xué)理論”中提出了這一方法；不久之后，范諾也獨(dú)立地以技術(shù)報(bào)告形式將其發(fā)布。故而這套方法被稱作是香農(nóng)-范諾編碼。
但這個(gè)方法并非總是有效。像字母出現(xiàn)概率分別為 {0.35，0.17，0.17，0.16，0.15} 這種情況時(shí)，就不能給出理想編碼。
范諾認(rèn)為一定存在更好壓縮策略。于是乎，這樣的重任就交到了他的學(xué)生手里。
一次靈光乍現(xiàn)，一篇世紀(jì)論文
如果說(shuō)，范諾教授他們的方法是從上到下構(gòu)建字符樹，并在成對(duì)的樹枝之間盡可能保持對(duì)稱。
那么哈夫曼的方法，是直接顛覆了這一過(guò)程 —— 自下而上構(gòu)建二叉樹。
他認(rèn)為，無(wú)論發(fā)生什么情況，在一段有效的代碼中，兩個(gè)最不常見的字符應(yīng)該有兩個(gè)最長(zhǎng)的代碼。
因此首先就確定兩個(gè)最不常見的字符，將它們組合在一起作為一個(gè)分支對(duì)，然后再重復(fù)該過(guò)程，再?gòu)氖Ｓ嘧址信c剛剛構(gòu)建的字符對(duì)中尋找最不常見的字符（對(duì)）。
以 schoolroom 為例，其中 O 出現(xiàn)了四次，S、C、H、L、R、M 各出現(xiàn)一次。
范諾的方法，就是首先將 O 與另一個(gè)字母分配給左側(cè)分支，這樣一來(lái)兩邊都是 5 次總使用量，生成的編碼總共 27 位。
相比之下，哈夫曼的方法，比如就從不常見的 r 和 m 開始，將其組合成一個(gè)字母對(duì)。
組合完之后，現(xiàn)有字符（對(duì)）包括：O（4 次）、RM（2 次）以及單個(gè)字母 S、C、H 和 L。
按照出現(xiàn)頻率劃分，重復(fù)上一操作 —— 將兩個(gè)不常見的選項(xiàng)分組，然后更新數(shù)樹和頻率圖。
最終，“schoolroom”變成了 11101111110000110110000101，比 Fano 自上而下的方法少了 1 位。
雖然 1 位在這里并不多，但要是當(dāng)擴(kuò)展到數(shù)十億字節(jié)時(shí)候，這就是一次不小的節(jié)省。
事實(shí)上，哈夫曼的方法已經(jīng)被證明非常強(qiáng)大，據(jù)谷歌學(xué)術(shù)統(tǒng)計(jì)，當(dāng)年論文已經(jīng)被引用 9570 次。
至于他老師的辦法，卻幾乎沒(méi)有再被使用過(guò)。
直至今天，幾乎所有無(wú)損壓縮方法都全部或部分使用了哈夫曼的方法，可以壓縮圖像、音頻、表格等。它支持從 PNG 圖像標(biāo)準(zhǔn)到無(wú)處不在的軟件 PKZip 的一切。
現(xiàn)代計(jì)算機(jī)科學(xué)先驅(qū)、圖靈獎(jiǎng)得主高德納曾這樣形容哈夫曼的成就：
在計(jì)算機(jī)科學(xué)和數(shù)據(jù)通信領(lǐng)域，哈夫曼編碼是人們一直在使用的基本思想。
后來(lái)哈夫曼再回憶起那個(gè)「靈光乍現(xiàn)」時(shí)刻，當(dāng)時(shí)他正準(zhǔn)備將論文筆記扔進(jìn)垃圾桶，結(jié)果突然思想?yún)R聚，答案在腦海里出現(xiàn)了：
那是我生命中最奇特的時(shí)刻。
突然恍然大悟，猶如閃電一般。
并表示，如果他知道自己的教授范諾 (Fano) 曾與這個(gè)問(wèn)題作過(guò)斗爭(zhēng)，他可能永遠(yuǎn)都不會(huì)嘗試解決這個(gè)問(wèn)題，更不用說(shuō)在 25 歲的時(shí)候就大膽去嘗試。
成就與秩序感，用數(shù)學(xué)玩藝術(shù)
哈夫曼編碼改變了數(shù)據(jù)壓縮范式，也為其贏得了眾多榮譽(yù)與獎(jiǎng)?wù)隆?/p>
比如，1998 年哈夫曼獲得 IEEE 信息理論學(xué)會(huì)頒發(fā)的技術(shù)創(chuàng)新金禧獎(jiǎng)、1999 年獲得電氣和電子工程師協(xié)會(huì) (IEEE) 頒發(fā)的理查德?漢明獎(jiǎng)?wù)拢≧ichard Hamming Medal）。
不過(guò)即便如此，在他一生歷程中，相比發(fā)明無(wú)損壓縮方法這件事兒，最讓他引以為傲的反而是這篇博士論文。
題目：The Synthesis of Sequential Switching Circuits。
哈夫曼在 MIT 讀博期間，發(fā)布這篇討論時(shí)序開關(guān)電路的重要論文。在當(dāng)時(shí)，哈夫曼幾乎是首個(gè)闡述如何設(shè)計(jì)異步順序開關(guān)電路的學(xué)者，而這一理論后來(lái)也為計(jì)算機(jī)發(fā)展提供了重要邏輯支撐。
這篇論文的發(fā)布，不僅幫助他獲得富蘭克林研究所的 Louis E. Levy Medal，也順理成章讓他獲得留校任職資格，教授關(guān)于開關(guān)電路的課程。
在校期間，哈夫曼還提出一種革新的數(shù)學(xué)公式，可以在不丟失任何信息的情況下將一個(gè)二進(jìn)制數(shù)序列轉(zhuǎn)換成另一個(gè)二進(jìn)制數(shù)序列，這項(xiàng)研究在當(dāng)時(shí)密碼學(xué)中發(fā)揮了重要作用，也為其謀得了一份重要職位。
時(shí)任貝爾實(shí)驗(yàn)室研究副總裁的 William O. Baker 將其招納入了一個(gè)審查委員會(huì)，主要負(fù)責(zé)為國(guó)家安全局審查未來(lái)科技計(jì)劃。Baker 博士曾擔(dān)任過(guò)艾森豪威爾、肯尼迪、約翰遜、尼克松和里根五位總統(tǒng)的科學(xué)顧問(wèn)。
1967 年已是正教授的霍夫曼選擇離開 MIT，加入加利福尼亞大學(xué)圣克魯茲分校 (UCSC)，期間主導(dǎo)創(chuàng)立了計(jì)算機(jī)科學(xué)系，并參與學(xué)術(shù)課程開發(fā)工作，為之后計(jì)算機(jī)科學(xué)系發(fā)展奠定重要基礎(chǔ)。
數(shù)學(xué)可以說(shuō)是哈夫曼畢生追求之一，以至于后來(lái)在搞藝術(shù)時(shí)，也離不開數(shù)學(xué)。
70 年代開始，哈夫曼對(duì)折紙產(chǎn)生濃厚興趣，同時(shí)研究數(shù)學(xué)和折紙藝術(shù)，制作了上百件曲痕折紙作品，還專門發(fā)表論文分析曲痕折紙的數(shù)學(xué)性質(zhì)，成為折紙數(shù)學(xué)領(lǐng)域的先驅(qū)人物。
回過(guò)頭看，哈夫曼的一生贏得過(guò)無(wú)數(shù)榮譽(yù)與表彰，卻從未為自己任何一項(xiàng)發(fā)明申請(qǐng)過(guò)專利。
最后，借用哈夫曼自己的一段話。
作為一名科學(xué)家和老師，我真的非常執(zhí)著。如果我覺得自己還沒(méi)有找到問(wèn)題的最簡(jiǎn)單解決方法，我會(huì)非常不滿意，這種不滿會(huì)一直持續(xù)，直到我找到最佳方法為止。對(duì)我來(lái)說(shuō)，這就是科學(xué)家的本質(zhì)。
參考鏈接：
[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
本文來(lái)自微信公眾號(hào)：量子位 （ID：QbitAI），作者：楊凈 尚恩
廣告聲明：文內(nèi)含有的對(duì)外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。