Python哈夫曼编码

哈夫曼编码：让文件变小的“聪明快递员”

你有没有想过，为什么电脑里的文本文件可以变得很小？其中一个秘密就是一种叫做“哈夫曼编码”的技术。它像一位聪明的快递员，把经常出现的物品放在小盒子里，很少出现的物品用大盒子装，这样总共用的纸箱就更少。哈夫曼编码是一种无损压缩算法，也就是说压缩后的数据可以完全还原成原来的样子，不会丢失任何信息。它被用在很多地方，比如 ZIP 压缩包、MP3 音乐、JPEG 图片背后都有它的身影。

生活中的比喻

假设你要给全班同学发姓名贴纸。有的同学名字很短，比如“王二”，有的名字很长，比如“欧阳德华”。如果每个名字都固定写10个字，那么“王二”就浪费了很多空白。哈夫曼编码的做法是：给最常见的名字（比如“小明”）用一个很短的编号（比如“0”），给不常见的名字用一个长一点的编号（比如“110”）。这样整体看来，写名字用的字数就大大减少了。

再举一个例子：你每天上学要带水杯、饭盒、一本书。水杯你最常带（每天），饭盒偶尔带（每周一次），书很少带（每月一次）。如果用普通的书包，每个物品都占一个固定的大格子，很浪费空间。哈夫曼编码就像给物品分配合适大小的格子——水杯用一个很小的格子，饭盒用中等格子，书用大格子。这样书包就能装更多东西。

什么是哈夫曼树？

哈夫曼编码的核心是一棵哈夫曼树（也叫最优二叉树）。这棵树的特点是：从根节点到每个字符叶子节点的路径长度乘以字符出现频率的总和最小。简单说，出现越多的字符，路径越短，编码就越短。

构建哈夫曼树的步骤（分要点）

统计频率：数一数每个字符出现了几次。
- 例如字符串 "hello world"，空格也算一个字符。统计结果：h:1, e:1, l:3, o:2, 空格:1, w:1, r:1, d:1。
创建节点：每个字符变成一个树节点，节点里存着字符和它出现的频率。
不断合并：每次从节点中挑出频率最小的两个节点，把它们合并成一个新节点（频率相加），新节点作为它们的爸爸（父节点）。把这两个节点从列表里删除，把新节点加进去。
重复直到只剩一个节点：这个节点就是哈夫曼树的根节点。
生成编码：从根节点出发，往左走写 0，往右走写 1，走到叶子节点时，经过的 0 和 1 串就是该字符的编码。

为什么这样能压缩数据？

因为频率高的字符编码短，频率低的编码长。假设原文有100个字符，如果每个字符用固定8位二进制表示（如ASCII码），需要 100×8=800 位。如果用哈夫曼编码，高频字符可能只用1~~3位，低频字符用5~~6位，总位数可能只有400~500位，大大减少了。

新手容易犯的错误

忘记处理空格和标点符号：统计频率时，空格、换行、标点也要算进去，否则解压时会丢失信息。
合并时选错节点：必须每次都选频率最小的两个。如果用普通列表排序，每次合并后要重新排序，效率低。正确做法是用优先队列（最小堆）。
递归生成编码时忘记终止条件：如果节点不是叶子（没有字符），要递归左右子树；如果是叶子，才记录编码。否则会死循环或报错。
大小写敏感：'A' 和 'a' 是不同的字符，统计时要注意。实际使用时通常先统一转换为小写或大写，但压缩时按原样处理。
解压时没有哈夫曼树：压缩后的文件需要同时保存哈夫曼树的结构（或每个字符的编码），否则无法解码。这部分比较复杂，本篇文章不深入。

Python 代码实现（逐步讲解）

下面是一个完整的 Python 程序，它根据你输入的字符串生成每个字符的哈夫曼编码。代码中每一行变量定义都加了中文注释，方便理解。

import heapq  # 导入优先队列模块，用于快速找到最小频率节点

# 定义树节点类
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 = {}  # 频率字典，键是字符，值是出现次数
    for ch in text:
        freq[ch] = freq.get(ch, 0) + 1  # 如果ch不存在，返回0再加1

    # 2. 把每个字符变成节点，放入最小堆（优先队列）
    heap = [Node(char, freq) for char, freq in freq.items()]  # 列表推导式创建节点
    heapq.heapify(heap)  # 将列表转换成堆结构

    # 3. 不断合并最小的两个节点，直到只剩一个根节点
    while len(heap) > 1:
        left = heapq.heappop(heap)   # 弹出频率最小的节点，作为左子
        right = heapq.heappop(heap)  # 弹出频率次小的节点，作为右子
        merged = Node(None, left.freq + right.freq)  # 合并后的新节点，char为None
        merged.left = left
        merged.right = right
        heapq.heappush(heap, merged)  # 把新节点放回堆

    # 返回堆中唯一的节点（根节点），如果空字符串则返回None
    return heap[0] if heap else None

def generate_codes(node, prefix="", code_dict=None):
    """遍历哈夫曼树，生成字符到编码的映射字典"""
    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
        return code_dict
    # 递归遍历左子树，路径加"0"
    generate_codes(node.left, prefix + "0", code_dict)
    # 递归遍历右子树，路径加"1"
    generate_codes(node.right, prefix + "1", code_dict)
    return code_dict

# ============== 测试 ==============
text = "hello world"  # 原始字符串
root = build_huffman_tree(text)  # 构建哈夫曼树
codes = generate_codes(root)     # 生成编码字典

print("字符的哈夫曼编码：")
for char, code in codes.items():
    print(f"'{char}': {code}")

# 计算压缩前和压缩后的位数比较
original_bits = len(text) * 8  # 每个字符8位（ASCII）
compressed_bits = 0
for ch in text:
    compressed_bits += len(codes[ch])  # 累加每个字符的编码长度
print(f"\n原文长度: {len(text)} 个字符")
print(f"原始编码（固定8位）: {original_bits} 位")
print(f"哈夫曼编码后: {compressed_bits} 位")
print(f"压缩率: {compressed_bits / original_bits * 100:.1f}%")

运行这个程序，你会看到输出类似：

字符的哈夫曼编码：
'h': 1100
'e': 1101
'l': 0
'o': 10
' ': 1110
'w': 1111
'r': 010
'd': 011

原文长度: 11 个字符
原始编码（固定8位）: 88 位
哈夫曼编码后: 30 位
压缩率: 34.1%

注意：'l' 出现了3次，编码只有1位 0；'o' 出现了2次，编码 10 是2位；其他出现1次的字符编码都是4位。频率越高，编码越短！

完整可运行示例（带输入）

你可以把上面的代码复制到 Python 环境里直接运行。如果想自己输入字符串，可以在代码最后加一句：

text = input("请输入要编码的字符串：")

然后运行，看看不同输入得到的编码有什么不同。比如输入 "aaaaabbbccd"，会看到 'a' 的编码很可能只有1位。