506 哈夫曼树

哈夫曼树

定义

带权路径长度

• 结点的权：给树中的每个结点赋予一个有意义的数值，称为该结点的权。
• 结点的带权路径长度：从树根到该结点之间的路径长度与该结点权的乘积。
  • 路径长度：从根结点到目标结点所经过的边数
  • 带权路径长度 = 路径长度 × 结点权值
• 树的带权路径长度（WPL）：树中所有叶结点的带权路径长度之和。

$$WPL=\sum _{i=1}^n{w}_i\cdot l_i$$

其中 $w_i$ 是第 $i$ 个叶结点的权值，$l_i$ 是第 $i$ 个叶结点的路径长度。

哈夫曼树（最优二叉树）

在含有 $n$ 个带权叶结点的所有二叉树中，带权路径长度最小的二叉树称为哈夫曼树或最优二叉树。

构造方法

给定 $n$ 个权值分别为 $w_1,w_2,\dots ,w_n$ 的结点，构造方法如下：

哈夫曼算法（贪心算法）

1. 初始化：将 $n$ 个权值看作 $n$ 棵只有根结点的二叉树，构成森林 $F=\{T_1,T_2,\dots ,T_n\}$

2. 重复执行以下步骤（共执行 $n-1$ 次）：

   • 在森林 $F$ 中选取两棵根结点权值最小的树作为左、右子树
   • 构造一棵新的二叉树，其根结点权值为左、右子树根结点权值之和
   • 从森林 $F$ 中删除这两棵树，同时将新构造的树加入森林 $F$

3. 结束条件：森林中只剩一棵树时，该树即为哈夫曼树

构造示例

设有权值序列：{5, 29, 7, 8, 14, 23, 3, 11}

步骤	选择结点	新结点权值	森林状态
1	3, 5	8	{8, 7, 8, 11, 14, 23, 29}
2	7, 8(新)	15	{8, 11, 14, 15, 23, 29}
3	8, 11	19	{14, 15, 19, 23, 29}
4	14, 15	29	{19, 23, 29, 29}
5	19, 23	42	{29, 29, 42}
6	29, 29	58	{42, 58}
7	42, 58	100	{100}

算法特点

• 时间复杂度：$O(n\log n)$（使用优先队列实现）
• 空间复杂度：$O(n)$
• 最优性：基于贪心策略，每次选择当前最小权值，保证全局最优
• 唯一性：当权值中有相等值时，哈夫曼树形态可能不同，但 WPL 相同

性质

基本性质

• 权值越大的叶结点离根越近
• 哈夫曼树中没有度为 1 的结点（只有度为 0 和度为 2 的结点）
• 哈夫曼树不唯一，但 WPL 值唯一且最小
• 在哈夫曼树（Huffman Tree） 中，它的带权路径长度（WPL）恰好等于其所有分支节点（非叶结点）的权值之和。

节点数量关系

• 若哈夫曼树有 $n$ 个叶节点，则：
  • 总节点数：$2n-1$
  • 非叶节点数：$n-1$
• 反之，若哈夫曼树总共有 $m$ 个节点，则：
  • 叶子节点数：$(m+1)/2$
  • 非叶节点数：$(m-1)/2$

推导过程：

设哈夫曼树中：

• 叶结点（度为 0）数量为 $n_0$
• 度为 2 的结点数量为 $n_2$
• 总结点数为 $n$ 由于哈夫曼树中没有度为 1 的结点，所以：

$$n=n_0+n_2$$

在任意二叉树中，边数 = 总结点数 - 1，即：

$$\text{边数}=n-1=n_0+n_2-1$$

从度的角度统计边数（每条边对应一个非根结点）：

$$\text{边数}=0\cdot n_0+2\cdot n_2=2n_2$$

因此：

$$2n_2=n_0+n_2-1$$ $$n_2=n_0-1$$

将此关系代入总结点数公式：

$$n=n_0+n_2=n_0+(n_0-1)=2n_0-1$$

所以：

• 若有 $n_0$ 个叶结点，则总结点数为 $2n_0-1$，非叶结点数为 $n_0-1$
• 若总结点数为 $m$，则叶结点数为 $\frac{m+1}{2}$，非叶结点数为 $\frac{m-1}{2}$

应用

前缀编码

定义：前缀编码是指任何一个字符的编码都不是另一个字符编码的前缀。

特点：

• 无二义性：解码过程中不会产生歧义
• 即时解码：读到完整编码后可立即确定对应字符
• 最优性：哈夫曼编码是最优的前缀编码

示例：

• 合法前缀编码：A=0, B=10, C=110, D=111
• 非法前缀编码：A=0, B=01, C=011（A 是 B 的前缀）

数据压缩（哈夫曼编码）

基本原理：

• 根据字符出现频率构造哈夫曼树
• 高频字符分配短编码，低频字符分配长编码
• 实现数据的无损压缩

编码步骤：

1. 统计频率：计算各字符在文本中的出现频率
2. 构造哈夫曼树：以字符频率为权值构建最优二叉树
3. 生成编码：
   • 左子树路径标记为 ‘0’
   • 右子树路径标记为 ‘1’
   • 从根到叶的路径即为该字符的编码

解码过程：

• 从根节点开始，根据编码序列中的 0/1 选择左/右子树
• 到达叶节点时输出对应字符，重新从根开始

压缩效果：

• 压缩比 = $\frac{\text{原文件大小}-\text{压缩后大小}}{\text{原文件大小}}\times 100\%$
• 平均编码长度 = ${\sum }_{i=1}^n{p}_i\cdot l_i$（其中 $p_i$ 为字符频率，$l_i$ 为编码长度）

应用场景：

• 文件压缩（ZIP、GZIP 等）
• 图像压缩（JPEG 等）
• 通信传输中的数据编码

推广

度为 m 的哈夫曼树

度为 m 的哈夫曼树（m-ary Huffman Tree）是普通二叉哈夫曼树的推广，其目标同样是在所有具有相同带权叶结点的 m 叉树中，找到一棵带权路径长度（WPL）最小的树。

它具有以下几个主要特点：

依然是最优树

其核心特点没有改变：对于给定的 $n$ 个带权叶结点，度为 $m$ 的哈夫曼树是所有 m 叉树中 WPL 最小的那一棵。

构造方法的推广

它的构造方法是二叉哈夫曼树构造过程的推广：

• 二叉 (m=2)：每次选取权值最小的 2 个结点，合并成一个新结点。
• m 叉 (m>2)：每次选取权值最小的 m 个结点，合并成一个新的父结点。这个新父结点的权值是这 $m$ 个子结点权值之和。这个过程一直重复，直到最后只剩下一个根结点。

结点数量的约束

为了确保每次都能不多不少地取 $m$ 个结点，并且最后能完美地形成一棵树（即只剩一个根结点），对叶结点的数量 $n$ 有一个要求。

在合并过程中，每合并一次，结点总数就减少 $m-1$。为了从 $n$ 个叶结点最终变成 $1$ 个根结点，总共需要减少 $n-1$ 个结点。因此， $n-1$ 必须是 $m-1$ 的整数倍。

• 约束条件：$(n-1)(\mathrm{mod}m-1)=0$
• 解决方法：如果原始的 $n$ 个叶结点不满足这个条件，我们需要添加若干个权值为 0 的“虚结点”，直到结点总数 $n^{\prime }$ 满足 (n' - 1) % (m - 1) == 0 为止。因为这些虚结点的权值为 0，所以它们不会影响最终 WPL 的计算结果，但能保证哈夫曼树的结构是完整的。

树的结构特点

• 在（可能添加了虚结点后的）一棵度为 m 的哈夫曼树中，不存在度为 1, 2, …, m-1 的结点。也就是说，任何一个分支结点（非叶结点）都恰好有 $m$ 个子结点。
• 权值越大的叶结点，离根结点越近（路径长度越短）；权值越小的叶结点，离根结点越远（路径长度越长）。这保证了最终的 WPL 是最小的。

总结

特点	描述
最优性	在所有可能的 m 叉树中，其带权路径长度（WPL）最小。
构造算法	采用贪心策略，每次合并当前权值最小的 $m$ 个结点。
结点约束	叶结点总数 $n$ 需要满足 (n-1)%(m-1)==0，否则需添加权值为 0 的虚结点。
分支度数	所有分支结点（非叶结点）的度都恰好为 $m$。
权值分布	权值越大的叶结点离根越近，权值越小的离根越远。

定长编码集

概念

定义：定长编码是指每个字符都用相同长度的二进制串来表示的编码方式。

基本特征：

• 编码长度固定：所有字符的编码长度相同
• 解码唯一性：任何编码序列只有唯一的解码结果
• 无前缀性：任何编码都不是其他编码的前缀

编码长度确定：

• 若字符集大小为 n，则编码长度至少为 $\lceil {\log }_{2}n\rceil$ 位
• 例如：26 个英文字母需要 $\lceil {\log }_{2}26\rceil =5$ 位编码

优缺点分析：

优点	缺点
解码简单，无需分隔符	编码效率低，未考虑字符频率
编码长度可预测	总编码长度通常较长
实现简单	存储空间利用率不高

二叉树形

满二叉树结构：

• 叶节点：存储待编码的字符
• 内部节点：用于路径导航，不存储字符信息
• 树的深度：等于编码长度，为 $\lceil {\log }_{2}n\rceil$

编码规则：

• 左子树：编码位为 0
• 右子树：编码位为 1
• 根到叶路径：构成该字符的完整编码

构造方法：

1. 确定树深度：$d=\lceil {\log }_{2}n\rceil$
2. 构建满二叉树：深度为 d 的完全二叉树
3. 字符分配：将 n 个字符分配到叶节点
4. 编码生成：从根到每个叶节点的路径即为对应字符的编码

示例（4 个字符 A、B、C、D）：

        根
       /  \
      0    1
     / \  / \
    A  B  C  D

• A: 00
• B: 01
• C: 10
• D: 11

性质：

• 无歧义性：由于是满二叉树且字符仅在叶节点，解码过程唯一
• 即时解码：读取固定长度位数即可确定字符
• 空间利用：若字符数 n 不是 2 的幂，会有 $2^d-n$ 个叶节点空闲

与变长编码对比：

• 哈夫曼编码：根据字符频率构造最优二叉树，编码长度可变
• 定长编码：不考虑频率，所有字符编码长度相同，构造简单但效率较低