楊淨 尚恩 發自 凹非寺
誰曾想，一次學生不想參加考試的「任性」，後來竟影響了整個網際網路。
70年前MIT的一堂資訊論課上，一位老師為了給學生「減壓」，擺出一道選擇題。
要麼參加期末考試，要麼寫篇論文改進現有演算法，自己挑。
這位老師名叫羅伯特·範諾，他沒告訴學生們的是，這個「現有演算法」，正是他和資訊論創始人夏農合著的夏農-範諾編碼。而為了改進演算法不足，他本人已經投入大量時間進行研究。
（老師內心OS：沒想到吧。）
雖然有點損，但這招還真管用。這票學生一聽「交篇論文」就不用考試，拍腦袋就決定寫論文，包括大衛•哈夫曼。
不選不知道，一選嚇一跳。初出茅廬的哈夫曼很快意識到了老師挖的坑——這論文也太**難搞了。
這一寫，就是好幾個月，並且苦苦掙扎中，哈夫曼仍然一無所獲。
但命運，有時候就是十分奇妙。就在哈夫曼終於放棄「逃考」，準備將論文筆記扔到垃圾桶中時，突然靈光一現！答案出現了！
哈夫曼放棄對已有編碼的研究，轉向新的探索，最終發現了基於有序頻率二叉樹編碼的方法。
他提出的這一想法，效率成功超越他老師的方法論。甚至在之後的發展中，以他命名的編碼方法——哈夫曼編碼，直接改變
了資料壓縮正規化。
至於當時那篇結題報告，已引用近萬次。
低效的傳統編碼方法
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位在這裡並不多，但要是當擴展到數十億位元組時候，這就是一次不小的節省。
事實上，哈夫曼的方法已經被證明非常強大，據Google學術統計，當年論文已經被引用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]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