【2023年修正版】哈夫曼编码详解

2023-12-02 22:20

本文主要是介绍【2023年修正版】哈夫曼编码详解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

霍夫曼编码的原理就是根据字符的使用频率,排成二叉树,使用次数少的放到后面,使用次数多的离根节点越近;这样字符的占位也相应的较少。

  1. 首先,主要操作是找每次字符中使用频率最低的(数最小)两个数字,然后将他们两个结合;
  2. 结合后的数字和添加到原数组中(使用频率次数中),继续找最小的两个,根据左小右大原则存放;
  3. 最终组成的数从根节点开始左0右1,遍历到目标节点即为哈夫曼编码。

其中,如果遇到相等的情况则按小于的情况来看。

以下题为例,画哈夫曼编码图
image.png

第一步

先写出字符对应的频率:
8fe6e7a3f1e7d36c1fba1781ab90b1b.jpg
找到其中最小的两个数,目前为5和4;并将他们两个结合左小右大,4+5=9;
e68a15f4e57328a35901fbf2ba88e1b.jpg

第二步

将9写入原序列中,删除已经用掉的4和5
image.png
再找其中最小的两个数,这次为8和9;9已经在图中了,根据左小右大原则,8放到9的左边并相加结合;
8+9=17
image.png

第三步

基本就是这样的步骤,下面删除已经用过的8和9,再加上17
image.png
当前最小的数为13和17(注意相同的数字优先找原序列中的),找个其他地方重新结合即可;
image.png

第四步

数字序列中加上刚刚得到的30,找到最小的17和24结合;
image.png

第五步

这一步最小的数为34和30,将这两个结合,得到30+34=64
image.png

第六步

将最后两个数结合即可得到哈夫曼树;
image.png

以下方法是2022年底有缺陷的方法。


直接上题目:
已知字符集{ a, b, c, d, e, f },若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 },则对应字符集中各字符的哈夫曼编码可能是:(2分)
A. 00, 1011, 01, 1010, 11, 100
B. 00, 100, 110, 000, 0010, 01
C. 10, 1011, 11, 0011, 00, 010
D. 0011, 10, 11, 0010, 01, 000

步骤一:

1.找最小两个次数(这里是2和3)
image.png
2.把他们放进树中(小左大右
3.每次组合都多一个父节点(即2+3=5)
image.png

步骤二:

1.再选出2个最小的数(排除上面已经选了的)——选出了4和6
image.png
2.因为4<=5(注意是小于等于) , 6>5(5为步骤一中组合后的父节点)
3.单独拿4来跟5组合(小左大右) 【如果拿出的2个数都比5小,则这2个数自己组合后跟5组合,下面提到】
image.png

步骤三:

1.因为步骤二用掉了4,还没用6。现在取最小2个数
image.png
2.因为6 < 9 , 8< 9 所以6和8自己组合(小左大右) (组合后先放一边)
image.png

步骤四:

1.取出最后10
image.png
2.10要和这两个子树根节点最小的组合(9<14,所以和9组合)(小左大右
image.png
3.然后把14的子树组合上去(小左大右) 所以放左边
image.png

步骤五:

组合完哈夫曼树后,将对应的字符填上去
image.png

步骤六:

从根节点开始向下走往左为0,往右1。走到对应的字符的路径就是该字符的哈夫曼编码(左0右1
image.png

最后结果:

字符哈夫曼编码
a00
b1011
c01
d1010
e11
f100

所以最后答案 A
已知字符集{ a, b, c, d, e, f },若各字符出现的次数分别为{ 6, 3, 8, 2, 10, 4 },则对应字符集中各字符的哈夫曼编码可能是:(2分)
A. 00, 1011, 01, 1010, 11, 100 ✔
B. 00, 100, 110, 000, 0010, 01
C. 10, 1011, 11, 0011, 00, 010
D. 0011, 10, 11, 0010, 01, 000

这篇关于【2023年修正版】哈夫曼编码详解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/447050

相关文章

SpringIoC与SpringDI详解

《SpringIoC与SpringDI详解》本文介绍了Spring框架中的IoC(控制反转)和DI(依赖注入)概念,以及如何在Spring中使用这些概念来管理对象和依赖关系,感兴趣的朋友一起看看吧... 目录一、IoC与DI1.1 IoC1.2 DI二、IoC与DI的使用三、IoC详解3.1 Bean的存储

Spring Cloud之注册中心Nacos的使用详解

《SpringCloud之注册中心Nacos的使用详解》本文介绍SpringCloudAlibaba中的Nacos组件,对比了Nacos与Eureka的区别,展示了如何在项目中引入SpringClo... 目录Naacos服务注册/服务发现引⼊Spring Cloud Alibaba依赖引入Naco编程s依

C语言中的浮点数存储详解

《C语言中的浮点数存储详解》:本文主要介绍C语言中的浮点数存储详解,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、首先明确一个概念2、接下来,讲解C语言中浮点型数存储的规则2.1、可以将上述公式分为两部分来看2.2、问:十进制小数0.5该如何存储?2.3 浮点

大数据spark3.5安装部署之local模式详解

《大数据spark3.5安装部署之local模式详解》本文介绍了如何在本地模式下安装和配置Spark,并展示了如何使用SparkShell进行基本的数据处理操作,同时,还介绍了如何通过Spark-su... 目录下载上传解压配置jdk解压配置环境变量启动查看交互操作命令行提交应用spark,一个数据处理框架

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

Java实现数据库图片上传功能详解

《Java实现数据库图片上传功能详解》这篇文章主要为大家详细介绍了如何使用Java实现数据库图片上传功能,包含从数据库拿图片传递前端渲染,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1、前言2、数据库搭建&nbsChina编程p; 3、后端实现将图片存储进数据库4、后端实现从数据库取出图片给前端5、前端拿到

Windows命令之tasklist命令用法详解(Windows查看进程)

《Windows命令之tasklist命令用法详解(Windows查看进程)》tasklist命令显示本地计算机或远程计算机上当前正在运行的进程列表,命令结合筛选器一起使用,可以按照我们的需求进行过滤... 目录命令帮助1、基本使用2、执行原理2.1、tasklist命令无法使用3、筛选器3.1、根据PID

MySql中的数据库连接池详解

《MySql中的数据库连接池详解》:本文主要介绍MySql中的数据库连接池方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql数据库连接池1、概念2、为什么会出现数据库连接池3、原理4、数据库连接池的提供商5、DataSource数据源6、DBCP7、C

Spring-AOP-ProceedingJoinPoint的使用详解

《Spring-AOP-ProceedingJoinPoint的使用详解》:本文主要介绍Spring-AOP-ProceedingJoinPoint的使用方式,具有很好的参考价值,希望对大家有所帮... 目录ProceedingJoinPoijsnt简介获取环绕通知方法的相关信息1.proceed()2.g

一文详解kafka开启kerberos认证的完整步骤

《一文详解kafka开启kerberos认证的完整步骤》这篇文章主要为大家详细介绍了kafka开启kerberos认证的完整步骤,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、kerberos安装部署二、准备机器三、Kerberos Server 安装1、配置krb5.con