程序员经验分享-hwhale

详细图解哈夫曼Huffman编码树

2023-05-16

1 引言

　　哈夫曼（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位的内存空间去存储这些数据。
　　很显然直接ASCII码编码是很浪费空间的，Unicode就更不用说了，下面我们先来统计一下这句话中每个字符出现的频率。如下表，按频率高低已排序：


这里写图片描述

2 哈夫曼二叉树构建

2.1 初始队列

　　那么我们按出现频率高低将其放入一个优先级队列中，从左到右依次为频率逐渐增加。


这里写图片描述

　　下面我们需要将这个队列转换成哈夫曼二叉树，哈夫曼二叉树是一颗带权重的二叉树，权重是由队列中每个字符出现的次数所决定的。并且哈夫曼二叉树始终保证权重越大的字符出现在越高的地方。

2.2 第一步合并

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


这里写图片描述

　　同理，新元素可以和字符i再合并，如下：

这里写图片描述

2.3 重新调整队列

　　上图新元素权重相加后结果是变大了，需要对权重进行重新排序。


这里写图片描述

　　然后再依次从左到右合并，每合并一次则进行一次队列重新排序调整。如下：

这里写图片描述

　　经过多步操作之后，得到以下的哈夫曼二叉树结构，也就是一个带有权重的二叉树：

这里写图片描述

2.4 哈夫曼编码

　　有了上面带权重的二叉树之后，我们就可以进行编码了。我们把二叉树分支中左边的支路编码为0，右边分支表示为1，如下图：


这里写图片描述

　　这样依次遍历这颗二叉树就可以获取得到所有字符的编码了。例如：‘ ’的编码为10，‘l’的编码为00，‘u’的编码为11100等等。经过这个编码设置之后我们可以发现，出现频率越高的字符越会在上层，这样它的编码越短；出现频率越低的字符越会在下层，编码越短。经过这样的设计，最终整个文本存储空间才会最大化的缩减。
　　最终我们可以得到下面这张编码表：

这里写图片描述

2.5 字符串编码

　　有了上面的编码表之后，”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。这样最终我们只需50位内存，比原ASCII码表示节约了2/3空间，效果还是很理想的。当然现实中不是简单这样表示的，还需要考虑很多问题。

3 补充

　　我们需要弄明白哈夫曼二叉树概念，它是带权路径达到最小的二叉树，也叫最优二叉树。它不一定是完全二叉树，也不一定是平衡二叉树，它们描述的完全不是一件事情，完全没有概念上的重叠关系。

　　个人学习记录，由于能力和时间有限，如果有错误望读者纠正，谢谢！
　　转载请注明出处：http://blog.csdn.net/fx677588/article/details/70767446

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

详细图解哈夫曼Huffman编码树 的相关文章

  • 超棒的离线文档阅读器：Zeal

    前言 xff1a 大家写代码的时候总会有些方法或者属性不太清楚 xff0c 这时候我们就会打开浏览器 xff0c 然后找官方api或者直接搜索引擎找对应问题 xff0c 无疑花费了大量的时间 所以 xff0c 你需要一个桌面应用Zeal x

  • UITabBarController标签控制器相关设置

    1 根据下标索引以及控制器索引显示需要显示的控制器 self selectedIndex 61 sender tag 100 self selectedViewController 61 VC 2 设置标签控制器下面的文字 这里是设置系统自

  • Node App: Note命令行应用程序

    此程序需安装npm 第三方库yargs 解析命令行参数 xff0c chalk 输出特定样式的文本 安装版本如下 xff1a chalk 4 1 1 yargs 17 0 1 Note 应用程序支持 4个命令 xff1a add 添加一个n

  • 怎么样用批处理来创建一个txt文件

    怎么样用批处理来创建一个txt文件 cd gt test txt cd 表示切换到当前目录 xff0c 这个命令没有任何作用 gt 是重定向符 xff0c 将当前输出重定向到文件 这个命令创建一个名为test txt的空文件

  • STM32F103寄存器方式点亮LED流水灯

    一 设计思路 本实验使用GPIOB GPIOC GPIOD这3个端口控制LED灯 GPIO 是通用输入输出端口的简称 xff0c 简单来说就是 STM32 可控制的引脚 xff0c STM32 芯片 的 GPIO 引脚与外部设备连接起来 x

  • 一步步CEF（2）之编译ceflicent

    一步步CEF xff08 1 xff09 之编译libcef dll wrapper lib已经提供了c 43 43 的静态库 xff0c 这次要将cefclient编译出来 这里要说明一下 xff0c 如果仅仅将cefclient编译的话

  • Java查找最长字符匹配子串

    1 比较两个字符串 xff0c 短的那一个先判断是否包含在长的字符串中 2 如果不在 xff0c 短的字符串子串长度 1 xff0c 从前往后移判断是否包含 xff0c 不包含继续此操作 public class getMaxStringT

  • Python，Anaconda环境安装配置

    文章目录 Python安装pip包管理 Anaconda安装conda包管理和环境管理Python3与Python2共存 xff08 Anconda3与Anaconda2共存 xff09 Jupyter notebook配置Jupyter

  • SVN提示E230001、E170013解决方案

    解决办法 1 Windows电脑打开cmd命令行 xff0c Mac电脑打开终端 2 输入如下命令 svn ls https 127 0 0 1 8888 svn XXXXXXXX 这里是项目的svn地址 他会提示你输入信息 xff0c 这

  • 记一次Nginx启动失败解决过程(环境:linux Ubuntu 16.04 64bit , ECS for Aliyun)

    背景 今天装了个jpress想弄个博客 xff0c 然后关了Nginx和uwsgi xff0c 启动了tomcat 使用80端口 xff0c 后来直接shutdown sh关闭tomcat后 xff0c 再次启动Nginx报了个错误 Job

  • Windows安装Qt在选择界面卡死解决方案

    Windows安装Qt在选择界面卡死解决方案 很简单的操作 xff1a 就是安装了有道词典 xff0c 退出有道词典 xff0c 再安装Qt 哈哈哈 xff0c 是不是很简单 xff0c 我也是摸索了半天才知道 xff0c 网上说的各种卸载

  • Linux之cmake3.6安装

    1 官网下载cmake 3 6 3 tar gz https cmake org files v3 6 cmake 3 6 3 tar gz 2 解压文件tar xvf cmake 3 6 3 tar gz xff0c 并修改文件权限chm

  • mysql 分组获取最新一条记录

    1 需求 按用户名分组 xff0c 获取最新插入的一条记录 2 模拟数据 span class token comment span span class token comment Table structure for user spa

  • 电脑连接树莓派出现问题--(putty，VNC,MobaXterm和远程桌面连接)

    以下解决方法与问题是基于我之前给树莓派写的一个开机自启动python脚本导致的问题所提出的 如果你从来没有给树莓派写过脚本 xff0c 那我的这篇博客对现在的你来说没有帮助 xff0c 不用浪费时间了 今天在用PC的Putty ssh方式连

  • STM32+ESP-07S+MQTT服务器实现数据上传和接收

    参考文章 xff1a https blog csdn net weixin 46144773 article details 128793578 https docs ai thinker com esp8266 sdk esp32下载工具

  • Python问题：AttributeError: ‘str‘ object has no attribute ‘decode‘

    具体报错情况 xff1a AttributeError Traceback most recent call last lt ipython input 29 7b65833fd81b gt in lt module gt 8 from k

  • mount.nfs报错

    mount nfs requested NFS version or transport protocol is not supported 今天在挂载nfs时遇到mount nfs requested NFS version or tra

  • VMware虚拟机安装win10 32位

    VM15 43 Win10 32位 前期准备安装过程 前期准备 VMware Workstation15官方版下载 xff1a https www onlinedown net soft 2062 htm Win10 32位镜像下载 xff

  • AttributeError: ‘str‘ object has no attribute ‘value‘

    属性错误 xff1a str 对象没有属性 值 这是我在用python读取excel单元格的时候遇到的报错 xff0c cell对象没有属性值 xff0c 说明我的语法返回的是cell单元格对象而并非单元格的值 这时候只需将iter row

  • 算法题：马走日（C++）

    题目 xff1a 总时间限制 1000ms 内存限制 1024kB 描述 马在中国象棋以日字形规则移动 请编写一段程序 xff0c 给定n m大小的棋盘 xff0c 以及马的初始位置 x xff0c y xff0c 要求不能重复经过棋盘上的

随机推荐

  • WSL2-ubuntu1804安装以及一些个人使用调整

    文章目录 前言一 WSL是什么 xff1f 二 启用WSL21 首先确定自己的windows系统版本2 打开系统的虚拟化等一大堆功能3 切换默认模式至WSL2 三 安装WSL虚拟机 Ubuntu18041 下载安装 方法1 Microsof

  • LVM精简卷(Thinly-Provisioned Logical Volumes)的扩容

    LVM精简卷 Thinly Provisioned Logical Volumes 如果被人偷偷的在生产中使用 xff0c 紧急故障处理的时候 xff0c 可以一下子给人干懵 并且在百度还不能搜索到完整可用的文档 LVM精简卷的存在给我的感

  • Mac 备份 time machine开启全速备份

    Mac 备份非常慢 如果你的 Mac 是第一次在这个上面进行备份 xff0c 第一次备份一般都很慢 xff0c 可以调节参数的方式将其调节为全速进行备份 xff0c 记得备份完后将其调整回来 xff0c 否则可能会导致你的电脑在正常使用的时

  • 关于下载 http://arduino.esp8266.com/stable/package_esp8266com_index.json 出错的解决方法

    在使用 Arduino 43 NodeMCU 进行编程时 xff0c 有时候会出现如题所述的错误 xff0c 出错的网址是首选项中的 附加开发板管理器网址 xff0c 其意义是使得 Arduino 能够在开发板选项里找到ESP8266这块开

  • ubuntu 安装 qemu 提示 ERROR: glib-2.40 gthread-2.0 is required to compile QEMU and ERROR: pixman >= 0.21

    首先我们使用 xff1a apt cache search glib2 看看应该安装哪个库 sudo apt get install libglib2 0 dev 继续使用 apt cache search pixman 看看应该安装哪个库

  • 如何进行探索式数据分析？

    与数据同行 已开通综合 数据仓库 数据分析 产品经理 数据治理及机器学习六大专业群 xff0c 加微信号frank61822701 为好友后入群 新开招聘交流群 xff0c 请关注 与数据同行 公众号 xff0c 后台回复 招聘 后获得入群

  • Linux 移动或复制文件（文件夹）

    Linux 移动或复制文件 xff08 文件夹 xff09 命令格式 xff1a cp rf home backup default Public Public 复制 home backup default Public文件夹 到当前文件夹

  • 手把手教你配置阿里云服务器搭建网站

    写在前面 出于好奇 xff0c 我用学生优惠租了一台阿里云服务器 xff0c 打算做一些Java web的开发 xff0c 但是毕竟是第一次接触这样的东西 xff0c 还是比较懵逼 xff0c 在这个过程中遇到了一些问题 xff08 肯定会

  • Python

    人机交互 1 input 是输入函数 xff0c 会将所有输入做一个字符串类型的处理 a 61 input 作用 xff1a 显示出括号内的东西 xff0c 并要求用户输入一个东西 xff0c 赋给a 如果要有输入提示 xff0c 要在括号

  • PHP学习笔记——wampserver安装步骤

    1 wampserver的安装 安装链接 xff1a wampserver安装链接 选择 64 exe为后缀的安装包 xff08 前提是64位系统机器 xff09 选择语言 xff1a English 同意协议 next 选择安装路径 ne

  • 微博粉丝走势监控

    前言 因为之前写过很多爬虫 xff0c 然后近期也是选秀节目比较多 xff0c 像创造营 xff0c 青春有你等 一般情况下微博粉丝的增长速度是节目组比较关注的数据之一 因此 xff0c 想做一个简单的粉丝监控平台 xff0c 话不多说 x

  • ubuntu系统下各个目录的一般作用

    1 这是根目录 xff0c 一个Ubuntu系统下只有一个根目录 2 root 系统管理员的目录 3 boot 系统启动文件 4 bin 存放系统程序 5 etc 存放系统配置方面的文件 6 dev 存放与设备有观点文件 xff0c 例如

  • C/C++中枚举类型enum使用

    1 说明 xff1a 枚举enum的出现 xff0c 主要是为了解决一些特定属性的赋值 xff0c 变量取值仅在一定有限范围内的问题 例如一年只有十二个月取值 xff0c 一个星期只有七天情况 xff0c 人的性别只有男女两种等 这些属性如

  • Matlab中save实现保存数据到mat文件的正确使用

    主要需要注意save savePath A 和 save savePath 39 KSD 39 两种写法的区别 1 普通保存在当前文件夹下 save matPath mat span class hljs literal A span B

  • C/C++笔试必须熟悉掌握的头文件系列（三）——stdlib.h/cstdlib

    1 说明 stdlib h 头文件即标准库头文件 xff08 standard library xff09 xff0c stdlib 头文件里包含了C语言的最常用的系统函数 而C 43 43 中有对应相同作用的 cstdlib 头文件 xf

  • matlab图像类型转换以及uint8、double、im2double、im2uint8和mat2gray等说明

    1 matlab图像保存说明 matlab中读取图片后保存的数据是uint8类型 8位无符号整数 xff0c 即1个字节 xff0c 以此方式存储的图像称作8位图像 xff0c 好处相比较默认matlab数据类型双精度浮点double xf

  • PyCharm安装第三方库如Requests

    PyCharm安装第三方库是十分方便的 xff0c 无需pip或其他工具 xff0c 平台就自带了这个功能而且操作十分简便 如下 xff1a 注 xff1a 本人PyCharm已汉化 xff0c 若是英文版按括号中英文指示操作即可 1 打开

  • 关于django的ORM查询出来的数据格式的转换：OrderedDict类型转换为list；serializers序列化器配置字段可以为null

    目录 一 django查询的结果的类型是 xff1a OrderedDict类型 xff0c 如下 xff1a 二 serializers序列化器配置字段可以为null 一 django查询的结果的类型是 xff1a OrderedDict

  • pyCharm上解决安装不上pandas库问题

    最近在PyCharm上安装pandas库的时候 xff0c 总是安装不上 xff0c 提示好像是pip除了错误 我使用的是python 3 4版本 最后判断应该是自己pip版本应该太旧了 xff0c 最后再cmd更新了pip之后就行了 如下

  • 详细图解哈夫曼Huffman编码树

    1 引言 哈夫曼 xff08 Huffman xff09 编码算法是基于二叉树构建编码压缩结构的 xff0c 它是数据压缩中经典的一种算法 算法根据文本字符出现的频率 xff0c 重新对字符进行编码 因为为了缩短编码的长度 xff0c 我们

热门标签