复旦大学961-数据结构-第二章-树（5）-哈夫曼（Huffman）树的定义与应用

╰+攻爆jí腚メ 2022-12-11 13:47 141阅读 0赞

[961全部内容链接][961]

### 文章目录 ###

*  哈夫曼（Huffman）树的定义
 *  哈夫曼树的构造
 *  哈夫曼树的代码实现
 *  哈夫曼树的应用
 *   *  哈夫曼编码

# 哈夫曼（Huffman）树的定义 #

对于树的每个"**叶节点**"，都赋予一个权值w。如图

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]  
用它的权值乘以它的深度减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的带权路径长度最小的树，即哈夫曼树。也就是说，哈夫曼树不唯一。

# 哈夫曼树的构造 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 1]

1.  先将要构造哈夫曼树的节点放入一个集合
2.  每次从集合中挑出两个权值最小的节点，组成新的树。左右顺序无所谓
3.  将新的树加入集合，并删除原来的那两个节点
4.  重复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  
如果将上述编码使用树进行表示，则如下图所示：  
![在这里插入图片描述][20201002094015332.png_pic_center]  
其中左边的边代表0，右边的边代表1。叶节点的权值就是该节点出现的频率。则该树的WPL就是要传输的bit长度。

此时，为了减少传输长度，就可以通过构造哈夫曼树，来将数据压缩到最小。构造后结果如下：  
![在这里插入图片描述][20201002094330431.png_pic_center]  
此时，各个字母的编码情况如下：

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

这样数据就得到了压缩。

注意：  
一个编码不能是另一个编码的前缀，否则接受方就没法识别了。如果对应到哈夫曼树上，也就是说只有叶节点能存储数据，分支节点不可以存在数据。

[961]: https://blog.csdn.net/zhaohongfei_358/article/details/111414370
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/dd715eb6bb44494fbd7f2ad8b20b8078.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW9ob25nZmVpXzM1OA_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/9d607c7c74cc424694b59ab057aa9046.png
[20201002094015332.png_pic_center]: /images/20221123/af021ff29ae74df6beb9bdd10eb47d78.png
[20201002094330431.png_pic_center]: /images/20221123/212b604672334cba93e5ce406b3fca9c.png