為什麼貪心策略是最優的
霍夫曼演算法是一個貪心演算法：在每一步，它做出局部最優選擇（合併兩個成本最低的節點），而不向前看。貪心演算法並非總是全局最優的 — 但在這裡是的。
最優性論證
假設編碼C的平均長度最小為L。考慮兩個概率最低的符號，比如p_a和p_b。在任何最優編碼中，這兩個符號必須在樹的最深層級中作為兄弟葉子出現。為什麼？
如果它們沒有共享父節點，你可以將較深的符號與較短的編碼交換 — 減少L。因此最深的葉子必須是最不可能的符號。
現在，如果你將a和b合併成一個元符號ab（p_ab = p_a + p_b），縮減字母表上的任何最優編碼減去一個符號恰好是簡化問題上的霍夫曼編碼。歸納法完成論證。
幾何視圖
霍夫曼演算法從下往上構造二元樹，將最不可能的符號放在最大深度。這最小化Σ p_i · depth(i) = L。
等價的視圖：你正在為樹葉分配標籤以最小化加權路徑長度，其中每個葉子的權重是其概率。
執行貪心步驟
概率：p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1。和 = 1.0 ✓
第1步：最低的兩個：C(0.2), D(0.1)。合併 → CD(0.3)。列表：A(0.4), B(0.3), CD(0.3)。
第2步：最低的兩個：B(0.3), CD(0.3)（並列 — 任一有效）。合併 → BCD(0.6)。列表：A(0.4), BCD(0.6)。
第3步：合併A(0.4), BCD(0.6) → root(1.0)。分配A=0, BCD=1。
回溯： BCD → B=10 (l=2), CD=11 → C=110 (l=3), D=111 (l=3)。
L = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4+0.6+0.6+0.3 = 1.9位。
編碼長度的變異數
兩個霍夫曼編碼可能達到相同的L但有不同的編碼長度分佈。編碼長度的變異數衡量這種傳播：
Var(l) = E[l²] − (E[l])²
其中E[l] = L（平均編碼長度）和E[l²] = Σ p_i · l_i²。
為什麼變異數很重要：
1. 緩衝區需求。 在實時解碼中，每個符號需要可變數量的位。高變異數意味著一些符號需要許多位 — 你需要更大的輸入緩衝區以保證你總是可以讀取完整符號。
2. 解碼延遲。 高變異數編碼有長的最壞情況解碼路徑。低變異數（灌木狀）編碼更緊密地限制最壞情況。
3. 魯棒性。 高變異數編碼中丟失的位會造成更多同步化損害，因為長編碼詞必須完全重新讀取。
漢明的建議：當存在多個有效霍夫曼編碼時（並列分解選擇），優先選擇變異數較低的 — 灌木狀樹。
計算兩棵樹的變異數
使用p(A)=0.4, p(B)=0.3, p(C)=0.2, p(D)=0.1和編碼A=0, B=10, C=110, D=111：
E[l] = L = 1.9
E[l²] = 0.4·1² + 0.3·2² + 0.2·3² + 0.1·3² = 0.4+1.2+1.8+0.9 = 4.3
Var = 4.3 − 1.9² = 4.3 − 3.61 = 0.69
3-符號霍夫曼編碼端到端
完整的端到端例子：構造霍夫曼編碼、計算L、計算H、驗證L ≥ H、計算Var。
源：p(X)=0.6, p(Y)=0.3, p(Z)=0.1。
霍夫曼構造：
第1步：排序：X(0.6), Y(0.3), Z(0.1)。最低的兩個：Y(0.3), Z(0.1)。
合併 → YZ(0.4)。列表：X(0.6), YZ(0.4)。
第2步：合併X(0.6), YZ(0.4) → root(1.0)。分配X=0, YZ=1。
YZ → Y=10, Z=11。
編碼：X=0 (l=1), Y=10 (l=2), Z=11 (l=2)。
L = 0.6·1 + 0.3·2 + 0.1·2 = 0.6 + 0.6 + 0.2 = 1.4位。
熵： H = −0.6·log₂(0.6) − 0.3·log₂(0.3) − 0.1·log₂(0.1)
log₂(0.6) ≈ −0.737, log₂(0.3) ≈ −1.737, log₂(0.1) ≈ −3.322
H = 0.6·0.737 + 0.3·1.737 + 0.1·3.322 = 0.442 + 0.521 + 0.332 = 1.295位。
L = 1.4 ≥ H = 1.295 ✓。L/H = 1.4/1.295 ≈ 1.081。熵上方8.1%。
變異數： E[l²] = 0.6·1 + 0.3·4 + 0.1·4 = 0.6+1.2+0.4 = 2.2。Var = 2.2 − 1.4² = 2.2 − 1.96 = 0.24。
輪到你：完整的管道
參考log₂值：log₂(0.5)=−1.000, log₂(0.25)=−2.000, log₂(0.125)=−3.000, log₂(0.375)≈−1.415, log₂(0.625)≈−0.678。