Huffman 如何構建最優編碼
Hamming 將 Huffman 編碼呈現為一種貪心演算法，該演算法構建最小平均長度的無前綴編碼。關鍵想法：自下而上構建樹，始終合併兩個機率最低的符號。
前向傳遞（構建）
1. 將所有符號按機率從高到低排序。
2. 取兩個機率最低的符號。將它們合併為一個新的元符號，其機率 = 兩者之和。
3. 將元符號插入其排序位置。
4. 重複直到只剩兩個符號。
5. 為剩餘的兩個符號分配 0 和 1。
後向傳遞（分配編碼）
逆向撤銷合併：在每次分割處，被合併的兩個符號接收與其組合父符號相同的前綴位，加上額外的 0（一個子符號）或 1（另一個子符號）。0/1 分配是任意的——兩者都有效。
為什麼這是最優的：如果任何其他編碼的平均長度 L' 更小，應用相同的前向化簡最終會產生兩個符號，其平均長度小於 1 比特——對於 2 符號編碼來說是不可能的。矛盾。
追蹤演算法
Hamming 的示例：四個符號 A、B、C、D，機率分別為 p(A)=0.5、p(B)=0.25、p(C)=0.125、p(D)=0.125。
前向傳遞：
步驟 1：排序：A(0.5)、B(0.25)、C(0.125)、D(0.125)。最低的兩個：C、D。
步驟 2：合併 CD，機率=0.25。新列表：A(0.5)、B(0.25)、CD(0.25)。
步驟 3：最低的兩個：B(0.25)、CD(0.25)。合併 BCD，機率=0.5。
步驟 4：剩餘兩個符號：A(0.5)、BCD(0.5)。分配 A=0、BCD=1。
後向傳遞：
BCD → B 得到 10、CD 得到 11。CD → C 得到 110、D 得到 111。
最終編碼：A=0 (l=1)、B=10 (l=2)、C=110 (l=3)、D=111 (l=3)。
L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75 比特。
多個有效的 Huffman 編碼
Hamming 注意到非唯一性的兩個來源：
1. 任意的 0/1 分配。在每次分割處，您可以給任一子節點分配 0。交換整個編碼中的 0 和 1 會產生不同的編碼，其平均長度 L 相同。
2. 平手打破。當兩個節點機率相等時，任一個都可以被放置在更高的位置（先合併）。不同的平手打破選擇可以產生結構不同的樹——'長'與'茂密'——具有相同的 L 但不同的編碼長度分佈。
長樹與茂密樹
長樹（偏斜）：每個深度級別一個符號（Fibonacci 類的結構）。編碼長度差異很大：一個符號獲得短編碼，其他符號級聯為更長的編碼。
茂密樹（平衡）：符號均勻分佈在深度級別。編碼長度聚集在平均值附近。較低的方差。
Hamming 的建議：在有選擇的情況下，更喜歡茂密樹。相同的 L，但編碼長度的方差更小 → 更統一的解碼時間 → 實時應用中所需的緩衝區更小。
計算編碼長度方差
編碼長度方差：Var = E[l²] − (E[l])²
對於編碼 {A=0 l=1、B=10 l=2、C=110 l=3、D=111 l=3}，機率為 p=[0.5, 0.25, 0.125, 0.125]：
E[l] = L = 1.75
E[l²] = 0.5·1² + 0.25·2² + 0.125·3² + 0.125·3² = 0.5 + 1.0 + 1.125 + 1.125 = 3.75
Var = 3.75 − 1.75² = 3.75 − 3.0625 = 0.6875
等機率符號的替代茂密編碼使用所有 2 長度編碼：L=2、Var=0。
壓縮收益 vs 符號分佈
Hamming 的規則：Huffman 編碼只有在符號機率差異很大時才值得。
等機率。如果所有 2^k 個符號機率相等，均為 1/2^k，Huffman 產生分塊編碼：每個符號獲得長度 k。L = H = k。與簡單分塊編碼相比沒有收益。
偏斜的機率。如果一個符號佔主導（p >> 1/2^k 對其他人），Huffman 為其分配一個非常短的編碼（長度 1 或 2），大幅降低 L。
逗號編碼（Hamming 的術語）。當每個機率超過剩餘總數的 2/3 時，Huffman 自然產生：p(s1)→0、p(s2)→10、p(s3)→110、...，直到末尾的兩個等長編碼。這是一個'逗號編碼'：1 後面的尾隨 0 充當逗號。
Hamming 指出：現實世界的數據壓縮（備份、文件歸檔）當源具有偏斜機率時可以減少超過一半的存儲——英文文本是主要例子。
Huffman 與分塊編碼：數值比較
Hamming 的第二個例子：p(s1)=1/3、p(s2)=1/5、p(s3)=1/6、p(s4)=1/10、p(s5)=1/12、p(s6)=1/20、p(s7)=1/30、p(s8)=1/30。
分塊編碼：8 個符號 → 各 3 位 → L_block = 3。
Hamming 計算 Huffman 編碼並報告 L_Huffman ≈ 2.58 比特。
節省：(3 − 2.58)/3 ≈ 14% 相對分塊編碼的壓縮。
當符號機率差異很大時（此處 1/3 vs 1/30，比例 10:1），變長編碼大幅節省。
自編譯程序
Hamming 在第 11 章結束時提出了一個引人注目的想法：Huffman 編碼器可以對自己進行編碼。解碼樹（告訴解碼器如何讀取壓縮信息）與壓縮數據一起傳輸。接收器不需要先驗知道編碼。
編碼器：對數據進行採樣、估計機率、構建 Huffman 編碼、將解碼樹編碼為頭部、然後編碼數據。
解碼器：讀取頭部以重建樹，然後使用它解碼數據。
Hamming 的觀點：整個管道可以作為庫函數運行，無需人工參與。您調用它，它自動壓縮和解壓縮。現代歸檔格式（ZIP、gzip、bzip2）實施完全相同的模式。
更深層的原則：智能在演算法中，而不在固定的編碼表中。該演算法適應它接收的任何數據。這是 Hamming 在所有偉大工程系統中看到的模式：適應性內置其中，而不是後來添加。