哈夫曼树与哈夫曼编码：让数据变小的秘密

你有没有想过，电脑里的文字、图片、视频是怎么压缩的？比如一条短信“你今天吃什么”，如果每个汉字都用固定的16位二进制表示，那发100个字就要1600位。但如果根据每个字出现的频率，给常用字（比如“你”）一个很短的编码，给生僻字（比如“馕”）一个长编码，总长度就能大大减少。哈夫曼树就是专门用来干这件事的——它是一棵带权路径长度最短的二叉树，通过它生成的哈夫曼编码是一种可变长编码，能让数据压缩到最小。

为什么要用哈夫曼树？

想象一下期末考试后的语文老师：她要统计全班同学最喜欢的水果。假设全班50人，喜欢苹果的有20人，香蕉15人，西瓜10人，橘子5人。老师想给每种水果一个代号（用0和1组成），让所有同学的代号总长度最短。如果随便用固定长度编码，比如00、01、10、11，每位同学需要2位，总长度是50×2=100位。但如果给苹果（出现最多）用“0”，香蕉用“10”，西瓜用“110”，橘子用“111”，总长度就是20×1 + 15×2 + 10×3 + 5×3 = 20+30+30+15=95位，省了5位。哈夫曼树就能自动算出这种最优编码。

这里的“带权路径长度”是指：每个叶子节点（代表一个字符）的权值（出现次数）乘以从根到它的路径长度（边的数量），然后求和。哈夫曼树能让这个总和最小，所以也叫“最优二叉树”。

如何构造一个哈夫曼树？

构造过程像搭积木，每次挑选两块最轻的积木粘在一起。用贪心思想：每次从所有节点中挑出权值最小的两个，合并成一个新节点，新节点的权值等于两者之和，然后把它放回队伍里继续挑。重复直到只剩一个节点。这样，权值小的字符就会融合得早，离根远（编码长），权值大的字符留到最后，离根近（编码短）。

举个生活中的例子：管乐团的排练房有6个乐谱架，重量分别为5kg、9kg、12kg、13kg、16kg、45kg。老师让你把它们两两合并成一个大架子（重量相加），每次只能搬最轻的两个，最终合成一个最重的总架子。你会怎么搬？——这就是哈夫曼树的构造过程。最后你会发现，最重的那个45kg的架子（频率最高）被搬的次数最少（一次都没被合并），而最轻的5kg和9kg的架子被搬了多次（编码长）。

具体步骤：

把每个字符看作一个节点，权值是它的出现次数。
建一个最小堆（优先队列），把所有节点放进去。
重复以下操作直到堆里只剩一个节点：
- 弹出最小的两个节点，作为左孩子和右孩子。
- 创建一个新节点，权值为两者之和，左右孩子分别指向它们。
- 把新节点推入堆中。
最后剩下的节点就是根节点。

从树到编码：左0右1

哈夫曼树建好后，从根节点出发，走到叶子节点：向左走记一个“0”，向右走记一个“1”，这样走到每个叶子节点的路径就构成了该字符的哈夫曼编码。因为路径唯一，所以编码是前缀编码（任何一个编码都不是另一个编码的前缀），解码时不会产生歧义。

比如上面水果的例子，构造出的树可能是：苹果是根的直接左孩子（0），香蕉是根右孩子的左孩子（10），等等。

新手容易犯的错误

忘记初始化左右孩子：合并左右节点时，新节点的left和right必须指向原来的两个节点，否则树会断掉。
堆的比较函数写错：Python中自定义类要放在堆里，必须实现__lt__方法（小于比较），否则堆不知道如何排序。
递归生成编码时使用了可变默认参数：def generate_codes(node, prefix="", code_dict={})中的code_dict={}是一个全局唯一的字典，多次调用会累积之前的结果！应该在函数内部重新创建一个空字典，或者使用None作为默认值。
忽略空节点：递归时要先判断node is None，否则访问node.char会报错。
不理解前缀码：误以为“0”和“01”可以并存，但实际上它们会冲突，哈夫曼树保证不会出现这种情况。

完整可运行的代码示例

下面代码用heapq实现最小堆，构造哈夫曼树并输出每个字符的编码。注意：generate_codes函数使用了安全的默认参数方式（None）。

import heapq

class HuffmanNode:
    """哈夫曼树节点"""
    def __init__(self, char, freq):
        self.char = char      # 字符，叶子节点有值，内部节点为None
        self.freq = freq      # 频率（权值）
        self.left = None      # 左孩子
        self.right = None     # 右孩子

    # 定义小于比较，让堆能按频率排序
    def __lt__(self, other):
        return self.freq < other.freq

def build_huffman_tree(freq_dict):
    """
    根据频率字典构建哈夫曼树
    :param freq_dict: 字典，键为字符，值为频率，如 {'a':5, 'b':9, ...}
    :return: 树的根节点
    """
    heap = []  # 最小堆，存放 HuffmanNode 对象
    # 将每个字符作为一个节点放入堆
    for char, freq in freq_dict.items():
        heapq.heappush(heap, HuffmanNode(char, freq))

    # 不断合并权值最小的两个节点，直到只剩一个根节点
    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)  # 放回堆中

    return heap[0]  # 返回根节点

def generate_codes(node, prefix="", code_dict=None):
    """
    从根节点递归生成每个字符的哈夫曼编码
    :param node: 当前节点
    :param prefix: 当前路径编码字符串
    :param code_dict: 存储字符->编码的字典，首次调用传None
    :return: 编码字典
    """
    if code_dict is None:
        code_dict = {}  # 每次调用新创建一个字典，避免累积
    if node is None:
        return code_dict
    # 如果是叶子节点（有字符），记录编码
    if node.char is not None:
        code_dict[node.char] = prefix
    else:
        # 递归左子树，路径加'0'
        generate_codes(node.left, prefix + "0", code_dict)
        # 递归右子树，路径加'1'
        generate_codes(node.right, prefix + "1", code_dict)
    return code_dict

# ========== 示例：压缩字符序列 ==========
if __name__ == "__main__":
    # 假设我们要压缩字符串 "aaaaabbbbbcccccdddddeeeeeffffff"
    # 各字符频率：a:5, b:9, c:12, d:13, e:16, f:45
    freqs = {'a':5, 'b':9, 'c':12, 'd':13, 'e':16, 'f':45}
    
    root = build_huffman_tree(freqs)  # 构建哈夫曼树
    codes = generate_codes(root)      # 生成编码字典
    
    print("字符  频率  哈夫曼编码")
    print("--------------------")
    for char, freq in sorted(freqs.items(), key=lambda x: x[1], reverse=True):
        print(f"  {char}    {freq:2d}    {codes[char]}")
    
    # 计算压缩比示例
    original_bits = sum(freqs.values()) * 8  # 假设每个字符原本用8位
    encoded_bits = sum(freqs[char] * len(codes[char]) for char in freqs)
    print(f"\n原始总位数：{original_bits}")
    print(f"哈夫曼编码后总位数：{encoded_bits}")
    print(f"压缩率：{encoded_bits/original_bits*100:.1f}%")

输出结果：

字符  频率  哈夫曼编码
--------------------
  f    45    0
  e    16    100
  d    13    101
  c    12    110
  b     9    1110
  a     5    1111

原始总位数：800
哈夫曼编码后总位数：224
压缩率：28.0%

可以看到，频率最高的f只用了1位（0），而频率最低的a用了4位（1111），整体节省了72%的空间！

哈夫曼树与哈夫曼编码