霍夫曼編碼（1952）：源自 MIT 作業的最佳前綴碼

Claude Shannon 於 1948 年的研究奠定資訊理論，並定義熵：

H = −Σ p(x) log₂ p(x)

在機率模型中，熵代表每個來源符號的平均資訊量。來源編碼定理給出長區塊編碼的漸近極限；它並不是說每個有限檔案都必須恰好至少使用 H 位元／符號。

Shannon 與 Robert Fano 發展出一種自頂向下的編碼方式，現在稱為 Shannon–Fano 編碼，但這種構造並非對所有機率分布都最佳。

David A. Huffman 當時是 MIT Robert Fano 資訊理論課程的研究生。後來的記述提到，作業可在參加期末考與撰寫一份找出最高效率二元碼的報告之間二選一。

Huffman 發現一種由下而上的構造，可在給定符號權重下，將二元前綴碼的平均碼字長度降到最低。他僅四頁的論文〈A Method for the Construction of Minimum-Redundancy Codes〉刊登於 1952 年 9 月的 Proceedings of the IRE。

課堂上的選擇，以及丟棄筆記時得到靈感的故事，都來自後來的回憶，而不是原始論文本身。

給定符號與機率後，反覆合併出現頻率最低的兩個節點：

1. 為每個符號建立一個葉節點。
2. 選出權重最小的兩個節點。
3. 把兩者連到同一個父節點，父節點權重為兩者之和。
4. 重複以上步驟，直到只剩一個根節點。
5. 將兩條向外的邊標為 0 與 1。

A 45%、B 13%、C 12%、D 16%、E 9%、F 5%

F(5)  + E(9)  → FE(14)
C(12) + B(13) → CB(25)
FE(14) + D(16) → FED(30)
CB(25) + FED(30) → BCDEF(55)
A(45) + BCDEF(55) → 根節點(100)

其中一棵有效的樹會分配 1、3、3、3、4、4 的碼字長度。其平均長度為：

L = 0.45×1 + 0.13×3 + 0.12×3 + 0.16×3 + 0.09×4 + 0.05×4
  = 2.24 位元／符號

此分布的熵約為 2.21988 位元／符號。霍夫曼碼在這個分布的二元前綴碼中確實是最佳解；所謂「接近」描述的是它與熵下界的距離，而不是對前綴碼最佳性有所保留。

在某棵最佳樹中，可以把機率最低的兩個符號放在最深層，並使其成為具有同一父節點的兄弟葉節點。把兩者合併後，就會形成同一問題的較小實例。反覆使用這項化簡，便能以數學歸納法證明貪婪構造。

適用範圍很重要。霍夫曼編碼會為每個符號的前綴碼字分配整數個位元。算術編碼則把整段訊息表示成逐步縮小的區間，因此就整段訊息而言，每個來源符號的平均位元數可以不是整數。

RFC 1951 將 DEFLATE 定義為類似 LZ77 的序列表示方式，再搭配霍夫曼編碼。它定義三種區塊：

• 未壓縮區塊；
• 使用 RFC 指定固定霍夫曼碼的區塊；
• 攜帶動態霍夫曼碼長度的區塊。

gzip、zlib、PNG、HTTP Content-Encoding: gzip，以及 ZIP 的一種常見壓縮方式都會使用 DEFLATE。ZIP 支援多種方法，也包含直接儲存而不壓縮，因此 ZIP 不等同於 DEFLATE。DEFLATE 資料流也不會替每一個區塊都建立新的霍夫曼樹。

JPEG

常見的基線循序 DCT JPEG 流程會先轉換取樣值、量化係數，再以霍夫曼碼進行熵編碼。ISO/IEC 10918-1 也包含算術編碼，所以「JPEG 一律使用霍夫曼編碼」的說法太過籠統。色彩解讀與常見 RGB／YCbCr 慣例，也涉及 JFIF 等應用設定檔，並不是所有 JPEG 編碼流程都被強制套用同一個通用步驟。

MP3

MPEG Layer III 在量化後的頻譜值編碼中，會使用規定的霍夫曼碼表。霍夫曼編碼只是這套大型感知音訊編解碼器的其中一個階段。

HPACK

HTTP/2 HPACK 可以透過靜態與動態資料表索引表示標頭欄位。字串常值可使用 RFC 7541 附錄 B 的固定霍夫曼表，也可以不採用霍夫曼編碼。在該表中，'a' 是 5 位元、':' 是 7 位元、'A' 是 6 位元。壓縮節省量取決於字串與資料表狀態，不存在適用所有流量的單一百分比。

方法	與模型的關係	實作特性	範例
霍夫曼編碼	對合適的分布可接近熵	樹狀或資料表查詢	DEFLATE、基線 JPEG、MP3、HPACK
算術編碼	可更接近模型熵	更新區間	HEVC CABAC、JPEG 2000
ANS	接近算術編碼的效率	可採用高速查表實作	Zstandard FSE、LZFSE

Jarek Duda 於 2009 年發表非對稱數字系統（ANS）研究，並在 2010 年代逐漸擴大應用。Zstandard 同時使用霍夫曼編碼與 ANS 家族的有限狀態熵（FSE）技術，但不是每個壓縮區塊都必須使用兩者。

RFC 8878 允許字面資料區段採用未壓縮資料（raw）、連續長度編碼（RLE）或霍夫曼壓縮。霍夫曼權重可以直接表示，也可以用 FSE 壓縮。字面資料長度、偏移量與匹配長度的符號資料表，則可採用預先定義、RLE、FSE 壓縮或重複使用先前資料表等模式。

• 霍夫曼編碼在指定的二元前綴碼問題中是最佳解。
• 其貪婪演算法會反覆合併權重最小的兩個節點。
• 熵是以模型為基礎的平均極限，而不是每個檔案都適用的神奇大小。
• DEFLATE、JPEG、MP3、HPACK 與 Zstandard 都在不同且可選的結構中使用霍夫曼編碼。
• 算術編碼與 ANS 以不同方式避開每個符號必須使用整數長度碼字的限制。