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为什么这个方法成立
- 最低频符号可放在最深兄弟位置而不损失最优性。
- 收缩这对节点后,原问题成本等于子问题最优成本加两者频次和。
- 反复安全收缩再展开,得到最优前缀码树。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
为什么编码 0 和 01 不能同时使用?
需要一点提示
一个是另一个前缀。
查看解析与答案
读到 0 时无法确定已结束还是还应读取 1,破坏无分隔前缀解码。
四个等频符号的理想码长?
需要一点提示
平衡二叉树。
查看解析与答案
各 2 位。
换成三进制码,合并规则能照抄吗?
需要一点提示
内部节点的分支数改变。
查看解析与答案
需改为三叉 Huffman 并处理叶子数量条件,通常每次合并三个最小权重并可能补零权叶。