哈夫曼编码：数据压缩的经典算法

2025年1月26日星期日 · simons · 本文共 729 个字，预计需要阅读 2 分钟

哈夫曼编码：数据压缩的经典算法

今天遇到一个有趣的问题：一个100MB的日志文件，需要实时传输，但带宽只有 10MB。很多人二话不说就上 gzip，但你真的理解压缩算法的原理吗？

什么是哈夫曼编码？

本质上，哈夫曼编码是一种变长编码方案。它的核心思想是：出现频率高的字符用短编码，频率低的用长编码。

# 一个简单的例子
text = "AAAAABBBCC"  # 原始数据
# 普通编码：每个字符占8位
# A: 01000001 (8位) × 5 = 40位
# B: 01000010 (8位) × 3 = 24位
# C: 01000011 (8位) × 2 = 16位
# 总共：80位

# 哈夫曼编码
# A: 0 (1位) × 5 = 5位
# B: 10 (2位) × 3 = 6位
# C: 11 (2位) × 2 = 4位
# 总共：15位

为什么需要哈夫曼编码？

看看其他编码方案的问题：

定长编码：空间浪费
简单变长编码：可能产生歧义
字典编码：需要存储字典

哈夫曼编码解决了这些问题：

保证无歧义解码
平均码长最短
编解码效率高

算法原理

class Node:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

def build_huffman_tree(text):
    # 统计频率
    freq = {}
    for char in text:
        freq[char] = freq.get(char, 0) + 1

    # 构建优先队列
    nodes = [Node(char, f) for char, f in freq.items()]
    while len(nodes) > 1:
        # 取出频率最小的两个节点
        nodes.sort(key=lambda x: x.freq)
        left = nodes.pop(0)
        right = nodes.pop(0)

        # 创建新节点
        parent = Node(None, left.freq + right.freq)
        parent.left = left
        parent.right = right
        nodes.append(parent)

    return nodes[0]  # 返回根节点

实战经验

最常见的坑：

内存问题

# 错误做法：一次性读入
text = file.read()  # 内存爆炸

# 正确做法：分块处理
CHUNK_SIZE = 1024 * 1024  # 1MB
while chunk := file.read(CHUNK_SIZE):
    process_chunk(chunk)

性能优化

# 优化前：使用列表排序
nodes.sort(key=lambda x: x.freq)  # O(nlogn)

# 优化后：使用堆
import heapq
heap = []
for char, freq in freq.items():
    heapq.heappush(heap, (freq, Node(char, freq)))