文档章节

哈夫曼树和哈夫曼编码

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
朝阳
程序员
私信 提问
哈夫曼树的构建、编码以及带权路径长计算

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

勉旃
09/17
0
0
数据结构与算法之9(哈夫曼编解码与广度优先搜索)

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

kkae8643150
2017/11/27
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

没有更多内容

加载失败,请刷新页面

加载更多

Netty 备录 (一)

入职新公司不久,修修补补1个月的bug,来了点实战性的技术---基于netty即时通信 还好之前对socket有所使用及了解,入手netty应该不是很难吧,好吧,的确有点难,刚看这玩意的时候,可能都不知道哪里...

_大侠__
昨天
4
0
Django简单介绍和用户访问流程

Python下有许多款不同的 Web 框架。Django是重量级选手中最有代表性的一位。许多成功的网站和APP都基于Django。 Django是一个开放源代码的Web应用框架,由Python写成。 Django遵守BSD版权,初...

枫叶云
昨天
8
0
EOS错误代码及中文释义

本文集汇总了EOS区块链常见错误代码及其含义,完整错误代码集请查看 EOS错误代码集 - 汇智网 EOS错误代码列表如下, <table class="table table-striped"> <thead> <tr><th>错误代码</th><t......

汇智网教程
昨天
4
0
Spring Cloud Stream消费失败后的处理策略(四):重新入队(RabbitMQ)

应用场景 之前我们已经通过《Spring Cloud Stream消费失败后的处理策略(一):自动重试》一文介绍了Spring Cloud Stream默认的消息重试功能。本文将介绍RabbitMQ的binder提供的另外一种重试...

程序猿DD
昨天
5
0
kiss原则

KISS 原则是用户体验的高层境界,简单地理解这句话,就是要把一个产品做得连白痴都会用,因而也被称为“懒人原则”。换句话说来,”简单就是美“。KISS 原则源于 David Mamet(大卫马梅)的电...

NB-One
昨天
14
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部