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

这篇具有很好参考价值的文章主要介绍了哈夫曼树、带权路径长度、前缀编码 的概念。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、基本概念

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=71+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://www.toymoban.com/news/detail-755561.html

到了这里,关于哈夫曼树、带权路径长度、前缀编码 的概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 哈夫曼树,哈夫曼编码及解码详解

    🌍新人小白的博客 ⌛️希望大家多多关注 🌱一起加油,共同成长 🎃以后会经常更新哒~🙈 ⭐️个人主页: 收藏加关注,永远不迷路~⭐️ 一: 顺序表的操作,你真的学会了吗? 二: 顺序栈的基本操作 三: 循环队列的基本操作,你学会了吗? 四: 单链表的操作(超详细

    2024年02月05日
    浏览(45)
  • 哈夫曼树详解及其应用(哈夫曼编码)

    一,哈夫曼树的基本概念 路径: 从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径 结点的路径长度 :两结点之间路径上的 分支数 树的路径长度: 从 树根 到每一个结点的 路径长度之和 . 记作:TL 权(weight): 将树中结点赋给一个有着某种含义的数值

    2024年02月04日
    浏览(48)
  • 哈夫曼树、哈夫曼编码和字典树

    目录 哈夫曼树 树的带权路径长度(wpl) 哈夫曼编码 代码实现哈夫曼树 封装哈夫曼树的节点 构建哈夫曼树 字典树 执行流程 代码实现字典树 封装字典树的节点 构建字典树         哈夫曼树(Huffman Tree)是一种带权路径长度最短的二叉树。哈夫曼树常常用于数据压缩,其压

    2023年04月09日
    浏览(49)
  • 数据结构——哈夫曼树与哈夫曼编码

    1.1 基本概念 路径 :指从根结点到该结点的分支序列。 路径长度 :指根结点到该结点所经过的分支数目。 结点的带权路径长度 :从树根到某一结点的路径长度与该结点的权的乘积。 树的带权路径长度(WPL) :树中从根到所有叶子结点的各个带权路径长度之和。 哈夫曼树 是由

    2024年02月05日
    浏览(43)
  • 数据结构之哈夫曼树与哈夫曼编码

    编码是信息处理的基础(重新表示信息)。 普通的编码是等长编码,例如7位的ASCIL编码,对出现频率不同的字符都使用相同的编码长度。 但其在传输和存储等情况下编码效率不高 。 可使用不等长编码,来压缩编码:高频字符编码长度更短,低频字符编码长度更长。   [例

    2023年04月15日
    浏览(61)
  • 数据结构之哈夫曼树和哈夫曼编码

    切入正题之前,我们先了解几个概念: 路径:从树的一个结点到另一个结点分支所构成的路线 路径长度:路径上的分支数目 树的路径长度:从根结点出发到每个结点的路径长度之和 带权路径长度:该结点到根结点的路径长度乘以该结点的权值 树的带权路径长度:树中所有

    2024年02月11日
    浏览(43)
  • 哈夫曼树及哈夫曼编码(考试常考版)

    哈夫曼树的基本概念 哈夫曼树的定义是对一组具有确定权值的叶子节点,选出最小带权路径长度的二叉树为哈夫曼树(WPL最小),也称最优二叉树 哈夫曼算法的实现 注意:哈夫曼树在构造时选择两个最小的权值点,默认小的在左边大的在右边,但实际上并没有硬性规定,可以

    2024年02月11日
    浏览(55)
  • 【贪心法】最优前缀码(Huffman哈夫曼算法)

    在计算机中需要用0-1字符串作为代码来表示信息,为了正确解码,必须要求任何字符的代码不能作为其他字符代码的前缀,这样的码称为 二元前缀码。 二元前缀码的存储通常采用二叉树结构,令每个字符作为树叶,对应这个字符的前缀码看作根到这片树叶的一条路径,规定

    2024年02月03日
    浏览(47)
  • 数据结构课程实验五:哈夫曼树与哈夫曼编码

    实验日期:2022-12-20   目录 一、实验目的 1、掌握哈夫曼树的建立 2、掌握哈夫曼编码方式 二、实验内容

    2024年02月05日
    浏览(47)
  • 【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码

    超详细讲解哈夫曼树(Huffman Tree)以及哈夫曼编码的构造原理、方法,并用代码实现。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。 结点的路径长度 :两结点间路径上的 分支数 。 树的路径长度: 从树根到每一个结点的路径长度之和。记作: TL  权

    2024年02月06日
    浏览(51)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包