961全部内容链接
文章目录
- 哈夫曼（Huffman）树的定义
- 哈夫曼树的构造
- 哈夫曼树的代码实现
- 哈夫曼树的应用
-
- 哈夫曼编码
哈夫曼（Huffman）树的定义
对于树的每个"叶节点"，都赋予一个权值w。如图
用它的权值乘以它的深度减1（从根节点到该节点所经过的边数），称为该节点的带权路径长度。 整个树的每个叶节点的带权路径长度之和，称为树的带权路径长度，公式如下：
W P L = ∑ i = 1 n w i l i ( w i 为 第 i 个 节 点 的 权 值 , l i 为 其 路 径 长 度 ) WPL = \sum_{i=1}^n w_i l_i ~~~~(w_i为第i个节点的权值,l_i为其路径长度) WPL=i=1∑nwili (wi为第i个节点的权值,li为其路径长度)
WPL（Weighted Path Length of Tree）。对于同一批节点，带全路径长度最小的树称为哈夫曼树，也叫最优二叉树。
该图中，树的带权路径长度分别为：
图 1 ： W P L = 1 × 2 + 3 × 2 + 4 × 2 + 5 × 2 = 26 图 2 ： W P L = 1 × 3 + 3 × 3 + 4 × 2 + 5 × 1 = 25 图 3 ： W P L = 5 × 1 + 3 × 3 + 1 × 3 + 4 × 2 = 25 \begin{aligned} & 图1：WPL = 1 \times 2 + 3\times2 + 4 \times 2 + 5 \times 2 = 26\\ & 图2：WPL = 1 \times 3 + 3 \times 3 + 4 \times 2 + 5 \times 1 = 25 \\ & 图3：WPL = 5 \times 1 + 3 \times 3 + 1 \times 3 + 4 \times 2 =25 \end{aligned} 图1：WPL=1×2+3×2+4×2+5×2=26图2：WPL=1×3+3×3+4×2+5×1=25图3：WPL=5×1+3×3+1×3+4×2=25
其中，图2和图3的带权路径长度最小的树，即哈夫曼树。也就是说，哈夫曼树不唯一。
哈夫曼树的构造
- 先将要构造哈夫曼树的节点放入一个集合
- 每次从集合中挑出两个权值最小的节点，组成新的树。左右顺序无所谓
- 将新的树加入集合，并删除原来的那两个节点
- 重复2,3动作，直到集合中只剩下一棵树。则这棵树就是哈夫曼树
哈夫曼树的代码实现
todo，非重点，后期补充
哈夫曼树的应用
哈夫曼编码
哈夫曼编码主要用于数据压缩。
考虑如下场景，目前需要传输一段文本，其中只包含A,B,C,D，其中他们出现的频率不一样：分别为 A(10)，B(8)，C(80)，D(2)。如果按照ascii码（一个字母1个字节，也就是8个bit）进行对ABCD进行编码，不用说，肯定需要很大的空间。如果简化一下，对A,B,C,D进行如下编码：
A: 00
B: 01
C: 10
D: 11
这种编码每个字母的二进制位是一致的，称为固定长度编码，此时如果传递数据的话，需要200个bit位，计算方式如下：
10 ∗ 2 + 8 ∗ 2 + 80 ∗ 2 + 2 ∗ 2 = 200 10 * 2 + 8*2 + 80 * 2 + 2 * 2= 200 10∗2+8∗2+80∗2+2∗2=200
如果将上述编码使用树进行表示，则如下图所示：
其中左边的边代表0，右边的边代表1。叶节点的权值就是该节点出现的频率。则该树的WPL就是要传输的bit长度。
此时，为了减少传输长度，就可以通过构造哈夫曼树，来将数据压缩到最小。构造后结果如下：
此时，各个字母的编码情况如下：
A: 10
B: 111
C: 0
D: 110
这种每个数据的编码长度不一致，就成为可变长度编码。此时，需要传输的数据长度为：
W P L = 80 ∗ 1 + 10 ∗ 2 + 2 ∗ 3 + 8 ∗ 3 = 130 WPL = 80*1 + 10 * 2 + 2 * 3 + 8 * 3 = 130 WPL=80∗1+10∗2+2∗3+8∗3=130
这样数据就得到了压缩。
注意：
一个编码不能是另一个编码的前缀，否则接受方就没法识别了。如果对应到哈夫曼树上，也就是说只有叶节点能存储数据，分支节点不可以存在数据。