敖飛寺楊靖山恩

量子比特|公眾號QbitAI

誰能想到，一個學(xué)生不想考試的“任性”，后來影響了整個互聯(lián)網(wǎng)。

70年前，在麻省理工學(xué)院的信息論課上，一位老師為了“減輕”學(xué)生的壓力，提出了一道選擇題。

要么參加期末考試，要么寫一篇論文來改進(jìn)現(xiàn)有算法，您可以選擇。

老師的名字叫羅伯特·范諾。他沒有告訴學(xué)生的是，這個“現(xiàn)有算法”就是他和信息論創(chuàng)始人香農(nóng)共同創(chuàng)作的香農(nóng)-法諾碼。為了改進(jìn)算法的缺點(diǎn)，他本人投入了大量的時間進(jìn)行研究。

（老師內(nèi)心OS：沒想到。）

雖然傷害有點(diǎn)大，但這招確實(shí)管用。包括大衛(wèi)·霍夫曼在內(nèi)的這群學(xué)生一聽到“交論文”就決定不考試寫論文。

如果你不選擇，你就不會知道。如果你選擇，你會感到震驚。剛?cè)腴T的霍夫曼很快意識到老師在卷子上挖了一個洞：——，這個洞太難解了。

這篇寫作花了幾個月的時間，盡管付出了艱辛的努力，霍夫曼仍然一無所獲。

但命運(yùn)有時就是很奇怪。就在霍夫曼終于放棄“逃考”，準(zhǔn)備把紙條扔進(jìn)垃圾桶時，他突然靈機(jī)一動！答案出現(xiàn)了！

霍夫曼放棄了對現(xiàn)有編碼的研究，轉(zhuǎn)向新的探索，最終發(fā)現(xiàn)了一種基于有序頻率二叉樹編碼的方法。

他提出的想法比他老師的方法更有效。甚至在后來的發(fā)展中，以他命名的編碼方法——霍夫曼編碼直接改變了數(shù)據(jù)壓縮范式。

至于當(dāng)時的最終報(bào)告，已經(jīng)被引用了近萬次。

傳統(tǒng)編碼方法效率低下1951年，在麻省理工學(xué)院任教的羅伯特·范諾正在思考信息論中的一個難題：

如何用二進(jìn)制代碼高效地表示數(shù)字、字母或其他符號？

當(dāng)時最常見、最直接的方法是為每個字符分配一個唯一的二進(jìn)制數(shù)。

例如，字母A可以表示為01000001，表示為00100001，每個八位數(shù)字對應(yīng)一個字符。

這使得代碼易于解析，但效率極低。

還有一種優(yōu)化方法，類似于摩爾斯電碼。常見的字母E只用一個點(diǎn)來表示，但不常見的Q則需要更長、更費(fèi)力的“—— ——·——”。

這種方式會導(dǎo)致代碼長度不同，信息不易理解；而且傳輸時字符之間需要添加間隙，否則無法區(qū)分不同的字符組合。

范諾意識到也許可以結(jié)合這兩種方法的優(yōu)點(diǎn)來表示不同長度的二進(jìn)制代碼中的字符。此外，為了避免代碼“重疊”，他還構(gòu)造了一個二叉樹。

他詳盡地測試了每種排列以獲得最大效率的可能性，最終得出了一種可行的情況：

每條消息按照頻率分為兩個分支，兩邊字母的使用頻率盡可能基本一致。

這樣，常用的字符將出現(xiàn)在較短、較不密集的分支上。

1948年，信息論之父香農(nóng)在介紹信息論的文章《通信的數(shù)學(xué)理論》中提出了這一方法；不久之后，范諾也以技術(shù)報(bào)告的形式獨(dú)立發(fā)表。因此，這種方法稱為Shannon-Fano編碼。

但這種方法并不總是有效。例如，當(dāng)字母出現(xiàn)的概率為{0.35,0.17,0.17,0.16,0.15}時，無法給出理想的編碼。

范諾認(rèn)為必須有更好的壓縮策略。于是乎，這么重要的任務(wù)就交給了他的學(xué)生們。

范諾教授靈光一閃，在一篇世紀(jì)論文中表示，他們的方法是從上到下構(gòu)建一棵字符樹，并在成對的分支之間保持盡可能多的對稱性。

所以哈夫曼的方法直接顛覆了這個過程，自下而上構(gòu)建二叉樹。

他認(rèn)為，無論發(fā)生什么，在有效的代碼中，兩個最不常見的字符應(yīng)該具有兩個最長的代碼。

因此，首先識別出兩個最不常見的字符，將它們組合在一起作為分支對，然后重復(fù)該過程，從剩余的字符和剛剛構(gòu)建的字符對中找到最不常見的字符（對）。

以教室為例，O 出現(xiàn)四次，S、C、H、L、R、M 各出現(xiàn)一次。

Fanno的方法是先將O和另一個字母賦給左邊的分支，這樣兩邊總共使用了5次，生成的代碼總共27位。

相比之下，例如，霍夫曼的方法從不常見的r 和m 開始，并將它們組合成字母對。

組合后，現(xiàn)有字符對包括：O（4次）、RM（2次）以及單個字母S、C、H、L。

根據(jù)出現(xiàn)頻率進(jìn)行劃分，重復(fù)前面的操作——，將兩個不常見的選項(xiàng)分組，然后更新數(shù)樹和頻數(shù)圖。

最終，“schoolroom”變?yōu)?1101111110000110110000101，這比Fano 自上而下的方法少了1 位數(shù)字。

雖然1 位在這里并不算多，但當(dāng)擴(kuò)展到數(shù)十億字節(jié)時，這是一個相當(dāng)大的節(jié)省。

事實(shí)上，霍夫曼的方法已經(jīng)被證明是非常強(qiáng)大的。據(jù)Google Scholar統(tǒng)計(jì)，該論文當(dāng)年被引用9570次。

至于他老師的方法，幾乎就沒有再用過。

時至今日，幾乎所有無損壓縮方法都全部或部分使用霍夫曼方法，并且可以壓縮圖像、音頻、表格等。它支持從PNG圖像標(biāo)準(zhǔn)到無處不在的軟件PKZip。

現(xiàn)代計(jì)算機(jī)科學(xué)的先驅(qū)、圖靈獎獲得者高德納曾這樣形容霍夫曼的成就：

在計(jì)算機(jī)科學(xué)和數(shù)據(jù)通信領(lǐng)域，霍夫曼編碼是人們一直在使用的基本思想。

后來，霍夫曼回憶起那個“頓悟”的時刻。當(dāng)時他正要把紙條扔進(jìn)垃圾桶，突然思緒一齊，腦海中浮現(xiàn)出了答案：

這是我一生中最奇怪的時刻。我突然意識到，就像閃電一樣。

他說，如果他知道他的教授法諾一直在為這個問題苦苦掙扎，他可能永遠(yuǎn)不會嘗試解決它，更不用說在25 歲時冒險嘗試了。

帶著成就感和秩序感，用數(shù)學(xué)玩藝術(shù)，用霍夫曼編碼改變了數(shù)據(jù)壓縮范式，為他贏得了許多榮譽(yù)和獎牌。

例如，霍夫曼于1998年獲得IEEE信息理論學(xué)會頒發(fā)的技術(shù)創(chuàng)新金禧獎，并于1999年獲得電氣和電子工程師協(xié)會（IEEE）頒發(fā)的理查德·漢明獎?wù)隆?

但即便如此，在他的一生中，與無損壓縮方法的發(fā)明相比，他最引以為傲的還是這篇博士論文。標(biāo)題：順序開關(guān)電路的綜合。

當(dāng)霍夫曼在麻省理工學(xué)院攻讀博士學(xué)位時，他發(fā)表了這篇討論順序開關(guān)電路的重要論文。當(dāng)時，霍夫曼幾乎是第一個解釋如何設(shè)計(jì)異步順序開關(guān)電路的學(xué)者，這一理論后來為計(jì)算機(jī)的發(fā)展提供了重要的邏輯支持。

這篇論文的發(fā)表不僅幫助他獲得了富蘭克林研究所的Louis E. Levy Medal，也自然讓他獲得了留在學(xué)校教授開關(guān)電路課程的資格。

在學(xué)校期間，霍夫曼還提出了一種創(chuàng)新的數(shù)學(xué)公式，可以將一個二進(jìn)制數(shù)字序列轉(zhuǎn)換為另一個二進(jìn)制數(shù)字序列，而不會丟失任何信息。這項(xiàng)研究在當(dāng)時的密碼學(xué)領(lǐng)域發(fā)揮了重要作用。也為他獲得了重要的職位。

時任貝爾實(shí)驗(yàn)室研究副總裁的威廉·O·貝克（William O. Baker）招募他加入一個審查委員會，主要負(fù)責(zé)審查國家安全局未來的技術(shù)計(jì)劃。貝克博士曾擔(dān)任五位總統(tǒng)的科學(xué)顧問：艾森豪威爾、肯尼迪、約翰遜、尼克松和里根。

1967年，已經(jīng)是正教授的霍夫曼選擇離開麻省理工學(xué)院，加入加州大學(xué)圣克魯斯分校（UCSC）。在此期間，他主導(dǎo)建立了計(jì)算機(jī)系并參與了學(xué)術(shù)課程的開發(fā)，為計(jì)算機(jī)系的后續(xù)發(fā)展奠定了重要基礎(chǔ)。

數(shù)學(xué)可以說是霍夫曼一生的追求之一，以至于后來他從事藝術(shù)時，都離不開數(shù)學(xué)。

從20 世紀(jì)70 年代開始，霍夫曼對折紙產(chǎn)生了濃厚的興趣。他同時學(xué)習(xí)數(shù)學(xué)和折紙藝術(shù)，創(chuàng)作了數(shù)百幅彎曲的折紙作品。他還發(fā)表了一篇分析彎曲折紙數(shù)學(xué)特性的論文，成為折紙數(shù)學(xué)領(lǐng)域的先驅(qū)。

回想起來，霍夫曼一生贏得了無數(shù)榮譽(yù)和嘉獎，但從未為他的任何發(fā)明申請過專利。

最后，讓我借用霍夫曼本人的一句話。

作為一名科學(xué)家和教師，我真的很執(zhí)著。如果我覺得我還沒有找到問題的最簡單的解決方案，我就會變得極度不滿，并且這種不滿會持續(xù)下去，直到我找到最好的解決方案。對我來說，這就是作為一名科學(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

- 超過-

量子比特QbitAI·今日頭條訂閱關(guān)注我們，第一時間了解前沿技術(shù)動態(tài)