专题进阶 · 贪心策略推荐总顺序 · 第 83 / 148 课

通过合并两个最小权重构造前缀码,并用带权路径长度衡量编码成本。

先学会这些,再进入本课 贪心思想 优先队列 二叉树
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 贪心策略

Huffman 编码Huffman Coding

不断合并频次最小的两棵树,构造最小带权路径长度的前缀码。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

通过合并两个最小权重构造前缀码,并用带权路径长度衡量编码成本。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

符号频次为 a:5、b:2、c:1、d:1,怎样用可唯一解码的二进制码减少总比特数?

02一步步得到方法

前缀码用叶子代表符号

任何符号的编码都不是另一个编码的前缀,因此从根沿比特走到叶子就能识别一个符号,不需要额外分隔符。频率高的符号放得浅,通常能节省总位数 Σfreq[s]·depth[s]。

Huffman 每次取两个最小频次子树,合为一个新节点,权重为两者之和,再放回小根堆。最后得到一棵树,左边记 0、右边记 1。

为什么合并最小者是安全的

某棵最优前缀树中可以让两个最低频符号成为最深的兄弟:把较小权重换到更深位置不会增加代价。将这对兄弟收缩为一个权重之和的新符号,剩下是同类型的更小问题。

每次合并权重之和等于这两棵子树所有叶子深度加一产生的额外编码成本,因此所有合并权重的总和等于最终带权路径长度。

合并权重就是增加一层的总代价

把两个子树接到一个新父节点,会让它们所有叶子的编码长度各增加1,总代价增加这两棵子树频次之和。因此每次合并最小的两个权重,最少增加当前这一步的加权长度。

最优性的关键还在于可以把两个最小频次符号放在最深层成为兄弟,再缩成一个伪符号继续求解。编码具体0/1方向可交换,最优总长度不受影响,所以最优编码未必唯一。

03把一个小例子完全算清楚

a5、b2、c1、d1。

步骤计算与状态为什么这样做
合并 c、d权重 2,成本增 2最小两项
合并 b 与 cd权重 4,累计 6再次取最小
合并 a 与 bcd权重 9,累计 15总编码位数 15

窄屏可左右滑动表格,阅读完整计算与理由。

等频平局可能产生不同编码,但最优带权总长度相同。

04为什么这个方法成立

  1. 最低频符号可放在最深兄弟位置而不损失最优性。
  2. 收缩这对节点后,原问题成本等于子问题最优成本加两者频次和。
  3. 反复安全收缩再展开,得到最优前缀码树。

05把推导翻译成代码

Python · 可独立运行的教学实现

import heapq
from itertools import count
def huffman(frequencies):
    serial = count()
    heap = [(f,next(serial),s) for s,f in frequencies.items() if f > 0]
    heapq.heapify(heap)
    if not heap:
        return {}
    while len(heap) > 1:
        a,_,left = heapq.heappop(heap)
        b,_,right = heapq.heappop(heap)
        heapq.heappush(heap,(a+b,next(serial),(left,right)))
    codes = {}
    def walk(node,prefix):
        if isinstance(node,str):
            codes[node] = prefix or "0"
        else:
            walk(node[0],prefix+"0"); walk(node[1],prefix+"1")
    walk(heap[0][2],"")
    return codes

逐个理解关键决定

next(serial)
相同频次时避免比较字符串叶子与元组内部节点。
prefix or "0"
单符号输入约定用一位 0,便于实际传输;纯树的深度公式则为零,需要区分约定。

06时间、空间与实现范围

k 个符号,建堆 O(k),k−1 次合并 O(k log k),树空间 O(k),输出编码还受总码字长度影响。

解码端需要知道编码树或规范码长度;压缩文件的头部成本不包含在纯符号带权长度里。

07改变条件,检查哪里会出错

频次高就直接给所有高频符号单比特码

二进制前缀码受树结构约束,不能任意分配彼此冲突的码字。

只剩一个符号时输出约定不明确

数学树深可为0,但实际编码格式可能约定至少1位;需在编码与解码双方保持一致。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

为什么编码 0 和 01 不能同时使用?

需要一点提示

一个是另一个前缀。

查看解析与答案

读到 0 时无法确定已结束还是还应读取 1,破坏无分隔前缀解码。

练习 2 · 边界与辨析

四个等频符号的理想码长?

需要一点提示

平衡二叉树。

查看解析与答案

各 2 位。

练习 3 · 变式与迁移

换成三进制码,合并规则能照抄吗?

需要一点提示

内部节点的分支数改变。

查看解析与答案

需改为三叉 Huffman 并处理叶子数量条件,通常每次合并三个最小权重并可能补零权叶。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。