4.5.3 哈弗曼树(Huffman)树和哈弗曼编码

1.哈夫曼树的定义

树中结点被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度,记为

WPL=连加Wi*Li

式中,Wi是第i个叶结点所带的权值;Ii是该叶结点到根结点的路径长度。

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

2.哈夫曼树的构造

给定N个权值分别是w1,W2,……,Wn的结点

1)将这N个结点分别分为N棵含一个结点的二叉树,构成森林F.

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

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

4)重复步骤2)和3),直到F中只剩下一棵树为止。

哈夫曼树具有如下特点:

1)每个初始结点最终都成叶结点,并且权值最小的结点到根结点的路径长度越大。

2)构造过程中共新建了N-1个结点(双分支结点),因此哈夫曼树中结点总数为2N-1。

3)每次构造都选择2棵树作为新结点的孩子,因此哈夫曼树中不存在度为1的结点。

3.哈夫曼编码

对于待处理的一个字符串序列,如果对每个字符采用同样长度的二进制来表示,则称这种编码方式为固定长度编码。

如果对不同字符采用不等长的二进制来表示,则称这种编码方式为可变长度编码。

如果没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。如0、101和100是前缀编码。

解码过程:因为没有一个码是其他码的前缀,所以,可以识别出第一个编码,将它翻译为源码,再对余下的编码文件重复同样的解码操作。如00101100可被唯一地解析为0、0、101和100。

由哈夫曼树得到哈夫曼编码是一个很自然的过程,首先,将每个出现的字符当做一个独立的结点,其权值为它出现的频度(或次数),构造出对应的哈夫曼树。显然所有字符结点都出现在叶子结点。我们可以将字符的编码解释为从根至该路径上边标记的序列,其中边标记为0表示“转向左孩子”,标记为1表示“转向右孩子”。

WPL可以看成是最终编码得到二进制编码的长度。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏朱慕之的博客

基础算法

0.创建类 BinaryTreeNode 1.创建方法:传入根结点 2.判断根节点是否为空 3.判断左右结点是否同时为空 4.用self调用此方法,将根节点的左...

7410
来自专栏技术专栏

无向图最短路径问题

题目:无向图G有N个结点(1<N<=1000)及一些边,每一条边上带有正的权重值。 找到结点1到结点N的最短路径,或者输出不存在这样的路径。

55420
来自专栏tkokof 的技术,小趣及杂念

数学小记之数系

自然数即非负整数(包括 0 和 正整数),字母表示为 N(Natural number) :

20440
来自专栏互扯程序

Java集合深度解析之TreeMap

红黑树简介 TreeMap是基于红黑树实现的,这里只对红黑树做个简单的介绍,红黑树是一种特殊的二叉排序树,红黑树通过一些限制,使其不会出现二叉树排序树中极端的一...

40850
来自专栏郭耀华‘s Blog

剑指offer 第十天

37.数字在排序数组中出现的次数 统计一个数字在排序数组中出现的次数。 采用二分查找法 /* 方法一:时间复杂度O(n),不可选 */ public cla...

34980
来自专栏机器学习入门

LWC 62:742. Closest Leaf in a Binary Tree

LWC 62:742. Closest Leaf in a Binary Tree 传送门:742. Closest Leaf in a Binary Tree...

312100
来自专栏数据结构与算法

P1040 加分二叉树

题目描述 设一个n个节点的二叉树tree的中序遍历为(1,2,3,…,n),其中数字1,2,3,…,n为节点编号。每个节点都有一个分数(均为正整数),记第i个节...

326100
来自专栏racaljk

[数据结构]C语言二叉树的实现

树和图是数据结构中比较麻烦的东西,里面涉及的概念比较多,也最有用, 就比如一般树广泛应用于人工智能的博弈上,而基于图的广度优先和深度优先搜索也广泛应用于人工智能...

33220
来自专栏ACM算法日常

算法合集 | 神奇的笛卡尔树 - HDU 1506

笛卡尔树是一个很有意思的树形结构,因为它同时满足两个性质,从key(key就是索引位置,如下图中9的key为1,3的key为2......)来看...

40820
来自专栏机器学习从入门到成神

数据结构之判断一棵树是否为完全二叉树

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

1.5K10

扫码关注云+社区

领取腾讯云代金券