文档章节

哈夫曼树和哈夫曼编码

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 786
阅读 8
收藏 0

哈夫曼树

给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

基本概念

哈夫曼树(霍夫曼树)又称为最优树.

1、路径和路径长度

在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和,记为WPL。

哈夫曼树的构造

哈夫曼树的构造

假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:

(1) 将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点);

(2) 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;

(3)从森林中删除选取的两棵树,并将新树加入森林;

(4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

举例

简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率(即权值)分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3,如图:

这里写图片描述

虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图:

这里写图片描述

再依次建立哈夫曼树,如下图:
这里写图片描述

其中各个权值替换对应的字符即为下图:

哈夫曼编码

这里写图片描述

所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010

霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。

我的微信二维码如下,欢迎交流讨论

这里写图片描述

欢迎关注《IT面试题汇总》微信订阅号。每天推送经典面试题和面试心得技巧

微信订阅号二维码如下:

这里写图片描述

© 著作权归作者所有

共有 人打赏支持
fengsehng
粉丝 4
博文 284
码字总数 214494
作品 0
朝阳
程序员
数据结构与算法之9(哈夫曼编解码与广度优先搜索)

》哈夫曼编码 在二叉树最后的例子里的最后提到了哈夫曼树,个人感觉不是很好理解,为大家找到了一个篇讲的比较简洁明了的http://blog.csdn.net/jinixin/article/details/52142352,就不再造轮...

kkae8643150
2017/11/27
0
0
哈夫曼树的构建、编码以及带权路径长计算

给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点...

勉旃
09/17
0
0
哈夫曼树的基本操作,(树的建立,带权路径长度,哈夫曼编码)

哈夫曼树中的名词意思:(ps:本想画个图的不知这上面怎么弄,就没弄了) 树的权值:每个树节点所在的那个数字。 路径:两个节点之间所经过的分支。 路径长度: 某一路径上的分支条数。 节点带...

lfb637
2017/09/27
0
0
HuffmanTree----文件压缩

所谓Huffmantree又称为最优二叉树,是一种带权路径长度最短的二叉树;在Huffmantree中只有叶子节点才是有效数据节点,其他的非叶子节点是为了构造Huffmantree引入的。 一、首先要知道哈弗曼树...

七十七快
06/26
0
0
HuffmanTree----文件压缩

所谓Huffmantree又称为最优二叉树,是一种带权路径长度最短的二叉树;在Huffmantree中只有叶子节点才是有效数据节点,其他的非叶子节点是为了构造Huffmantree引入的。 一、首先要知道哈弗曼树...

科技小能手
2017/11/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

redis 系列一 -- 简介及安装

1.简介 redis -- remote dictionary server 远程字典服务 使用 C 语言编写; 高性能的 key-value数据库; 内存数据库,支持数据持久化。 Redis 是一个开源(BSD许可)的,内存中的数据结构存...

imbiao
37分钟前
1
0
nginx log记录请求响应时间

有时为了方便分析接口性能等,需要记录请求的时长,通过修改nginx的日志格式可以做到,如 添加一个新的log_format log_format timed_combined '$remote_addr - $remote_user [$time_local] "...

swingcoder
今天
2
0
Spring MVC之RequestMappingHandlerMapping匹配

对于RequestMappingHandlerMapping,使用Spring的同学基本都不会陌生,该类的作用有两个: 通过request查找对应的HandlerMethod,即当前request具体是由Controller中的哪个方法进行处理; 查...

爱宝贝丶
今天
2
0
Java Web--增删改查之二界面后台java代码(转载参考)

/** *  *//** * @author Administrator * */package dao; import java.sql.*;public class DBConn {/** * 链接数据库 * @return */  ...

小橙子的曼曼
今天
4
0
Redis源码阅读笔记-对象及其类型和编码

总结之《Redis设计与实现》 对象 Redis中是使用对象来便是数据库中的键和值。 结构 // server.h...#define LRU_BITS 24...typedef struct redisObject { unsigned type:4; ...

Jian_Ming
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部