❤️

ARCHAI

Undergraduate / Rookie

Back

哈夫曼树

基本概念

1.结点的权

每个结点带有的具有某种现实意义的数值(比如代表重要性等)

2.结点的带权路径长度

从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积

3.的带权路径长度

树中所有叶结点的带权路径长度之和(WPL, Weighted Path Length)

$WPL=\sum_{i=1}^{n}w_il_i$

4.哈夫曼树

在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树

构造哈夫曼树

给定n个权值分别为 $w_1,w_2,…,w_n$ 的结点,其构造过程描述如下:

① 将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F

② 构造一个新结点,从F中选取两棵根结点权值最小的树作为新结点的左右子树,并且将新结点的权值置为左、右子树上根结点的权值之和。

③ 从F中删除刚才选出的两棵树,同时将新得到的树加入F中。

④ 重复步骤②和③,直至F中只剩下一棵树为止。

假设给定结点在经过步骤①之后如下

则其②③④步骤为:

$WPL_{min}=1*7+2*3+3*2+4*1+4*2=31$

或者

$WPL_{min}=1*7+3*(1+2+2+3)=31$

👇👇👇👇👇👇

哈夫曼树特点:

① 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大。 ② 哈夫曼树的结点总数为2n-1。 ③ 哈夫曼树中不存在度为1的结点。 ④ 哈夫曼树并不唯一,但WPL必然相同且为最优。

哈夫曼编码

固定长度编码

如ASCII码

可变长度编码

前缀编码

没有一个编码是另一个编码的前缀

哈夫曼编码

由哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点,各个字符出现的频度作为结点的权值,根据之前介绍的方法构造哈夫曼树。

应用

可用于数据压缩

如图,为英文字母使用频率表,若不进行压缩,第 i 个字母频率用$l_i表示$,路径长至少为5($2^4<26<2^5$),则

$WPL=5×\sum_{i=1}^{n}l_i$=500

若通过构造哈夫曼树进行哈夫曼编码

则$WPL_{min}=$

$v=\frac{WPL_{min}}{WPL}$

Archai
Built with Hugo
Theme Stack designed by Jimmy