哈夫曼树、带权路径长度、前缀编码 的概念

• 算法结构

文章目录

  • 一、基本概念
    • 1.1带权路径长度（WPL）
    • 1.2哈夫曼树
  • 二、哈夫曼树的构造
  • 三、哈夫曼树的应用
    • 3.1哈夫曼编码与前缀编码

一、基本概念

1.1带权路径长度（WPL）

路径长度： 经历的边数

结点的带权路径长度： 从树的根到该结点的路径长度 X 该结点上权值。

举例帮助理解

在这里插入图片描述

图中结点A的带权路径长度为:

3

×

5

=

15

3\times5=15

3×5=15

图中结点D的带权路径长度为:

2

×

2

=

4

2\times 2=4

2×2=4

1.2哈夫曼树

树的带权路径长度： 所有叶子结点的带权路径长度之和

哈夫曼树： 在含n个带权结点的二叉树中，带权路径最小的二叉树，又称最优二叉树

【注意】：哈夫曼树是最小带权二叉树，此处指树的带权路径长度（所有叶子结点WPL之和）

二、哈夫曼树的构造

给定n个权值分别为

w

1

,

w

2

,

w

3

,

.

.

.

,

w

n

w_1,w_2,w_3,…,w_n

w1​,w2​,w3​,…,wn​的结点，构造哈夫曼树的算法描述如下：

  1. 每次从结点集合中选择最小的两个结点，作为新结点的左右子树。
  2. 新结点的权值为被选出的两个结点权值之和。
  3. 删除旧的两个结点，将新结点加入集合
  4. 重复123步骤，直至集合中只剩一个结点

举例帮助理解：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

至此，哈夫曼树构造完毕

W

P

L

=

7

∗

1

+

3

∗

(

1

+

2

+

2

+

3

)

=

31

WPL=7*1+3*(1+2+2+3)=31

WPL=7∗1+3∗(1+2+2+3)=31

三、哈夫曼树的应用

3.1哈夫曼编码与前缀编码

笔者在学习过程中，一直不明白，为什么哈夫曼树中，最小带权路径长度，是指所有叶子结点的WPL之和。也就是说，a,b,c,d都只能为叶子结点。

在这里插入图片描述

在此篇文章的案例中给出了答案。

可变长度编码： 允许对不同字符用不等长的二进制位表示

为了使编码的长度更短，进行可变长度编码，频率越高的码，对应的位数越少。根据我们所学的知识，可用哈夫曼树来解决。

举例帮助理解

学霸小甲答应告诉学渣小乙考试答案。他们决定用二进制编码来防止老师发现。

已知：C的出现频率为40%，A为30%，B为20%，D为10%

在这里插入图片描述

这里给出了答案。

对同一答案CAAABD

正确的哈夫曼编码应该为

0101010111110

而错误的哈夫曼编码为

01111110

只用肉眼看，是看不出问题在哪里的。一个合格的编码唯一对应一个答案。那么我们就从得到的编码逆向推导答案。

01111110得到的答案不唯一

0 11 11 11 0 = C B B B C??

0 1 1 1 1 1 1 0 = C A A A A A A C??

在读到A时，哈夫曼树仍可往下读得到B,D。（B,D的编码包含A）

因此，无法判断一个答案的范围。

0101010111110得到的答案唯一

0 10 10 10 111 110

= C A A A B D

而在正确编码中，读到A/B/C/D时，均为叶子结点，哈夫曼树不可往下读。也就实现了自动截断。

总结如上，要使编码之间不冲突，则编码之间是互相独立的，没有一个编码是另一个编码的前缀。这样的编码称之为前缀编码

哈夫曼编码就是一种前缀编码

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/3901620858.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐