首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法:哈夫曼编码(Huffman Coding)

算法:哈夫曼编码(Huffman Coding)

作者头像
WEBJ2EE
发布于 2019-07-19 04:35:45
发布于 2019-07-19 04:35:45
2.7K0
举报
文章被收录于专栏:WebJ2EEWebJ2EE

1. 哈夫曼编码?

  • 是 Huffman 于 1952 年提出一种编码方法。
  • 是一种无损编码方式,是可变字长编码 (VLC) 的一种。
  • 编码策略基于信源的概率统计模型:出现概率大的信源符号编长码,出现概率小的信源符号编短码,从而使平均码长最短。
  • 编码属于“无前缀编码”,即:任一字符的编码都不是另一个字符编码的前缀。
  • 可借助“最优二叉树(Huffman )”实现;
  • 常应用于数据压缩。

2. 最优二叉树?

  • 路径:树中一个结点到另一个结点之间的分支序列
  • 路径长度:路径上的分支数目
  • 树的路径长度:树根到每个结点的路径长度的和;
  • 结点带权路径长度:结点到树根的路径长度与结点的权的乘积;
  • 树的带权路径长度:树中所有叶子结点的带权路径长度之和(WPL);
  • 最优二叉树:WPL最小 的二叉树;

最优二叉树构造过程:

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

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

图1

  • 在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
  • 从森林中删除选取的两棵树,并将新树加入森林;

图2

  • 重复上面 2 步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树。

图3

图4

图5:最优二叉树构造完成

3. 哈夫曼编解码过程?

编码:

  1. 读入待编码源文件;
  2. 第一次扫描:统计文件中各字符的出现频率;
  3. 构建 Huffman 树;
  4. 遍历 Huffman 树,获得各字符的码表;
  5. 第二次扫描:对源文件的每个字符编码;

解码:

  1. 读入编码后的文件;
  2. 获取 Huffman 树;
  3. 从根节点开始依据从文件中读取的 Huffman 码值沿树行走,至叶结点时完成一个字符的解码,并返回根节点;
  4. 重复上述过程,完成所有字符的解码;

4. 程序代码?

例:用哈夫曼编码压缩字符串 “ABCACCDAEAE”;

图:编码过程构建的最优二叉树

图:JS 代码

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-03-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 WebJ2EE 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
哈夫曼树和哈夫曼编码
  在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i
mukekeheart
2018/02/27
2K0
哈夫曼树和哈夫曼编码
数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现
0. 数据结构图文解析系列 数据结构系列文章 数据结构图文解析之:数组、单链表、双链表介绍及C++模板实现 数据结构图文解析之:栈的简介及C++模板实现 数据结构图文解析之:队列详解与C++模板实现 数据结构图文解析之:树的简介及二叉排序树C++模板实现. 数据结构图文解析之:AVL树详解及C++模板实现 数据结构图文解析之:二叉堆详解及C++模板实现 数据结构图文解析之:哈夫曼树与哈夫曼编码详解及C++模板实现 数据结构图文解析之:直接插入排序及其优化(二分插入排序)解析及C++实现 1. 哈夫曼编码简
Tencent JCoder
2018/07/02
1.1K0
4.5.3 哈弗曼树(Huffman)树和哈弗曼编码
树中结点被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点上权值的乘积称为该结点的带权路径长度。树中所有叶结点的带权路径长度之和称为该树的带权路径长度,记为
week
2018/08/24
5230
哈夫曼树的详细讲解(手把手教学)
哈夫曼树又称为最优树,是一类带权路径长度最短的树,应用光泛。 在学习哈夫曼树的时候,我们来先引入路径和路径长度的概念。 ***1.1路径:***从树中的一个结点到另一个结点的之间的分支构成的。 ***1.2路径长度:***路径上的分支数目。 ***1.3树的路径长度:***从树根到每一个结点的路径长度之和 结点的带权路径长度:从该结点到树根之间的路径长度与结点上的权值的乘积 ***1.4树的带权路径长度:***树中所有叶子结点的·带权路径长度之和,也就是WPL,WPL=每一个结点的对应的权值乘以对应的路径长度之和。 注意: 1.满二叉树不一定是哈夫曼树 2.哈夫曼树中权值越大的叶子结点离根越近 3.具有相同带权结点的哈夫曼树不惟一 4.在结点相同的二叉树中,完全二叉树是路径长度最短的二叉树。
洁洁
2023/10/10
8680
哈夫曼树的详细讲解(手把手教学)
数据结构 Huffman树
Huffman 介绍 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点
Kindear
2017/12/29
1.5K0
数据结构 Huffman树
带权树 -- 哈夫曼树,与它的那张哈夫曼编码表
现在假设a处于0~60的概率为0.1 60~70:0.3 70~80:0.4 80~90:0.15 大于90:0.05
看、未来
2020/08/26
1.2K0
带权树 -- 哈夫曼树,与它的那张哈夫曼编码表
哈夫曼树与哈夫曼编码:聪明的数据压缩技术
👋 你好,我是 Lorin 洛林,一位 Java 后端技术开发者!座右铭:Technology has the power to make the world a better place.
Lorin 洛林
2023/11/14
1.2K1
哈夫曼树与哈夫曼编码:聪明的数据压缩技术
哈夫曼树(最优二叉树)的概念以及构造
在实际生活和生产应用中,我们往往会遇到综合比较一系列的离散量的问题;比如说车站根据包裹的重量以及旅途的长短来确定携带行李的价格,或者我们根据一定的重量范围来给一箱铁球进行分类。这一类问题的解决思路是: 1、 根据实际需要划分出分类的标准; 2、 按一定的顺序(算法)将实际的数据归到相应的类别里。 一般情况下,我们所确定的分类标准并不能保证每一类的数据量是平均分配的;也就是说,由于每一类数据出现的概率不同,造成当采用不同的算法时所需的运算次数的不同。当然,在实际生产生活中,我们更希望得到一种最快,最简洁同时也不会产生歧义的算法。在这个背景下,哈夫曼树以及哈夫曼算法应运而生。
SingYi
2022/07/13
8120
数据结构——HuffmanTree
Huffman tree 基本术语 路径和路径长度 - 路径:在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路。 - 结点的路径长度:从一个结点到另一个结点的路径上分支的数目。 结点的权及带权路径长度 - 结点的权:将树中结点赋予一个有着某种含义的数值。 - 结点的带权路径长度:从根结点到该结点之间的路径长度与该结点的权的乘积。 树的带权路径长度 - 树中所有叶子结点的带权路径长度之和。 赫夫曼树( Huffman tree ) - 带权路径长度达到最小的二叉树即为赫夫曼
ruochen
2021/06/29
2590
数据结构——HuffmanTree
最优二叉树—哈夫曼(huffman)树
ASL=(1+2*2+3)/4=2            ASL=(1+2+3+4)/4=2.5
一条晒干的咸鱼
2024/11/19
3420
最优二叉树—哈夫曼(huffman)树
原以为哈夫曼树、哈夫曼编码很难,结果……
哈夫曼树、哈夫曼编码很多人可能听过,但是可能并没有认真学习了解,今天这篇就比较详细的讲一下哈夫曼树。
main方法
2021/07/19
6930
原以为哈夫曼树、哈夫曼编码很难,结果……
【数据结构】建立二叉树以及哈夫曼树及哈夫曼编码
文章目录 5.4.1 方式 5.4.2 由先根和中根遍历序列建二叉树 5.4.3 由后根和中根遍历序列建二叉树 5.4.4 由标明空子树的先根遍历建立二叉树 5.4.5 由完全二叉树的顺序存储结构建立二叉链式存储结构 5.5 哈夫曼树及哈夫曼编码 5.5.1 基本概念 5.5.2 最优二叉树 5.5.3 构建哈夫曼树 5.5.4 哈夫曼编码 5.5.5 哈夫曼编码类 5.4.1 方式 四种方式可以建立二叉树 由先根和中根遍历序列建二叉树 由后根和中根遍历序列建二叉树 由标明空子树的先根遍
陶然同学
2023/02/26
1.1K0
【数据结构】建立二叉树以及哈夫曼树及哈夫曼编码
哈夫曼树
哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径
Java架构师必看
2021/12/27
7460
《大话数据结构》树以及赫夫曼编码的例子
第六章 树 6.2 树的定义 树(Tree)的n个结点的有限集。当n=0时,称为空树。 任意一个非空树中: 1)有且仅有一个特定的称为根(root)的结点 2)当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1、T2 …… 、Tm。其中每个集合本身又是一棵树,并且称为根的子树(SubTree)。 注意: 1)n>0时根节点的唯一的,不可能存在多个根节点。 2)m>0时,字数的个数没有限制,但是它们一定是互不相交的。 6.2.1 结点分类 结点拥有的子树个数称为结点的度(Degree)。 度为0的结
xcywt
2018/03/28
1K0
《大话数据结构》树以及赫夫曼编码的例子
产品能力|算法基础-哈夫曼树14天阅读挑战赛
趣味算法(第二版)读书笔记: day1: 序章|学习的方法和目标. day2:算法之美|打开算法之门与算法复杂性 day3.算法之美|指数型函数对算法的影响实际应用 day4.数学之美|斐波那契数列与黄金分割 day5.算法基础|贪心算法基础 day6.算法基础||哈夫曼树 day7.算法基础||堆栈和队列
破晓之翼
2022/11/18
4390
产品能力|算法基础-哈夫曼树14天阅读挑战赛
数据结构与算法 -判定树和哈夫曼树
判定树是用于描述分类过程的二叉 树,每个非终端结点包含一个条件,对应一次比较;每个终端结点 包含一个种类标记, 对应于一种分类结果。
越陌度阡
2020/11/26
1.4K0
数据结构与算法 -判定树和哈夫曼树
经典算法之最优二叉树
我想学过数据结构的小伙伴一定都认识哈夫曼,这位大神发明了大名鼎鼎的“最优二叉树”,为了纪念他呢,我们称之为“哈夫曼树”。哈夫曼树可以用于哈夫曼编码,编码的话学问可就大了,比如用于压缩,用于密码学等。今天一起来看看哈夫曼树到底是什么东东。
用户3467126
2019/11/27
1.5K0
数据结构09 哈夫曼树
这一篇要总结的是树中的哈夫曼树(Huffman Tree),我想从以下几点对其进行总结: 1、什么是哈夫曼树 2、如何构建哈夫曼树 3、哈夫曼编码 4、代码实现 1、什么是哈夫曼树 什么是哈夫曼树
nnngu
2018/03/15
8030
数据结构09 哈夫曼树
哈夫曼树【最优二叉树】【Huffman】
        在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率。例如,编制一个程序,将百分制转换成五个等级输出。大家可能认为这个程序很简单,并且很快就可以用下列形式编写出来:
瑾诺学长
2018/09/21
2.4K0
哈夫曼树【最优二叉树】【Huffman】
数据结构(15)–哈夫曼树以及哈夫曼编码的实现「建议收藏」
大家好,我是架构君,一个会写代码吟诗的架构师。今天说一说数据结构(15)--哈夫曼树以及哈夫曼编码的实现「建议收藏」,希望能够帮助大家进步!!!
Java架构师必看
2022/10/05
2.9K0
数据结构(15)–哈夫曼树以及哈夫曼编码的实现「建议收藏」
相关推荐
哈夫曼树和哈夫曼编码
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档