哈夫曼編碼：簡潔之樹

演算法背後的故事：摩爾斯電碼問題

1836 年，塞繆爾·摩爾斯發明了一種透過電線發送資訊的代碼。他注意到 ‘E’ 是英語中最常見的字母，而 ‘Z’ 非常罕見。 所以他把 ‘E’ 設為一個點 (.)。把 ‘Z’ 設為一個複雜的序列 (--..)。 透過讓常見的東西變短，罕見的東西變長，他節省了時間。

1952 年，大衛·哈夫曼 (David Huffman) 從數學上形式化了這個想法。他證明，如果妳根據頻率構建一種特定類型的二叉樹，妳可以為任何數據集創建最優的無前綴編碼。

這就是 哈夫曼編碼。它是 ZIP 檔案如此小巧以及 JPEG 圖像加載如此之快的原因。

為什麼需要它？

• 檔案壓縮： ZIP, GZIP, PNG, JPEG, MP3 都在最後一步使用哈夫曼編碼（或其變體）來榨乾每一個位元。
• 節省頻寬： 在網路上發送更少的數據意味著更快的網站和更低的成本。

演算法是如何「思考」的

這個演算法是一個自底向上的構建者。

1. 統計頻率： ‘A’: 5, ‘B’: 9, ‘C’: 12, ‘D’: 13, ‘E’: 16, ‘F’: 45。
2. 優先佇列： 將所有字元放入一個按頻率排序的最小堆積中。
3. 合併：
   • 挑出兩個最小的節點（5 和 9）。
   • 將她們合併成一個新節點（總和：14）。
   • 把 14 放回堆積中。
4. 重複： 不斷合併兩個最小的，直到只剩下一個節點（根）。
5. 分配代碼：
   • 左分支 = ‘0’
   • 右分支 = ‘1’

最高頻的字元最終會靠近頂部（代碼短）。罕見的字元最終會深埋在底部（代碼長）。

工程決策：無前綴編碼

哈夫曼編碼的一個關鍵屬性是沒有代碼是另一個代碼的前綴。

• 如果 ‘E’ 是 0，而 ‘A’ 是 01，當解碼器看到 0 時會困惑……這是 ‘E’ 還是 ‘A’ 的開始？
• 在哈夫曼樹中，如果 0 被 ‘E’ 佔用了，那麼就沒有其他代碼會以 0 開頭。這允許在沒有分隔符的情況下進行即時、無歧義的解碼。

實作參考 (Python)

import heapq
from collections import Counter

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    # 優先佇列需要的比較運算符
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(text):
    # 1. 統計頻率
    freq = Counter(text)
    
    # 2. 構建最小堆積
    heap = [Node(char, f) for char, f in freq.items()]
    heapq.heapify(heap)
    
    # 3. 合併節點
    while len(heap) > 1:
        left = heapq.heappop(heap)
        right = heapq.heappop(heap)
        
        # 創建內部節點 (char 為空)
        merged = Node(None, left.freq + right.freq)
        merged.left = left
        merged.right = right
        
        heapq.heappush(heap, merged)
        
    return heap[0] # 根節點

def generate_codes(node, prefix="", code_map={}):
    if node:
        if node.char is not None:
            code_map[node.char] = prefix
        generate_codes(node.left, prefix + "0", code_map)
        generate_codes(node.right, prefix + "1", code_map)
    return code_map

# 使用範例
text = "BEEP BOOP BEER!"
root = build_huffman_tree(text)
codes = generate_codes(root)
print(f"編碼表: {codes}")
# 像 'E' 這樣的常用字母將擁有更短的二進位串

小結

哈夫曼編碼教會我們：平等是低效的。將每個字元視為平等（都用 8 位元）是在浪費空間。透過擁抱不平等——給予高頻者特權（短代碼），給予罕見者負擔（長代碼）——我們實現了最高效的系統。它提醒我們，背景（頻率）定義了價值。