誰曾想，一次學生不想參加考試的 " 任性 "，後來竟影響了整個互聯網。
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 位在這裏并不多，但要是當擴展到數十億字節時候，這就是一次不小的節省。
事實上，哈夫曼的方法已經被證明非常強大，據谷歌學術統計，當年論文已經被引用 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
— 完 —
大咖雲集，錨定新技術，稀土開發者大會主會場亮點搶先看！
2023 年，數字技術快速發展，帶給人們新的掘金方向。以 " 不變 " 應 " 萬變 "，把握技術趨勢，需要所有開發者始終站在一起同頻共振，以期在新的範式轉換和新技術浪潮中摘得先機。
本屆大會主論壇演講嘉賓分别是：火山引擎副總裁 & 字節跳動開源治理運營負責人張鑫、英特爾軟件與先進技術事業部研發總監楊繼國、Google Cloud 首席架構師于有志、LVS 創始人章文嵩、火山引擎邊緣雲資深架構師徐廣治、北京大學王選計算機研究所教授、CCF 自然語言處理專委會秘書長萬小軍，他們将聚焦生成式 AI、雲原生、邊緣雲、ChatGPT 等熱門話題，深入分析新技術給未來産業帶來的挑戰和機遇。主會場還将爲「掘金引力榜」的獲獎項目和個人進行頒獎。點擊掃碼進入官網，點擊「立即報名」，還有少量名額可線下免費參與主論壇！
點這裏關注我，記得标星哦～
一鍵三連「分享」、「點贊」和「在看」
科技前沿進展日日相見 ~
