哈夫曼树与哈夫曼编码

目录#

[[toc]]

概念#

目的：给出现频率高的符号分配更短的二进制码，频率低的分配更长的码，从而降低加权平均码长，实现无损压缩。

性质：它是所有“前缀码”（任一码字都不是另一码字的前缀）里平均码长最优的方案。

结论

• 哈夫曼树是一棵满二叉树（每个内部结点都有两个孩子）。
• 若有 n 个符号（叶子），则结点总数为 2n-1。
• 构造复杂度：用小根堆实现是 O(n\log n)。
• 解码方法：从根开始，读 0/1 往左/右走，走到叶子输出该符号，再回根继续。

构造算法（左孩子记 0，右孩子记 1）#

1. 统计每个符号的权值（出现次数或概率）。
2. 把每个符号当作一棵单节点树放入小根堆（按权值排序）。
3. 反复从堆中取出权值最小的两棵树合并成一棵新树，新树权值为两子树权值之和，再放回堆。
4. 堆中只剩一棵树时结束。根到各叶的 0/1 路径即为该叶（符号）的码字。

合并时左右次序随意（通常把较小的放左边），不同实现得到的码字可能不同，但总加权码长相同

例如：

a:45, b:13, c:12, d:16, e:9, f:5

               [100]
              /     \
          a(45)     [55]
                    /   \
                 [25]   [30]
                 /  \    /  \
             c(12) b(13)[14] d(16)
                         / \
                      f(5) e(9)
                     
编码：
a: 0
b: 101
c: 100
d: 111
e: 1101
f: 1100

face
	•	f → 1100
	•	a → 0
	•	c → 100
	•	e → 1101
拼接得到比特串：1100 0 100 1101 → 110001001101

• 构建哈夫曼树的目标，是让带权路径长度最小。

• 公式：

  $WPL = \sum_{i=1}^{n} w_i \times l_i$

  • $w_i$ ：第 i 个叶子的权值（出现次数或概率）
  • $l_i$ ：该叶子到根的路径长度（码字长度）

哈夫曼算法的本质就是：

找一棵满二叉树，使得加权路径长度 WPL 最小

数据 -> 统计频率(权值) -> 构建最优二叉树(哈夫曼树) -> 导出二进制码(哈夫曼码)

应用场景#

1️⃣ 作用：无损压缩的“最优前缀码”

• 目标：让常用字符用更短的二进制表示，不常用的字符用稍长的表示，整体平均长度最低。
• 效果：减少存储空间、缩短传输时间，且无损（解码后与原数据一模一样）。

直观例子

假设有 6 个字符：

a:45 b:13 c:12 d:16 e:9 f:5

【a:45 这类数字，本质是每个符号出现的次数或概率。】

如果直接定长编码，每个要 3bit，总共 300bit。

哈夫曼编码后平均约 2.24bit/字符，总共约 224bit，节省 25% 空间。