Huffman Coding霍夫曼編碼
用堆積每次合併最小的兩個頻率。
用在：zip、JPEG、MP3 的熵編碼階段
01為什麼需要它
一份英文文件裡 e 出現幾萬次，z 只出現幾次，但 ASCII 一律用 8 位元存每個字。常見的字和罕見的字花一樣的空間，明顯浪費。
為什麼用它讓常見字元用短編碼、罕見字元用長編碼，總位元數就會下降。霍夫曼編碼每次把頻率最低的兩個合併成一棵樹，樹上的路徑就是編碼。它是 DEFLATE（zip、gzip、PNG）最後一個階段用的方法，而且可以證明在「每個字元一個編碼」的前提下是最短的。
影像和聲音經過轉換和量化後，會得到一大堆數字，其中 0 和小數字特別多，大數字很少。要把這些數字存成檔案，越小越好。
為什麼用它這正是頻率極度不均的資料，霍夫曼編碼在這種分布上壓縮率最好。JPEG 的熵編碼階段、MP3 的位元流打包都用它。有損壓縮的「有損」發生在量化，霍夫曼這一步是無損的。
變長編碼有個陷阱：如果 a 是 0、b 是 01，讀到 0 的時候不知道該停還是該繼續。加分隔符會把省下的空間吃回去。
為什麼用它霍夫曼樹的字元全部在葉節點，所以沒有任何編碼是另一個編碼的前綴，這叫前綴碼。解碼時從根往下走，走到葉節點就輸出，不需要分隔符。貪婪合併的方式自然保證了這個性質。
看到這些關鍵字就想到它：壓縮、變長編碼、頻率越高編碼越短、前綴碼、每次合併最小的兩個、最小堆積建樹。
02核心概念
霍夫曼編碼要解的問題是：給每個字元的出現頻率，設計一組前綴碼（沒有編碼是另一個的前綴），讓「頻率 × 編碼長度」的總和最小。任何前綴碼都對應一棵二元樹，字元在葉節點，從根走到葉的路徑（左 0 右 1）就是編碼，編碼長度等於葉的深度。所以問題變成：怎麼排葉節點，讓加權深度總和最小。
貪婪做法：把每個字元當成一個節點放進最小堆積，每次取出頻率最小的兩個，合併成一個頻率為兩者之和的新節點放回去，直到剩一個。頻率越小的節點越早被合併，就被推到樹的越深處，拿到越長的編碼；頻率最大的通常在最後才合併，深度最淺。n 種字元做 n − 1 次合併，每次堆積操作 O(log n)，總共 O(n log n)。
為什麼是最佳？交換論證分兩步。第一，頻率最小的兩個字元 x、y 一定可以放在最深的一層當兄弟：若最佳樹裡最深的兄弟是別的字元 a、b，把 a、b 和 x、y 對調，深的位置換成頻率更小的，加權總和不會變大。第二，把 x、y 合併成一個頻率 x + y 的節點後，剩下的問題是少一個字元的同型問題，它的最佳樹接上 x、y 就是原問題的最佳樹。兩步合起來就是貪婪選擇性質加最佳子結構。
注意幾件事。頻率相同時合併順序不唯一，所以霍夫曼碼不唯一，但總位元數一樣。只有一種字元時樹只有根，要特別給它編碼 0。解碼端需要同一棵樹，所以檔案裡要存編碼表（DEFLATE 用一套固定規則把表本身也壓得很小）。霍夫曼是「每個符號整數位元」下的最佳解，若允許每個符號花非整數個位元，算術編碼和 ANS 能再壓得更緊，xz 的 LZMA（區間編碼）和 zstd 的 FSE（ANS 的一種）走的就是這個方向。
03演算法步驟
- 1統計每個字元的頻率，每個字元建一個葉節點，全部放進最小堆積（依頻率）。
- 2堆積裡多於一個節點時：取出頻率最小的兩個 a、b。
- 3建新節點，頻率
a.freq + b.freq，左子 a、右子 b，放回堆積。重複直到剩一個，它就是根。 - 4從根走遍整棵樹，左 0 右 1，走到葉節點就記下該字元的編碼。
- 5編碼：逐字元查表串接。解碼：從根出發，讀 0 往左、讀 1 往右，碰到葉節點輸出並回到根。
04互動示範
「abracadabra」有 5 種字元。每一步先標出堆積裡頻率最小的兩個（黃色），下一步把它們合併成新節點（藍色）放回堆積。建完樹後從根往下走就得到編碼表，最後比較總位元數：霍夫曼 23 位元，固定 3 位元編碼要 33。
| 字元 | 次數 | 編碼 | 位元 |
|---|---|---|---|
| a | 5 | ? | ? |
| b | 2 | ? | ? |
| r | 2 | ? | ? |
| c | 1 | ? | ? |
| d | 1 | ? | ? |
| 合計 | 11 | 固定 3 位元：33 | ? |
05程式碼
用堆積建樹、走樹產生編碼表，加上編碼與解碼。Python 版用 tuple 表示內部節點，C++ 版用指標。
import heapq
from collections import Counter
def huffman_codes(text):
"""回傳 {字元: 編碼}。堆積裡放 (頻率, 序號, 節點)，序號讓 tuple 永遠比得出大小。"""
freq = Counter(text)
heap = []
for i, (ch, f) in enumerate(freq.items()):
heapq.heappush(heap, (f, i, ch)) # 葉節點直接用字元代表
seq = len(freq)
while len(heap) > 1:
f1, _, a = heapq.heappop(heap) # 頻率最小的兩個
f2, _, b = heapq.heappop(heap)
heapq.heappush(heap, (f1 + f2, seq, (a, b))) # 內部節點用 (左, 右)
seq += 1
root = heap[0][2]
codes = {}
def walk(node, code):
if isinstance(node, str): # 葉節點
codes[node] = code or "0" # 只有一種字元時給 "0"
else:
walk(node[0], code + "0")
walk(node[1], code + "1")
walk(root, "")
return codes
def encode(text, codes):
return "".join(codes[ch] for ch in text)
def decode(bits, codes):
rev = {v: k for k, v in codes.items()} # 前綴碼：邊讀邊比對，不需要分隔符
out, cur = [], ""
for b in bits:
cur += b
if cur in rev:
out.append(rev[cur])
cur = ""
return "".join(out)
if __name__ == "__main__":
text = "abracadabra"
codes = huffman_codes(text)
bits = encode(text, codes)
print(codes) # a 是 1 位元，c、d 是 3 位元
print(len(bits), "位元，固定長度要", len(text) * 3) # 23 位元，固定長度要 33
print(decode(bits, codes) == text) # True06練習題
- LeetCode 1046Last Stone Weight（每次取最大兩個）Easy
- LeetCode 1167Minimum Cost to Connect Sticks（付費題，和霍夫曼一模一樣）Medium
- LeetCode 347Top K Frequent Elements（統計頻率加堆積）Medium
- LeetCode 767Reorganize String（按頻率用堆積排）Medium
- LeetCode 1000Minimum Cost to Merge Stones（限制相鄰時貪婪失效，要區間 DP）Hard