文档章节

哈夫曼树和哈夫曼编码

fengsehng
 fengsehng
发布于 2016/11/09 09:11
字数 786
阅读 8
收藏 0
点赞 0
评论 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

用哈弗曼编码实现压缩软件

哈夫曼压缩是个无损的压缩算法,一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出...

刘学炜 ⋅ 2012/09/25 ⋅ 0

哈夫曼树的基本操作,(树的建立,带权路径长度,哈夫曼编码)

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

lfb637 ⋅ 2017/09/27 ⋅ 0

HuffmanTre----文件压缩

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

木木侠 ⋅ 2016/08/20 ⋅ 0

HuffmanTree----文件压缩

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

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

数据结构之哈夫曼树和编码器的构造

在最近的自学数据结构的过程中,为加深树的理解,码了一个二叉树编码器,请多多指教: #include #define MAXBIT100 //最大子树 #define MAXVALUE10000 //最大值 #define MAXLEAF30 //最大编码数 ...

云时之间 ⋅ 2017/11/15 ⋅ 0

最优二叉树——哈夫曼树

一:什么是最优二叉树? 从我个人理解来说,最优二叉树就是从已给出的目标带权结点(单独的结点) 经过一种方式的组合形成一棵树.使树的权值最小. 最优二叉树是带权路径长度最短的二叉树。根据...

长平狐 ⋅ 2012/11/12 ⋅ 0

详细图解哈夫曼Huffman编码树

http://blog.csdn.net/fx677588/article/details/70767446 最近笔试老是遇到霍夫曼树,不过老是限于考研那会学的。最近的题感觉知道思路,就是写不对,现找一篇讲的比较好的,做一下备份。 ...

努力的C ⋅ 2017/10/13 ⋅ 0

JPG文件编解码详解——详细介绍编码和解码JPG

http://blog.csdn.net/zhengzhoudaxue2/article/details/7693258 JPEG文件编/解码详解 cat_ng 猫猫 JPEG(Joint Photographic Experts Group)是联合图像专家小组的英文缩写。它由国际电话与...

stn_lcd ⋅ 2017/11/24 ⋅ 0

数据结构:哈夫曼编码(php版)

演示网址:http://huffman.sinaapp.com/ 源文件下载地址:http://xiaocao.u.qiniudn.com/work/huffman-2013-12-19.zip 概述下: 哈夫曼树─即最优二叉树,带权路径长度最小的二叉树,经常应用...

BearCatYN ⋅ 2014/11/29 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

个人博客的运营模式能否学习TMALL天猫质量为上?

心情随笔|个人博客的运营模式能否学习TMALL天猫质量为上? 中国的互联网已经发展了很多年了,记得在十年前,个人博客十分流行,大量的人都在写博客,而且质量还不错,很多高质量的文章都是在...

原创小博客 ⋅ 今天 ⋅ 0

JavaScript零基础入门——(十一)JavaScript的DOM操作

JavaScript零基础入门——(十一)JavaScript的DOM操作 大家好,欢迎回到我们的JavaScript零基础入门。最近有些同学问我说,我讲的的比书上的精简不少。其实呢,我主要讲的是我在开发中经常会...

JandenMa ⋅ 今天 ⋅ 0

volatile和synchronized的区别

volatile和synchronized的区别 在讲这个之前需要先了解下JMM(Java memory Model :java内存模型):并发过程中如何处理可见性、原子性、有序性的问题--建立JMM模型 详情请看:https://baike.b...

MarinJ_Shao ⋅ 今天 ⋅ 0

深入分析Kubernetes Critical Pod(一)

Author: xidianwangtao@gmail.com 摘要:大家在部署Kubernetes集群AddOn组件的时候,经常会看到Annotation scheduler.alpha.kubernetes.io/critical-pod"="",以表示这是一个关键服务,那你知...

WaltonWang ⋅ 今天 ⋅ 0

原子性 - synchronized关键词

原子性概念 原子性提供了程序的互斥操作,同一时刻只能有一个线程能对某块代码进行操作。 原子性的实现方式 在jdk中,原子性的实现方式主要分为: synchronized:关键词,它依赖于JVM,保证了同...

dotleo ⋅ 今天 ⋅ 0

【2018.06.22学习笔记】【linux高级知识 14.4-15.3】

14.4 exportfs命令 14.5 NFS客户端问题 15.1 FTP介绍 15.2/15.3 使用vsftpd搭建ftp

lgsxp ⋅ 今天 ⋅ 0

JeeSite 4.0 功能权限管理基础(Shiro)

Shiro是Apache的一个开源框架,是一个权限管理的框架,实现用户认证、用户授权等。 只要有用户参与一般都要有权限管理,权限管理实现对用户访问系统的控制,按照安全规则或者安全策略控制用户...

ThinkGem ⋅ 昨天 ⋅ 0

python f-string 字符串格式化

主要内容 从Python 3.6开始,f-string是格式化字符串的一种很好的新方法。与其他格式化方式相比,它们不仅更易读,更简洁,不易出错,而且速度更快! 在本文的最后,您将了解如何以及为什么今...

阿豪boy ⋅ 昨天 ⋅ 0

Python实现自动登录站点

如果我们想要实现自动登录,那么我们就需要能够驱动浏览器(比如谷歌浏览器)来实现操作,ChromeDriver 刚好能够帮助我们这一点(非谷歌浏览器的驱动有所不同)。 一、确认软件版本 首先我们...

blackfoxya ⋅ 昨天 ⋅ 0

线性回归原理和实现基本认识

一:介绍 定义:线性回归在假设特证满足线性关系,根据给定的训练数据训练一个模型,并用此模型进行预测。为了了解这个定义,我们先举个简单的例子;我们假设一个线性方程 Y=2x+1, x变量为商...

wangxuwei ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部