首页 > 其他分享 >18.哈夫曼编码

18.哈夫曼编码

时间:2023-06-25 22:25:26浏览次数:30  
标签:编码 哈夫曼 18 埃利奥特 卡利斯 普雷斯顿 梅尔斯 帕特森

哈夫曼(Huffman)编码算法是基于二叉树构建编码压缩结构的,它是数据压缩中经典的一种算法。算法根据文本字符出现的频率,重新对字符进行编码。
首先请大家阅读下面两段中外小学作文:
中国- 今天天气晴朗,我和小明出去玩!小明贪玩,不小心摔了一跤,小明被摔得哇哇哭了,小明的爸爸闻声赶来,又把小明痛扁了一阵。小明的小屁屁都被揍扁了,因为小明把妈妈刚买给他的裤子弄破了!

外国- 今天天气晴朗,我和乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿出去玩!乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿贪玩,不小心摔了一跤,乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿被摔得哇哇哭了,乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿的爸爸闻声赶来,又把乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿痛扁了一阵。乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿的小屁屁都被揍扁了,因为乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿把妈妈刚买给他的裤子弄破了!

同一段内容,当小明换成了外国小朋友的名字,篇幅就增加了几倍,有没有办法把内容缩减呢?
当然有!在文章的开头,先声明一个缩写:

名字 缩写
乔伊·亚历山大·比基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱士·普雷斯顿 乔顿

那么,上面这段文字就可以缩成很小的一段:
今天天气晴朗,我和乔顿出去玩!乔顿贪玩,不小心摔了一跤,乔顿被摔得哇哇哭了,乔顿的爸爸闻声赶来,又把小明痛扁了一阵。乔顿的小屁屁都被揍扁了,因为乔顿把妈妈刚买给他的裤子弄破了!

哈夫曼编码就是这样一个原理!按照文本字符出现的频率,出现次数越多的字符用越简短的编码替代,因为为了缩短编码的长度,我们自然希望频率越高的词,编码越短,这样最终才能最大化压缩存储文本数据的空间。

哈夫曼编码举例: 假设要对“we will we will r u”进行压缩。

压缩前,使用ASCII 码保存:

119 101 32 119 105 108 108 32 119 101 32 119 105 108 108 32 114 32 117

共需: 19 个字节-152 个位保存

下面我们先来统计这句话中每个字符出现的频率。如下表,按频率高低已排序:

字符 空格 w l e i r u
频率 5 4 4 2 2 1 l

接下来,我们按照字符出现的频率,制定如下的编码表:

字符 l w 空格 e i u r
频率 00 01 10 110 1111 11100 11101

这样,“we will we will r u”就可以按如下的位来保存:

01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100

1.哈夫曼二叉树构建

1.1按出现频率高低将其放入一个数组中,从左到右依次为频率逐渐增加


1.2从左到右进行合并,依次构建二叉树。第一步取前两个字符u 和r 来构造初始二叉树,第一个字符作为左节点,第二个元素作为右节点,然后两个元素相加作为新的空元素,并且两者权重相加作为新元素的权重。

1.3新节点加入后,依据权重重新排序,按照权重从小到大排列,上图已有序。

1.4红色区域的新增元素可以继续和i合并,如下图所示:

1.5合并节点后, 按照权重从小到大排列,如下图所示。

1.6排序后,继续合并最左边两个节点,构建二叉树,并且重新计算新节点的权重

1.7重新排序

1.8重复上面步骤6 和7,直到所有字符都变成二叉树的叶子节点






参考资料来源:

奇牛学院

标签:编码,哈夫曼,18,埃利奥特,卡利斯,普雷斯顿,梅尔斯,帕特森
From: https://www.cnblogs.com/codemagiciant/p/17504122.html

相关文章

  • 假期周进度报告1(6.18-6.24)
    6.18我已经分配了算法与数据结构的一阶段小组,和德民,垚基,旭彤我们分工明确,1. 7-2关键路径 2.7-5哈夫曼编码译码3.7-10寻找大富翁4. 7-11二路归并排序我分到了这四个题目在今天完成了关键路径的问题6.19今天尽力完成最终关键路径的问题,开始了哈夫曼编码译码的题目。创......
  • CodeForces 1842E Tenzing and Triangle
    洛谷传送门CF传送门一个很显然的观察:选择的三角形两两重叠面积为\(0\),否则合并更优。考虑dp,设\(f_i\)为删完\(x_j\gei\)的所有点的最小花费。转移就枚举选择的三角形直角边长\(l\),那么\(f_i=\min(f_{i+1}+\sum\limits_{x_p=i}c_p,\min\limits_lf_{i+l}......
  • CodeForces 1842G Tenzing and Random Operations
    洛谷传送门CF传送门原来还不会这种拆期望的套路设\(b_j\)为第\(j\)次操作中选择的\(i\),所求即为\(E(\prod\limits_{i=1}^n(a_i+\sum\limits_{j=1}^m[b_j\lei]\timesv))\)。乘法也可以考虑拆期望。我们有最基础的性质\(E((a+b)\times(c+d))=E(ac)......
  • 代码审计——硬编码口令/弱口令详解
    01漏洞描述根据网站所使用的第三方组件,寻找特定的弱口令或默认口令进行登录。或在代码层面寻找写死的账号口令,尝试进行登录。02审计要点对前端源代码以及系统后台代码进行全文关键字检索,如key、pass、pwd、password,查看是否存在明文显示的账号密码。03漏洞案例源码中某前端js......
  • 189. 旋转数组
    给定一个整数数组nums,将数组中的元素向右轮转k个位置,其中k是非负数。示例1:输入:nums=[1,2,3,4,5,6,7],k=3输出:[5,6,7,1,2,3,4]解释:向右轮转1步:[7,1,2,3,4,5,6]向右轮转2步:[6,7,1,2,3,4,5]向右轮转3步:[5,6,7,1,2,3,4]本题思路一致https://......
  • 刷新20项代码任务SOTA,Salesforce提出新型基础LLM系列编码器-解码器Code T5+
    前言 大型语言模型(LLMs)最近在代码层面的一系列下游任务中表现十分出彩。通过对大量基于代码的数据(如GitHub公共数据)进行预训练,LLM可以学习丰富的上下文表征,这些表征可以迁移到各种与代码相关的下游任务。但是,许多现有的模型只能在一部分任务中表现良好,这可能是架构和......
  • 国标GB28181协议客户端开发(二)程序架构和注册
    国标GB28181协议客户端开发(二)程序架构和注册本系列文章旨在探讨国标GB28181协议设备端的开发过程。本文将聚焦于架构设计和设备注册,并详细介绍了设备端的程序架构设计、exosip库介绍和接口分类,以及GB28181设备端的注册流程和信令交互报文。通过阅读本文,读者将深入了解GB28181协......
  • CodeForces 1842F Tenzing and Tree
    洛谷传送门CF传送门事实上自己方向一直是错的……绝对值不好弄,我一开始的想法是直接去绝对值,但是不可避免地要\(O(n^3)\)。考虑我们直接钦定黑点重心为根,设这个根为\(r\),设\(sz_i\)为\(i\)子树内黑点数,由重心的性质,可以直接去绝对值,也就是说答案为\(\sum\limits_{i\n......
  • 处理致远OA应付科目编码不显示问题,同样适用于付款单选择款项类型后无科目带出
    情况如下:当我们选择预付款时,无任何科目带出 这是由于我们U8的应付设置--基本科目设置中,没有设置预付款对应科目,处理方法如下图,添加上预付款对应科目即可。  ......
  • 语音信号的哈夫曼编码压缩解压缩算法matlab仿真,输出编码后数据大小,编码树等指标
    1.算法仿真效果matlab2022a仿真结果如下:     2.算法涉及理论知识概要        利用哈夫曼编码进行信息通信可以较大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码;在接收端将传来的数据进行译码......