第 5 章　霍夫曼與克勞德·香農：資訊理論與資料壓縮演算法的破曉#

5.2 戴維·霍夫曼的期末作業逆襲：為了完成課程作業而發明「霍夫曼編碼」的傳奇歷史#

5.2.1 MIT 那門課與那道題#

1951 年，25 歲的 David A. Huffman（1925–1999）在 MIT 選修 Robert Fano 的信息論課程。期末選項：寫報告，或解一道公開難題——找出最優的前綴二進制碼（給定各符號出現頻率，構造平均碼長最短的無歧義碼）。Fano 自己（與 Shannon 一起）未能解出最優情形。Huffman 選了難題。

5.2.2 傳說與史實的交界#

流傳版本：Huffman 幾個月無所獲，一度準備放棄轉寫報告；拋開筆記的某一刻靈光乍現——「從底部向上建樹」（自底向上合併兩個最低頻符號），數分鐘內得到最優解。據 Huffman 本人在 1991 年受訪（Scientific American 邀稿回憶錄）所述，過程確實如此：他放棄「自頂向下」的 Shannon–Fano 思路後，「決心證明這辦不到」的反證努力反而引出了合併法。霍夫曼後來自嘲：如果早知道 Fano 已研究多年，他可能根本不敢開始。

5.2.3 演算法與最優性#

貪心選擇性質可證：任何最優前綴碼必有兩個最低頻符號互為兄弟（可交換歸約），故合併策略全局最優；複雜度 \(O(n\log n)\)（堆實現）。平均碼長 \(L=\sum p_i \ell_i\) 滿足 \(H(X)\le L < H(X)+1\)。

5.2.4 選擇的代價與遺產#

Huffman 回憶，為 MIT 課題解出此題時不知道這將是博士論文級成果（他最終以開關電路理論獲博士）。此演算法進入：UNIX 的 compress（LZWH）、JPEG／MP3 的熵編碼層、HP 的印表機指令集（他後期在 HP 的貢獻之一）……一個學生的課堂作業，成為數位世界的標準零件。

5.2.5 前因後果#

• 前因：5.1 香農理論＋Fano 的未竟之題＋MIT 的研究型教學傳統。
• 事件：1951 解出、1952 論文發表（A Method for the Construction of Minimum-Redundancy Codes）。
• 後果：貪心演算法教學的經典範例；5.3 的 LZ 系列將在「字典壓縮」路線上超越頻率編碼，兩者於 DEFLATE（ZIP、gzip、PNG）中合體。

下一節：5.3 無損壓縮