什麼是霍夫曼編碼

根據符號出現的機率，做出平均碼長最小之前綴碼的方法。反覆把機率最小的2個符號（或節點）合併為1個以建立樹，並在各分岔處分配0與1作為碼字。越常出現的符號碼字越短。在逐一對符號編碼的前綴碼中是最佳的，平均碼長在熵以上、未滿熵 + 1 位元。在ZIP與gzip的Deflate、JPEG等中與其他方式組合使用。由霍夫曼於1952年發表。

日文名稱: ハフマン符号

「霍夫曼編碼」出現在1領域的5道練習題中（資訊理論與編碼基礎等）。

這個名詞所屬的領域: 資訊理論與編碼基礎

做法

例如機率為1/2、1/4、1/8、1/8的符號，先把兩個1/8合併為1/4，再把它與1/4合併為1/2，最後與剩下的1/2合併。在從根到各符號的分岔處標上0與1，碼字就成為 0、10、110、111，平均碼長為1.75位元，與熵相等。機率全部是2的冪次分之一時，平均碼長就會像這樣與熵一致。

碼字不是唯一的

依0與1的標法，以及相等機率先合併哪一個，碼字會改變。例如機率為0.4、0.2、0.2、0.1、0.1時，碼長可能是1、2、3、4、4，也可能是1、3、3、3、3或2、2、2、3、3，但平均碼長都是2.2位元。因此考試中多半問平均碼長，而不是碼字本身。

極限與改良

碼長只能是整數位元，因此有機率接近1之符號的資訊源，與熵的差距會變大。逐一對二元符號編碼時，無論偏差多大，每個符號都需要1位元。把符號合併編碼，或使用算術編碼這類不受整數位元限制的方式，就能接近熵。

練習霍夫曼編碼的題目

某資訊源以機率0.4、0.3、0.2、0.1彼此獨立地輸出符號A、B、C、D，以霍夫曼編碼進行編碼。每個符號的平均碼長為下列何者？

A約1.85位元
B1.9位元
C2位元

查看答案與解析

正確答案：B. 1.9位元

霍夫曼編碼反覆把機率最小的2個合併。先把0.1與0.2合併為0.3，接著把0.3與0.3合併為0.6，最後合併0.6與0.4，因此碼長為A 1位元、B 2位元、C與D 3位元。平均碼長為 0.4 × 1 + 0.3 × 2 + 0.2 × 3 + 0.1 × 3 = 1.9 位元。

某資訊源以機率0.3、0.25、0.2、0.15、0.1彼此獨立地輸出符號A～E，以霍夫曼編碼進行編碼。相等的機率先選哪一個，可能會使碼字不同，但平均碼長不變。每個符號的平均碼長為下列何者？

A2.25位元
B2.4位元
C3位元

查看答案與解析

正確答案：A. 2.25位元

先把0.1與0.15合併為0.25，接著把0.2與0.25合併為0.45，再把剩下的0.25與0.3合併為0.55，最後合併0.45與0.55。碼長為A、B、C 2位元、D與E 3位元，平均碼長為 (0.3 + 0.25 + 0.2) × 2 + (0.15 + 0.1) × 3 = 1.5 + 0.75 = 2.25 位元。機率偏差不大的資訊源，長度整齊的碼會比 1、2、3、4、4 這種階梯狀的碼長更短。

常見問題

要還原以霍夫曼編碼壓縮的資料，需要什麼？

需要知道哪個符號分配了哪個碼字（碼表，或各符號的碼長）。因此壓縮後的資料會附上碼表，或使用事先約定的表。Deflate只傳送碼長，接收端再以相同規則重建碼字（標準霍夫曼碼）。

霍夫曼編碼能讓任何資料變小嗎？

不能。符號出現的機率若沒有偏差，幾乎無法縮小。例如256種位元組全部以相同機率出現的資料，每個碼字都是8位元，加上碼表反而會變大。

解析中的「霍夫曼編碼」

霍夫曼編碼反覆把機率最小的2個合併。
某資訊源以機率0.4、0.3、0.2、0.1彼此獨立地輸出符號A、B、C、D，以霍夫曼編碼進行編碼。每個符號的平均碼長…
霍夫曼編碼先把0.1與0.3合併為0.4，再合併0.4與0.6，因此碼長為A 1位元、B與C 2位元。
某資訊源以機率0.6、0.3、0.1彼此獨立地輸出符號A、B、C，其熵約為1.30位元。以霍夫曼編碼對此資訊源編碼時，…
ZIP與gzip的Deflate方式，會把LZ77取代後的結果再以霍夫曼編碼進行編碼。
關於ZIP、gzip等所使用之LZ77方式的想法，下列何者正確？