当前位置:网站首页>哈夫曼树基本概念
哈夫曼树基本概念
2022-07-06 20:18:00 【木子正文_啊嘞】
哈夫曼树的基本概念:
(1)路径:由一结点到另一结点间的分支所构成
(2)路径长度:路径上的分支数目a→d的路径长度= 2
(3)树的路径长度:从树根到每一结点的路径长度之和。 例图:10
(4)权:赋予某个实体的一个量,是对实体的属性的数值化描述。若树的结点带有权值,即为带权树。
(5)结点的带权路径长度:结点到根的路径长度与结点上权值的乘积d的带权路径长度=72=14
(6)树的带权路径长度:树中所有叶子结点的带权路径长度之和。例图:27+25+22+2*4=36
(7)赫夫曼树(Huffman):最优二叉树,带权路径长度最小的树
哈夫曼树的特点
- 权值大的结点到根结点的路径长度短;
- 权值小的结点到根结点的路径长度长。
Ø哈夫曼编码树中没有度为1的结点;
Ø若给定n个权值(n个叶子结点),则哈夫曼树的总结点数为 2n-1;
Ø哈夫曼树的高度不超过n。
哈夫曼树的构造算法:
哈夫曼编码:
v前缀编码:任一字符的编码都不是另一字符编码的前缀。
如:字符a、b、c、d的编码分别为0、1、01、10,则a的编码是c的编码的前缀,b的编码是d编码的前缀,该编码不是前缀编码。
在译码时,对于01011011的译码结果将不唯一。
v哈夫曼编码
对一棵具有n个叶子的哈夫曼树,对每个左分支赋予0,右分支赋予1,则从根到每个叶子的路径上,分别构成一个二进制串,该二进制串称为哈夫曼编码。
进行哈夫曼编码,先建哈夫曼树。
哈夫曼编码是前缀编码,且是最优前缀编码。
边栏推荐
- Domcontentloaded and window onload
- When you go to the toilet, you can clearly explain the three Scheduling Strategies of scheduled tasks
- 腾讯云原生数据库TDSQL-C入选信通院《云原生产品目录》
- Not All Points Are Equal Learning Highly Efficient Point-based Detectors for 3D LiDAR Point
- The version control of 2021 version is missing. Handling method
- 硬件之OC、OD、推挽解释
- Jerry's transmitter crashed after the receiver shut down [chapter]
- 杰理之开 BLE 退出蓝牙模式卡机问题【篇】
- 【达梦数据库】备份恢复后要执行两个sql语句
- 你知道电子招标最突出的5大好处有哪些吗?
猜你喜欢
Cryptography series: detailed explanation of online certificate status protocol OCSP
树莓派设置wifi自动连接
22.(arcgis api for js篇)arcgis api for js圆采集(SketchViewModel)
制作(转换)ico图标
Lavel PHP artisan automatically generates a complete set of model+migrate+controller commands
如何替换模型的骨干网络(backbone)
尚硅谷JVM-第一章 类加载子系统
数学归纳与递归
The latest 2022 review of "small sample deep learning image recognition"
Jerry's broadcast has built-in flash prompt tone to control playback pause [chapter]
随机推荐
Variables, process control and cursors (MySQL)
mos管實現主副電源自動切換電路,並且“零”壓降,靜態電流20uA
Household appliance industry under the "retail is king": what is the industry consensus?
Lavel PHP artisan automatically generates a complete set of model+migrate+controller commands
上个厕所的功夫,就把定时任务的三种调度策略说得明明白白
leetcode
杰理之播内置 flash 提示音控制播放暂停【篇】
C language string sorting
OC, OD, push-pull explanation of hardware
存储过程与函数(MySQL)
尚硅谷JVM-第一章 类加载子系统
Graphical tools package yolov5 and generate executable files exe
杰理之开启经典蓝牙 HID 手机的显示图标为键盘设置【篇】
【安全的办公和生产力应用程序】上海道宁为您提供ONLYOFFICE下载、试用、教程
Shell programming basics
源代码保密的意义和措施
CVPR 2022 best paper candidate | pip: six inertial sensors realize whole body dynamic capture and force estimation
Laravel php artisan 自动生成Model+Migrate+Controller 命令大全
Flink task exit process and failover mechanism
cocos3——8.实现初学者指南