哈夫曼编码(C++实现)

文章目录

  • 1. 前言
  • 2. 固定长度编码
  • 3. 哈夫曼编码
  • 4. 哈夫曼解码
  • 5. 编码特点
  • 6. 代码实现
  • 7. 总结


1. 前言

在上一篇文章中,介绍了 哈夫曼树的概念及其实现 。

哈夫曼树有什么用途呢? —— 那就是用来创建哈夫曼编码(Huffman Coding —— 一种二进制编码)。

哈夫曼编码是一种可以用于数据压缩的编码方式,比如你可以想象在 winrar 或 winzip 等压缩软件中采用这种压缩方式。而哈夫曼编码的构造过程是需要用到哈夫曼树。

2. 固定长度编码

哈夫曼编码主要解决通信双方传输信息时针对信息压缩问题,通过传输最少量的信息来表达一段相同的内容。

设想有一段文字内容 “AFDBCFBDEFDF” 要通过网络传给别人。

一般来说,传输一段信息时,往往采用二进制的 0 和 1(分别代表两种信号)来进行信息传输最便捷,所以考虑把要传输的这段文字内容进行编码。

因为这段文字内容只涉及了 A、B、C、D、E、F 共 6 个字母。而用 3 位二进制数表示(编码)一个字母,则足可以表示 8 个字母(从二进制的 000 到二进制的 111),所以用 3 位二进制数(字符)表达这段文字内容涉及的 6 个字母绰绰有余

如下图所示,注意,这属于固定长度编码:

在这里插入图片描述

在传输文字内容 “AFDBCFBDEFDF” 时,传输的数据就是编码后 000101011001010101001011100101011101

接收方可以按照双方事先的约定,也就是 3 位一划分来将二进制编码译码还原为真正的文字内容。但是如果传输的文字内容特别多,那么编码后的内容也将非常的长,这意味着传输的内容也会非常多。

事实上,在真正的数据传输中,不管传输的是英文字母、汉字等等,字母或者汉字出现的频率并不相同,比如在英文的 26 个字母中 “E、A、T、I、N、O” 出现的频率就会明显高于其他字母,而在汉字中 “有、人、的、工、在、一、是” 等出现的频率也会比其他汉字更高。

3. 哈夫曼编码

针对前面传输的文字内容 “AFDBCFBDEFDF” 中所包含的 6 个字母,可以粗略估算也可以假设它们出现的频率,按照出现频率一共 100% 计算,大略估计这 6 个字母的出现频率为 A:12%、B:15%、C:9%、D:24%、E:8%、F:32%。

有了这种估计,就可以按照哈夫曼树来重新进行编码规划 —— 将 A、B、C、D、E、F 这 6 个字母分别看做叶子节点,将这 6 个字母的百分比(去掉百分号)12、15、9、24、8、32 分别看做叶子节点的权值,这样就可以构造出一棵哈夫曼树。

如下图所示:

在这里插入图片描述

针对上图所展示的哈夫曼树,如果左分支路径中的各个段用 0 标示,右分支路径的各个段用 1 标示,换句话说,从根节点出发,向左走表示二进制的 0,向右走表示二进制 1,那么这种用二进制字符表示字母的方案就可以映射为树的表示形式。如下图所示:

在这里插入图片描述

从上图可以看到,从根节点出发,访问节点 D 需要经过的路径所包含的二进制数为 00,节点 E 经过的路径所包含的二进制数为 010……,这意味着 D 的编码是 00,E 的编码是 010……。

那么哈夫曼树的 叶子节点 所对应的二进制编码如下图所示(这些字母对应的二进制字符编码就是 哈夫曼编码)。

在这里插入图片描述

从上图中可以看到,出现频率最高的字母,尽可能用最短的编码以节省数据通信量,所以这是一种可变长度编码,也就是不同的字母编码后对应的二进制字符长度不同。

最终,要传输的文字内容是 “AFDBCFBDEFDF”,而实际传输的内容是编码后的 11010001110111011100010100010

可以与原来需要传输的二进制字符对比一下:

  • 原二进制字符串:000101011001010101001011100101011101(36 个字符)
  • 新二进制字符串:11010001110111011100010100010(29 个字符)

这意味着需要传输的数据变少了,也就是数据被压缩了。节省了大概 19% 的保存或传输成本。显然,如果要传输的文字内容更多,所节省的成本也将更加可观。

4. 哈夫曼解码

那么如何从新的二进制字符串中把真正的文字内容解码出来呢?因为编码中只有 0 和 1,而且是一种可变长度的编码,在解码时其实是容易因混淆而导致解码错误的,所以,对于可变长度的编码,设计时必须保证任何一个字母的编码都不可以是另一个字母编码的前缀。

比如字母 F 的二进制编码是 10,那么其他字母在编码时绝对不可以以 10 开头,观察上=下图,字母 A、B、C、D、E 的二进制字符都不是以 10 开头。

在这里插入图片描述

这里涉及一个概念:前缀编码

  • 如果在一个编码方案中,任何一个编码都不是其他任何编码的前缀(最左子串),则称该编码是前缀编码。

哈夫曼编码就属于一种前缀编码。

举个例子,假设字母 C 的二进制编码不是 011 而是 101,因为以 10 开头了是不被允许的,那么如果传输的内容是 10110110,接收方在解码时可能会解码为 CCF,也可能会解码为 FAA,这样就产生了歧义和混乱。

而按照上图这样编码,在收到新二进制字符串时,解码出来的内容只能是 “AFDBCFBDEFDF”,绝不会解码成其他内容。当然,为了保证发送方发送的内容接收方能够成功解码,接收方手中也必须有一份上图所示的编码表。

5. 编码特点

哈夫曼编码是用构造哈夫曼树的方法来确定字符集的一种编码方案,属于一种前缀编码,在解码时可以保证解出的内容的唯一性。

  • 字符集中的每一个字符作为叶子节点,将各个字符出现的频率作为该节点的权值,构造出哈夫曼树。
  • 将哈夫曼树左分支路径中的各个段用 0 标示,右分支路径中的各个段用 1 标示。当然,左分支用 1 标示,右分支用 0 标示也可以,只要通信双方在编码和解码时做好一致的约定就可以。
  • 从哈夫曼树的根节点到叶子节点所经过的各段路径所对应的 0 或者 1 连接起来就构成了字符的哈夫曼编码。

因为哈夫曼树具有不唯一性,因此哈夫曼编码也是不唯一的。构建哈夫曼树时,有些资料上会建议左孩子节点的权值应该不大于右孩子节点的权值,或者要求左孩子与右孩子节点权值大小关系应该保持一致。

换句话说,就是要么保证所有左孩子节点权值小于或等于右孩子节点权值,要么保证所有右孩子节点权值小于或者等于左孩子节点权值(不需要保持左右孩子节点权值大小关系的一致性)。

6. 代码实现

哈夫曼编码的实现代码可以直接放在上篇文章中的 HFMTree 类中实现,增加 public 修饰的成员函数即可。

//生成哈夫曼编码
bool CreateHFMCode(int idx) //参数idx是用于保存哈夫曼树的数组某个节点的下标
{//调用这个函数时,m_length应该已经等于整个哈夫曼树的节点数量,那么哈夫曼树的叶子节点数量应该这样求int leafNodeCount = (m_length + 1) / 2;if (idx < 0 || idx >= leafNodeCount){//只允许对叶子节点求其哈夫曼编码return false;}string result = ""; //保存最终生成的哈夫曼编码int curridx = idx;int tmpparent = m_data[curridx].parent;while (tmpparent != -1) //沿着叶子向上回溯{if (m_data[tmpparent].lchild == curridx){//前插0result = "0" + result;}else{//前插1result = "1" + result;}curridx = tmpparent;tmpparent = m_data[curridx].parent;} //end whilecout << "下标为【" << idx << "】,权值为" << m_data[idx].weight << "的节点的哈夫曼编码是" << result << endl;return true;
}

在主函数中增加测试样例

//哈夫曼编码测试
int main()
{int weigh[] = { 12,15,9,24,8,32 };int sz = sizeof(weigh) / sizeof(weigh[0]);//分别传入:权值列表中元素个数 和 权值列表首地址HFMTree hfmt(sz, weigh);hfmt.CreateHFMTree(); //创建哈夫曼树hfmt.preOrder(hfmt.GetLength() - 1); //遍历哈夫曼树,参数其实就是根节点的下标(数组最后一个有效位置的下标)//求哈夫曼编码cout << "--------------" << endl;for (int i = 0; i < sz; ++i)hfmt.CreateHFMCode(i);return 0;
}

测试结果如下:

在这里插入图片描述

请注意,该结果与上图所展示的哈夫曼编码结果不完全一样,这是因为程序编码中哈夫曼树的构建规则完全遵照 “哈夫曼树左孩子节点的权值不大于右孩子节点的权值”,而上面图中的哈夫曼树并没有遵照这个规则构建(例如节点 24 和 17 结合的时候,还有节点 32 和 27 结合的时候)。

7. 总结

哈夫曼树是用来创建哈夫曼编码的。哈夫曼编码是一种可以用于数据压缩的编码方式,哈夫曼编码的构造过程需要用到哈夫曼树。

思考:英文的 26 个字母使用的频率是不一样的,这 26 个字母的使用频率数据可以通过搜索引擎来搜索。如果要对这 26 个字母进行哈夫曼编码,计算一下使用哈夫曼编码可以对数据压缩多少?

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/108172.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

IDEA软件安装包分享(附安装教程)

目录 一、软件简介 二、软件下载 一、软件简介 IntelliJ IDEA是一款流行的Java集成开发环境&#xff08;IDE&#xff09;&#xff0c;由捷克软件开发公司JetBrains开发。它专为Java开发人员设计&#xff0c;提供了许多高级功能和工具&#xff0c;使得开发人员能够更高效地编写…

识别图片中的文字

前言 PearOCR 是一款免费无限制网页版文字识别工具。 优点如下&#xff1a; 免费&#xff1a;完全免费&#xff0c;没有任何次数、大小限制&#xff0c;可以无限使用&#xff1b; 安全&#xff1a;全部数据本地运算&#xff0c;所有图片均不会被上传&#xff1b; 智能&#xf…

数仓--------简单了解

作者前言 &#x1f382; ✨✨✨✨✨✨&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f367;&#x1f382; ​&#x1f382; 作者介绍&#xff1a; &#x1f382;&#x1f382; &#x1f382; &#x1f389;&#x1f389;&#x1f389…

【坑】Vue中带有__ob__: Observer的数组无法遍历的问题

控制台可以打印出数据但是渲染不出结构 解决办法&#xff1a; setTimeout(() > {Bus.$emit(shareRes, this.result.filter(item > item.id id)) }, 500)替换 Bus.$emit(shareRes, this.result.filter(item > item.id id))总结 解决和总结 好像和__ob__.Observe无…

Android 11/12 app-lint 系统Update-API时Lint检查问题

有以下两种解决方法 1. 加SupressLint注解 这种方式你可以其他博客也有 但是要每个类和方法都加上SuppressLint 太麻烦了 我才不要这样呢 2. 添加 --api-lint-ignore-prefix 参数直接跳过代码检查 1. 打开 frameworks/base/Android.bp 文件 2. 搜索找到这个字段 metalava…

简述docker映射(Mapping)和挂载(Mounting)

映射的概念&#xff1a; 将容器内的端口映射到主机的端口上&#xff0c;这样就可以通过主机的网络接口与容器内部进行通信。主机上对应端口的请求会被转发到容器内部&#xff0c;从而实现对容器内部程序的通信访问&#xff08;注意&#xff01;这里提到的容器内部的端口并不一定…

PDFPrinting.Net Crack

PDFPrinting.Net Crack 它能够轻松灵活地预测完美的打印结果以及用户文件的示例性显示。在.NET的PDF打印中&#xff0c;可以快速浏览最关键的元素。如果用户需要获得更详细的概述&#xff0c;那么他可以查看快速入门手册&#xff0c;甚至现有文档的详细概述参考。 在这种情况下…

Maven聚合项目(微服务项目)创建流程,以及pom详解

一、创建流程 1、首先创建springboot项目作为父项目 只留下pom.xml 文件&#xff0c;删除src目录及其他无用文件 2、创建子项目 子项目可以是maven项目&#xff0c;也可以是springboot项目 3、父子项目关联 4、父项目中依赖管理 <?xml version"1.0" encoding…

为什么选择elasticsearch分布式搜索引擎

文章目录 &#x1f52d;什么是elasticsearch&#x1f320;ELK技术栈&#x1f320;elasticsearch和lucene&#x1f320;为什么不是其他搜索技术&#xff1f; &#x1f320;总结 &#x1f52d;什么是elasticsearch elasticsearch是一款非常强大的开源搜索引擎&#xff0c;具备非常…

C语言之函数题

目录 1.乘法口诀表 2.交换两个整数 3.函数判断闰年 4.函数判断素数 5.计算斐波那契数 6.递归实现n的k次方 7.计算一个数的每位之和&#xff08;递归&#xff09; 8.字符串逆序&#xff08;递归实现&#xff09; 9.strlen的模拟&#xff08;递归实现&#xff09; 10.求…

基于springboot学生社团管理系统/基于Java的高校社团管理系统的设计与实现

摘 要 随着信息技术和网络技术的飞速发展&#xff0c;人类已进入全新信息化时代&#xff0c;传统管理技术已无法高效&#xff0c;便捷地管理信息。为了迎合时代需求&#xff0c;优化管理效率&#xff0c;各种各样的管理系统应运而生&#xff0c;各行各业相继进入信息管理时代&…

蚂蚁 SOFAServerless 微服务新架构的探索与实践

赵真灵&#xff08;有济&#xff09; 蚂蚁集团技术专家 Serverless 和微服务领域专家曾负责基于 K8s Deployment 的应用发布运维平台建设、K8s 集群的 Node/pod 多级弹性伸缩与产品建设。当前主要负责应用架构演进和 Serverless 相关工作。同时也是 SOFAArk 社区的开发和维护者…

搭建开发环境-WSL+Ubuntu(一键搭建开发环境)

概述 所谓工欲善其事必先利其器&#xff0c;搭环境往往是开发过程中卡出很多初学者的拦路虎。 对于很多老鸟来说&#xff0c;很多东西都已经习惯成自然&#xff0c;也就没有刻意和初学者说。但对于很多初学者&#xff0c;却是受益良多。 这个系列&#xff0c;先从操作系统开始…

fegin实现方法级别注解超时配置

fegin实现方法级别注解超时配置 测试的3.18新版本已经支持方法中参数带有Options 也可以自定义配置, Options options findOptions(argv);; 使用该注解方式需配合AOP使用! 原理是包装自己的client客户端, 替换框架的客户端! 应用到生产环境需自己充验证测试 1.0 注解 Target(…

C# .aspx网页获取RFID读卡器HTTP协议提交的访问文件Request获得卡号、机号,Response回应驱动读卡器显示响声

本示例使用的设备&#xff1a;RFID网络WIFI无线TCP/UDP/HTTP可编程二次开发读卡器POE供电语音-淘宝网 (taobao.com) 服务端代码&#xff1a; using System; using System.Collections.Generic; using System.Linq; using System.Web; using System.Web.UI; using System.Web.…

【QT】重写QAbstractLIstModel,使用ListView来显示多列数据

qt提供了几个视图来进行信息的列表显示&#xff0c;QListView可以用来显示继承QStractListModel的字符串列表中的字符串&#xff0c;默认的模型里面只包含一列的内容&#xff1a; 这里以qml为例子&#xff0c;先新建一个qml的项目&#xff0c;示例代码如下&#xff1a; 先创建一…

深度学习3. 强化学习-Reinforcement learning | RL

强化学习是机器学习的一种学习方式&#xff0c;它跟监督学习、无监督学习是对应的。本文将详细介绍强化学习的基本概念、应用场景和主流的强化学习算法及分类。 目录 什么是强化学习&#xff1f; 强化学习的应用场景 强化学习的主流算法 强化学习(reinforcement learning) …

产品经理的六步路线图:快速制定你的产品计划

2023年的软件世界比以往任何时候都发展得更快&#xff0c;并充满了各种变量。而这将会以各种方式影响产品路线图的落地执行与实现。随着问题越来越多&#xff0c;世界需要不断发展的解决方案。因此&#xff0c;本文结合产品路线图当前存在的共性问题&#xff0c;借鉴企业的成功…

wxpython:wx.html2 是好用的 WebView 组件

wxpython : wx.html2 是好用的 WebView 组件。 wx.html2 是wxPython扩展模块中封装得干净漂亮的模块之一&#xff0c;它被设计为允许为每个端口创建多个后端&#xff0c;尽管目前只有一个可用。它与wx.html.HtmlWindow 的不同之处在于&#xff0c;每个后端实际上都是一个完整的…

图像检索,目标检测map的实现

一、图像检索指标Rank1,map 参考&#xff1a;https://blog.csdn.net/weixin_41427758/article/details/81188164?spm1001.2014.3001.5506 1.Rank1: rank-k&#xff1a;算法返回的排序列表中&#xff0c;前k位为存在检索目标则称为rank-k命中。 常用的为rank1&#xff1a;首…