5.2 Huffman編碼#

概念說明#

Huffman 編碼（David Huffman, 1952）是已知機率下的最佳前綴碼演算法，思路是貪婪法（見《演算法》書的貪婪法一章）的經典範例：反覆取出機率最小的兩個符號合併，直到只剩一棵樹。

證明最佳性的關鍵引理：在最佳前綴碼樹中，機率最小的兩個符號必是深度最大的一對兄弟葉（否則把深的葉子換下來可得更小的平均長度）。於是「每次合併兩個最小」不會損失任何最佳解，貪婪成立。

演算法流程：每個符號是一棵樹（權重 = 頻率），放入優先佇列；反覆取兩棵權重最小的合併成新節點（權重相加），新節點放回佇列；最後剩下的樹就是 Huffman 樹。左 0 右 1，根到每個葉的路徑即該符號的碼。高頻符號合併得晚、深度淺、碼短；低頻符號深、碼長——平均碼長最小。

實務議題：

如何存碼表？ 解碼器需要碼表。常見做法：檔頭存「符號→頻率」（解碼端重建同一棵樹）或直接存樹結構；總開銷必須算進壓縮結果，所以小檔案壓縮比可能為負（越壓越大）。
碼的表示：碼長可達 |Σ|−1（最壞 Fibonacci 分布），要用位元串（bitarray）而非字串。
應用：DEFLATE（zip/gzip/PNG）的兩層設計中，第二層就是 Huffman（見 6.3 節）；JPEG、MP3 也都用它。
極限：平均碼長 L 滿足 H ≤ L < H+1；每符號至少 1 位元（二元樹的限制），當某符號機率 > 0.5 時 Huffman 會顯著浪費，這正是算術編碼（5.3 節）出場的理由。

演算法步驟#

統計頻率，建葉節點，全部推入以頻率為鍵的最小堆。
while 堆中樹數 ≥ 2：彈出兩棵最小的 a、b，合併為節點（權 a+b，左 a 右 b），推回。
堆剩一棵即 Huffman 樹；DFS 標記路徑為各符號的碼。
編碼：查表串接各符號碼，寫成位元流；檔頭記錄頻率表與原始長度。
解碼：讀頻率表重建同一棵樹；從根開始，依位元 0/1 走樹，落到葉子即輸出符號並回到根，直到讀完所有符號。

Python 程式碼範例#

import heapq
from collections import Counter
from collections import namedtuple

Node = namedtuple("Node", ["freq", "sym", "left", "right"])

def build_tree(text):
    cnt = Counter(text)
    heap = [Node(f, s, None, None) for s, f in cnt.items()]
    heapq.heapify(heap)
    if len(heap) == 1:                       # 只有一種符號
        heap[0] = Node(heap[0].freq, heap[0].sym, None, None)
    while len(heap) > 1:
        a, b = heapq.heappop(heap), heapq.heappop(heap)
        heapq.heappush(heap, Node(a.freq + b.freq, None, a, b))
    return heap[0]

def build_codes(root):
    codes = {}
    def dfs(node, path):
        if node.sym is not None:
            codes[node.sym] = path or "0"    # 單符號特例
            return
        dfs(node.left, path + "0")
        dfs(node.right, path + "1")
    dfs(root, "")
    return codes

def encode(text):
    root = build_tree(text)
    codes = build_codes(root)
    bits = "".join(codes[c] for c in text)
    return codes, bits

def decode(codes, bits):
    inv = {v: k for k, v in codes.items()}
    out, buf = [], ""
    for b in bits:
        buf += b
        if buf in inv:
            out.append(inv[buf]); buf = ""
    return "".join(out)

text = "abracadabra abracadabra abracadabra"
codes, bits = encode(text)
total = len(codes.__str__()) + len(bits) // 8
print("原始位元數:", len(text) * 8)
print("壓縮位元數:", len(bits))
print("熵下限:", sum(f/len(text) * -__import__('math').log2(f/len(text))
                     for f in Counter(text).values()) * len(text))
print("碼表:", dict(sorted(codes.items(), key=lambda x: len(x[1]))))
assert decode(codes, bits) == text

複雜度分析#

建樹：|Σ| 個符號，堆操作 O(log|Σ|) × 合併 (|Σ|−1) 次 = O(|Σ| log|Σ|)；兩堆法（頻率排序後用兩個 FIFO 佇列）可到 O(|Σ|)。
編碼：O(n)；解碼：每符號走樹深 O(L̄) 步，共 O(n L̄)，可用碼表查表法加速。
空間：樹 O(|Σ|)、碼表 O(|Σ|×L̄)。
效果量尺：壓縮率 = 壓縮後/原始；理論下界 = H/8。英文文字一階 Huffman 約可到 4.3～4.5 位元/字元（≈55%），離英文真實極限（含上下文 < 2 位元）仍遠——上下文建模是字典法與算術編碼的主場。

練習#

修改程式，讓 encode 連同檔頭頻率表一起輸出位元組序列，再寫 decode_file 解回；測試 100 位元組以下的極小檔案，驗證「壓縮反而變大」的現象並計算損耗。
實作規範式 Huffman 碼（canonical Huffman）：只存各符號的碼長（依長度、符號序重排碼），大幅縮小檔頭；這正是 DEFLATE 使用的形式。
構造一個機率分布（如 {0.9, 0.1} 或 Fibonacci 頻率），計算其熵與 Huffman 平均碼長，展示「每符號至少 1 位元」造成的浪費；再用 5.3 節的算術編碼壓同樣資料，比較結果。