霍夫曼編碼

霍夫曼編碼將符號對應至可變長度位元字串。前綴無關碼不會有任何一個碼字是另一個碼字的前綴，因此解碼器可以沿著一棵二元樹行走，抵達葉節點時立即輸出符號。前綴無關碼都能唯一解碼，但可唯一解碼的編碼不一定都具備前綴無關性。

前綴無關碼與 Kraft 不等式 #

對於碼字長度為 lᵢ 的二元前綴碼，Kraft 不等式為

Σ 2^(-lᵢ) ≤ 1

不等式計算每個葉節點佔用二元樹的比例。反過來，每個符合該不等式的正整數長度序列，都能由二元前綴碼實現。等號表示完整的樹；嚴格不等式則代表存在未使用的分支。

建立頻率樹 #

給定符號頻率後，霍夫曼演算法會反覆移除權重最低的兩個節點，將它們置於權重為兩者總和的節點下作為兄弟，再插回該節點。符號的深度就是其碼長。將稀有符號合併至樹的最深處，提供了最佳性的直觀交換論證：將頻繁符號移到較不頻繁符號之上，不會增加加權路徑長度。對於提供的頻率，產生的樹會在二元前綴碼中使期望長度最小。

while more than one node remains:
    a, b = remove the two lowest-weight nodes
    insert node(weight(a) + weight(b), a, b)

相同權重允許多棵最佳樹。確定性實作必須定義平手時的排序，例如在頻率之後比較穩定的符號序號。即使期望位元數不變，確定性仍對可重現輸出與測試很重要。需要最大碼長的格式必須使用碼長受限的霍夫曼演算法；直接截短樹可能違反 Kraft 不等式，或改變預期的符號順序。

短輸入或高熵輸入的碼表負擔可能超過節省的空間。霍夫曼編碼是表示方式的選擇，不保證每個輸入都會變小。

標準化重建 #

許多格式傳送碼長，而不是左右樹指標。標準化建構會依 (length, symbol order) 排序作用中的符號，並在每個長度內指定連續的整數碼；長度增加時，將下一個碼向左移位。解碼器會重複該計算，然後將每個碼插入查找表或解碼樹。因此，相同的長度不需要傳送樹形狀也能產生相同的碼。

例如，符號 A 到 D 的長度 (1, 2, 3, 3) 會產生下列標準化表：

該表記錄邏輯碼值。以位元為導向的格式可以用不同順序序列化這些值；例如 DEFLATE 在將霍夫曼位元封裝至串流時會反轉它們。

解碼器應使用經檢查的算術建立表格，並拒絕：

• 超出外層格式限制的碼長；
• 過度訂閱的集合，其中長度要求的葉節點多於樹所包含的數量；
• 格式要求完整樹時的不完整集合；
• 重複或超出範圍的符號、格式錯誤的重複指令，以及缺少必要的區塊結束符號；
• 走過表格或在碼內結束的位元序列。

查找表可以一次解碼多個位元，但慢速路徑仍必須驗證碼長與剩餘輸入。將無效表格項目視為符號，會把格式錯誤的輸入轉成無聲的損毀。

具體的標準化格式請參閱 DEFLATE 與 Gzip 格式。

參考資料 #

• D. A. Huffman，「最小冗餘碼的建構方法」，Proceedings of the IRE，1952。
• RFC 1951：DEFLATE，第 3.2.1–3.2.2 節