某資訊源以機率0.4、0.3、0.2、0.1彼此獨立地輸出符號A、B、C、D，以霍夫曼編碼進行編碼。每個符號的平均碼長為下列何者？
- A約1.85位元
- B1.9位元
- C2位元
霍夫曼編碼計算工具
霍夫曼編碼是讓越常出現的符號使用越短的碼、使平均碼長最短的無失真壓縮方法。可由符號機率建立碼表，並與熵（理論下限）比較。
收藏與最近使用的工具只儲存在這個瀏覽器（localStorage）中。
計算結果
- 熵 H（每個符號）
- –
- 平均碼長 L（每個符號）
- –
- 效率（H ÷ L）
- –
- 固定長度碼的長度
- –
- 相對於固定長度的長度比
- –
- 整段文字的位元數
- –
合併的步驟
機率相同的節點，先取出輸入在前者。先合併哪一個會改變碼的形狀，但不會改變平均碼長。機率總和不為1時，會除以總和換算為機率。
以圖表檢視
其他輸入維持目前的值，只讓選擇的輸入在目前值的 1/4 到 4 倍之間變化時的結果。紅點是目前的值。
霍夫曼碼的建立方法
把每個符號當作以機率為權重的葉節點。從中選出機率最小的兩個，合併為機率相加的新節點，重複到只剩一個節點為止，就得到一棵樹；從根到葉的分支上標記的0與1，就是該符號的碼。在範例「3個符號」中，先把0.1與0.3合併為0.4，再把0.4與0.6合併，因此A的碼長為1位元，B與C為2位元。
熵與平均碼長
資訊源的熵 H = −Σ p log2 p，是每個符號所需位元數的理論下限。已知霍夫曼碼的平均碼長 L 滿足 H ≤ L < H + 1。在範例「3個符號」中，H ≒ 1.296 位元，L = 0.6 × 1 + 0.3 × 2 + 0.1 × 2 = 1.4 位元，效率約92.5%。所有機率都是2的負整數次方（1/2、1/4 …）時，L = H。
前綴碼與唯一解碼
霍夫曼碼是任何碼都不是其他碼開頭部分的前綴碼（即時碼），因此不需要分隔符號，只要從頭讀取位元串就能唯一解碼。依克拉夫特不等式，各碼長 l 的 2^(−l) 總和不超過1，而霍夫曼碼恰好等於1。
應用場合
霍夫曼編碼與其他方法搭配，用於 ZIP 與 PNG 所採用的 Deflate、JPEG 的熵編碼等。由於每個符號只能分配整數個位元，機率極度偏斜（如0.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 這種階梯狀的碼長更短。
某資訊源以機率0.6、0.3、0.1彼此獨立地輸出符號A、B、C，其熵約為1.30位元。以霍夫曼編碼對此資訊源編碼時，效率（熵 ÷ 平均碼長）最接近下列何者？
- A約65%
- B70%
- C約93%
某二元資訊源以機率0.8輸出0、以機率0.2輸出1，且彼此獨立。把每2個符號合成的00、01、10、11這4種分別視為1個符號，以霍夫曼編碼進行編碼。原本每個符號的平均碼長為下列何者？
- A約0.72位元
- B0.78位元
- C1位元
查看答案與解析
正確答案：B. 0.78位元
4種的機率為00 0.64、01與10 0.16、11 0.04。把0.04與0.16合併為0.2，0.2與0.16合併為0.36，最後與0.64合併，因此碼長為1、2、3、3位元，每2個符號的平均為 0.64 × 1 + 0.16 × 2 + 0.16 × 3 + 0.04 × 3 = 1.56 位元。換算成原本每個符號為 1.56 ÷ 2 = 0.78 位元。逐一編碼時只能對0與1各分配1位元，但合併編碼後，可以接近熵的約0.72位元。
常見問題
有機率相同的符號時，答案會改變嗎？
先合併哪個節點，可能改變碼的0與1排列，甚至個別符號的碼長；但無論怎麼選，平均碼長都是相同的最小值。因此考試多半問平均碼長，或在給定條件下的碼長。
比固定長度碼短多少？
符號有 n 個時，固定長度碼需要 ⌈log2 n⌉ 位元。機率越偏斜，霍夫曼碼越短；像範例「4個符號機率全部相同」這樣沒有偏斜時，與固定長度相同，都是2位元。
解碼需要什麼？
需要與傳送端相同的碼表（或樹）。若每份資料各自建立碼表，就要一併傳送碼表，或能由出現次數重建同一張表。像 Deflate 只傳送碼長，再依固定規則重建碼表。