哈夫曼编码：简洁之树

算法背后的故事：摩尔斯电码问题

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 位）是在浪费空间。通过拥抱不平等——给予高频者特权（短代码），给予罕见者负担（长代码）——我们实现了最高效的系统。它提醒我们，背景（频率）定义了价值。