目录
一、为什么需要哈夫曼编码
二、哈夫曼编码核心构造步骤
三、典型例题
四、哈夫曼编码特点
五、考点
前言
学完信息熵之后，紧接着最重要的考点就是无失真信源编码，而哈夫曼编码是考试出现频率最高的最优前缀码，经常出计算题。很多同学背完步骤，一拿到题目就容易踩坑：选符号、合并节点、码长分配、计算编码效率，稍有不慎就整道题失分。
本文从编码思想、构造步骤，搭配一道完整例题一步步演算，理清哈夫曼编码的做题套路。
一、为什么需要哈夫曼编码
信源各个符号发生的概率不一样，我们自然会想到：
概率大的符号，分配更短的码字；概率小的符号，分配更长的码字，这样整体平均码长就能尽可能变小，压缩数据，也就是实现无损压缩。
哈夫曼编码就是按照这个思路设计出来的最优前缀编码。
前缀码：任意一个码字，都不能是另一个码字的前缀，解码的时候不会出现歧义，不需要分隔符。
二、哈夫曼编码核心构造步骤
1. 将信源符号按照概率从小到大排序
2. 选取两个概率最小的节点，合并，两个概率相加，得到新节点
3. 给这两个分支分配码字，一般习惯：小概率标记1，大概率标记0（或者反过来，只要全程统一即可，最后结果形式不同，但平均码长不变）
4. 把合并后的新概率放回集合，重新排序，重复上面合并操作
5. 不断迭代，直到最后只剩下一个节点，概率总和等于1
6. 从根节点反向回溯，读出每个原始符号对应的码字
⚠️ 考试易错提醒：
- 每次合并之后一定要重新排序，不要沿用上次顺序
- 当出现概率相同节点时，不同选择会得到不同哈夫曼码，都算正确，但是平均码长一样
三、典型例题
题目：离散无记忆信源
对该信源进行二元哈夫曼编码，求各符号码字、平均码长、编码效率
步骤推演
1. 初始排序：0.1，0.2，0.3，0.4
2. 合并最小两个：0.1 + 0.2 = 0.3
新集合：0.3，0.3，0.4
3. 继续合并最小两个：0.3 + 0.3 = 0.6
新集合：0.4，0.6
4. 最后合并：0.4 + 0.6 = 1
分配码字（示例）
x_1(0.4)：0
x_2(0.3)：10
x_3(0.2)：110
x_4(0.1)：111
计算
平均码长
信源熵：
编码效率
四、哈夫曼编码特点
✅ 优点
1. 二元哈夫曼是最优前缀码，相同条件下平均码长最短
2. 属于无损编码，解码可以完全还原原始符号，不会丢失信息
3. 在文件压缩领域广泛应用，早期很多压缩算法底层都用到哈夫曼思想
❌ 局限性
1. 每个符号都需要事先统计概率，需要先扫描整个信源得到概率分布
2. 当信源符号概率接近均匀分布时，压缩效果很差
3. 不同合并方式得到的码字不唯一
五、考点
1. 哈夫曼编码是不是唯一编码？
答：码字不唯一，但平均码长相同，都是最优编码
2. 哈夫曼编码一定能实现无失真编码吗？
只要是前缀码，就可以唯一解码，实现无失真信源编码
结语
哈夫曼编码属于无失真信源编码最经典代表。它完美践行香农无失真编码定理：平均码长可以无限接近信源熵。
