3. 哈夫曼编码：从字符频率到最优前缀码的贪心算法
哈夫曼编码，说白了就是给数据里的每个字符重新分配一套二进制编号。这套编号有个特点：出现越频繁的字符，编号越短。你想想看，这就像给公司里最忙的几个人配个快捷键，其他人用长一点的指令，整体效率就上来了。
我第一次接触这个算法是在做嵌入式通信协议的时候。那时候要传传感器数据，带宽窄得可怜，每省一个比特都是胜利。嗯，哈夫曼编码帮我省了将近 30% 的流量，从那以后我就再也没小看过这个算法。
3.1 核心思想：用频率换长度
哈夫曼编码的本质，就是用频率信息来指导编码分配。高频字符给短码，低频字符给长码。这样整体数据量就能降下来。
但这里有个坑：你怎么保证解码的时候不会产生歧义？比如 A 的编码是 0，B 的编码是 01，那收到 01 的时候，到底是 A 后面跟了个 1，还是直接就是 B？
哈夫曼的解法很巧妙——前缀码。任何字符的编码，都不能是另一个字符编码的前缀。这样解码器从左往右读，碰到一个匹配就立刻确定，不会犹豫。
前缀码的核心约束：编码集合中，任意一个码字都不是另一个码字的前缀。
满足这个条件，解码就是确定性的，不需要回溯。
3.2 构建哈夫曼树：贪心策略的经典案例
构建哈夫曼树的过程，其实就是贪心算法的教科书级演示。每一步都选当前频率最小的两个节点合并，直到只剩一棵树。
具体步骤是这样的：
- 统计每个字符的出现频率，每个字符作为一个叶子节点。
- 从所有节点中选出频率最小的两个节点。
- 创建一个新节点，频率等于这两个节点之和，左右子节点分别指向它们。
- 把新节点放回集合，重复步骤 2-3，直到只剩一个节点。
- 从根节点出发，左分支标 0，右分支标 1，路径上的 0/1 序列就是该字符的编码。
我习惯把这个过程想象成「从下往上搭树」。叶子在最底层，越往上走，节点代表的频率越大，最后根节点就是总频率。
个人经验：我在做文件压缩工具时，发现一个容易被忽略的细节——频率统计的精度。如果统计窗口太小，频率分布不稳定，生成的哈夫曼树反而会膨胀数据。建议至少统计 1KB 以上的数据再做编码。
3.3 一个完整的例子
假设我们要编码一段文本，里面只有 5 个字符：A、B、C、D、E。频率如下：
| 字符 | A | B | C | D | E |
|---|---|---|---|---|---|
| 频率 | 5 | 9 | 12 | 13 | 16 |
我们一步步来：
- 初始节点：A(5), B(9), C(12), D(13), E(16)
- 选最小的两个：A(5) 和 B(9)，合并成新节点 N1(14)
- 剩余节点：C(12), D(13), E(16), N1(14)
- 选最小的两个：C(12) 和 D(13)，合并成 N2(25)
- 剩余节点：E(16), N1(14), N2(25)
- 选最小的两个：E(16) 和 N1(14)，合并成 N3(30)
- 剩余节点：N2(25), N3(30)
- 最后合并：N2(25) 和 N3(30)，得到根节点 Root(55)
最终得到的编码：
| 字符 | 频率 | 哈夫曼编码 | 编码长度 |
|---|---|---|---|
| A | 5 | 110 | 3 |
| B | 9 | 111 | 3 |
| C | 12 | 00 | 2 |
| D | 13 | 01 | 2 |
| E | 16 | 10 | 2 |
你看，频率最高的 E 只用了 2 位，而频率最低的 A 和 B 用了 3 位。整体平均码长 = (5×3 + 9×3 + 12×2 + 13×2 + 16×2) / 55 ≈ 2.25 位。如果用固定长度编码，5 个字符至少需要 3 位，平均码长就是 3 位。省了将近 25%。
我曾经踩过的坑：有一次我直接用频率排序后手动分配编码，结果生成了非前缀码，解码时全乱了。后来老老实实画了哈夫曼树，才意识到「左 0 右 1」的路径分配是保证前缀性的关键。千万别跳过建树这一步。
3.4 哈夫曼编码的完整流程
下面这张图展示了从原始数据到压缩数据的完整流程：
3.5 代码实现：从理论到实践
下面是我写的一个简化版哈夫曼编码实现。我习惯用优先队列来维护最小频率节点，这样每次取最小两个的时间复杂度是 O(log n)。
import heapq
from collections import Counter
class HuffmanNode:
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_map = Counter(text)
# 2. 构建优先队列
heap = [HuffmanNode(char, freq) for char, freq in freq_map.items()]
heapq.heapify(heap)
# 3. 贪心合并
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = HuffmanNode(None, left.freq + right.freq)
merged.left = left
merged.right = right
heapq.heappush(heap, merged)
# 4. 生成编码表
codes = {}
def generate_codes(node, code=""):
if node is None:
return
if node.char is not None:
codes[node.char] = code
return
generate_codes(node.left, code + "0")
generate_codes(node.right, code + "1")
root = heap[0] if heap else None
if root:
generate_codes(root)
return codes
# 使用示例
text = "AABBBCCCDDDDEEEEE"
codes = build_huffman_tree(text)
print("编码表:", codes)
# 编码
encoded = ''.join(codes[ch] for ch in text)
print("编码结果:", encoded)
# 解码
reverse_codes = {v: k for k, v in codes.items()}
decoded = ""
current = ""
for bit in encoded:
current += bit
if current in reverse_codes:
decoded += reverse_codes[current]
current = ""
print("解码结果:", decoded)我建议：实际项目中，优先队列的实现可以用 heapq，它比手动维护列表快得多。如果数据量特别大（比如上百万字符），可以考虑用 array 模块来存储频率，减少内存开销。
3.6 哈夫曼编码的优缺点
| 优点 | 缺点 |
|---|---|
| 压缩率接近理论最优（香农熵） | 需要两遍扫描：第一遍统计频率，第二遍编码 |
| 解码速度快，不需要查表 | 编码表需要随数据一起传输，增加开销 |
| 实现简单，算法稳定 | 对频率分布敏感，均匀分布时效果差 |
| 无损压缩，信息完全保留 | 无法处理流式数据（需要先知道全局频率） |
我曾经踩过的坑：有一次我直接用哈夫曼编码压缩一个已经压缩过的文件，结果文件反而变大了。后来才意识到，已经压缩过的数据频率分布很均匀，哈夫曼编码在这种场景下基本不生效。所以用之前先看看数据的频率分布，别盲目上。
3.7 实际应用场景
哈夫曼编码不是银弹，但在某些场景下特别好用：
- 文本压缩：英文文本中字母频率差异大，压缩效果明显
- 图像压缩：JPEG 在 DCT 变换后，对量化系数做哈夫曼编码
- 通信协议：我在做物联网项目时，用哈夫曼编码压缩传感器数据，省了不少流量费
- 文件归档：ZIP 格式中，Deflate 算法就用到了哈夫曼编码
嗯，哈夫曼编码的核心就这些。它不复杂，但很优雅。你想想看，一个 1952 年提出的算法，到现在还在各种压缩工具里活跃着，这就是经典的力量。