二叉树应用——最优二叉树(Huffman树)、贪心算法—— Huffman编码

1、外部带权外部路径长度、Huffman树

在这里插入图片描述
从图中可以看出,深度越浅的叶子结点权重越大,深度越深的叶子结点权重越小的话,得出的带权外部路径长度越小。
Huffman树就是使得外部带权路径最小的二叉树

2、如何构造Huffman树

(1)步骤

(1)根据给定的n个权值{W1,W2,…,Wn},构造n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树中均只含有一个带权值为Wi的根结点,其左右子树为空树
(2)在F中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树,并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;
(3)从F中删去这两棵树,同时加入刚生成的新树;
(4)重复(2)和(3)两步,直至F中只含一棵树为止

以上图的结点为例:
在这里插入图片描述

(2)代码

在这里插入图片描述

用bfs广度优先搜索遍历这个二叉树来检验
在这里插入图片描述

(3)代码注意点

在这里插入图片描述

2、ASCII码

在ASCII(American Standard Code for Information Interchange,美国信息交换标准代码)编码中,每个大写或小写英文字母都被赋予一个唯一的数字值。这些值都是7位的二进制数,但在实际存储和传输时,它们通常会被填充为一个字节(8位),最高位(第8位)设置为0。

对于小写字母 ‘a’,其ASCII码值是97(十进制)。在二进制表示中,它是 01100001。

同理,大写字母 ‘A’ 的ASCII码值是65(十进制),二进制表示为 01000001。

请注意,ASCII码只包含128个字符,包括大小写英文字母、数字、标点符号和一些控制字符。如果需要表示更多的字符,比如各种语言的文字符号,就需要使用扩展的字符编码,如ISO 8859系列、Unicode等。

3、Huffman编码

哈夫曼编码,它是一种可变长编码方式,根据字符出现频率来构造异字头的平均长度最短的码字,是数据压缩算法中的一种。哈夫曼编码是贪婪算法的应用之一。哈夫曼树又称最优二叉树,带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL=(W1L1+W2L2+W3L3+…+WnLn),N个权值Wi(i=1,2,…n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,…n)。可以证明哈夫曼树是WPL最小的二叉树,故有时也称哈夫曼编码为最优前缀码。

(1)Huffman编码对比其他编码方式的优势

这里先给出一个字符串:"this is isinglass’’
其中共有15个字符。

假如用ASCII码编码,ASCII编码每个字符用7个二进制数,但在存储时会被填充成一个字节,即8位,因此占位:15*8=120
在ASCII码的基础上进行改进,每个字符用3位表示,占位:15*3=45
我们再来看一下Huffman编码

文字部分可以打开图片直接对照,也可以先看文字解释
在这里插入图片描述

在这里插入图片描述
经过上述对比可以很明显看出Huffman编码的好处

(2)Huffman编码具有前缀特性

思考:为什么不给频率最高的字母s和i以最短的编号,如分别是0、1,然后剩余编号:00,01,10,11,000,001?这样不就能最大程度节省空间了吗?
其实这样是不正确的 。
首先,我们需要理解Huffman编码的目标:它是为了创建一种前缀编码(prefix code),在这种编码中,任何字符的编码都不是其他字符编码的前缀。这意味着编码字符串可以无歧义地解码回原始字符序列。如果我们简单地给频率最高的字母分配最短的编码(如0或1),那么很可能会有多个字符的编码成为其他字符编码的前缀,从而违反了前缀编码的原则。(解码时会出现二异性)

其次,Huffman编码追求的是整体编码长度的最小化,而不仅仅是单个字符编码长度的最小化。通过将频率最低的字符分配最长的编码,而频率最高的字符分配最短的编码,Huffman编码确保了整体编码长度最短。这是基于信息论中的最优编码理论,即使用最少的位数来表示最可能出现的事件。

Huffman树的前缀特性是由其构建过程自然产生的。Huffman树的构建过程确保了每个字符的编码都是唯一的,并且没有一个是另一个的前缀。这是因为Huffman树是一个二叉树,每个字符都是树的一个叶子节点,从根节点到该叶子节点的路径决定了该字符的编码。由于树的结构保证了从根到每个叶子节点的路径是唯一的,因此每个字符的编码也是唯一的,并且没有前缀冲突。

最后,虽然将频率最高的字母的编码设置为0和1可能在某些情况下看似节省空间,但这并不适用于所有情况。Huffman编码是一种通用的、自适应的编码方法,它根据字符的实际频率分布来构建编码,从而在各种不同的情况下都能达到较好的压缩效果。而简单地给某个字符分配固定的短编码可能会在某些特定情况下导致较差的压缩性能。

综上所述,Huffman编码不直接将频率最高的字母的编码设置为0和1,而是基于Huffman树来构建前缀编码系统,这是为了确保编码的唯一性和无前缀冲突,同时追求整体编码长度的最小化。Huffman树的前缀特性是由其构建过程自然产生的,保证了每个字符的编码都是唯一的。

(2)代码实现

在这里插入图片描述

代码拆分理解构

1、构建最优二叉树:

在这里插入图片描述

2、编码函数

在这里插入图片描述

3、解码函数

在这里插入图片描述

4、实例使用

在这里插入图片描述

import heapq
from collections import defaultdict, Counter# 辅助函数:构建Huffman树
def build_huffman_tree(freq_dict):heap = [[weight, [char, ""]] for char, weight in freq_dict.items()]heapq.heapify(heap)while len(heap) > 1:lo = heapq.heappop(heap)hi = heapq.heappop(heap)for pair in lo[1:]:pair[1] = '0' + pair[1]for pair in hi[1:]:pair[1] = '1' + pair[1]heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])return heap[0][1:]#打印char编码:[['r', '00'], ['t', '010'], ['y', '011'], ['u', '10'], ['o', '11']]# 编码函数
def huffman_encode(s):freq_dict = Counter(s)#Counter({'o': 5, 'u': 4, 'r': 3, 'y': 2, 't': 1})huff_tree = build_huffman_tree(freq_dict)#[['r', '00'], ['t', '010'], ['y', '011'], ['u', '10'], ['o', '11']]huff_dict = {pair[1]: pair[0] for pair in huff_tree}#huff_dict={'00':'r','010':'t','011':'y','10':'u','11':'o'}huff_dict1 = {pair[0]: pair[1] for pair in huff_tree}#huff_dict1={'r': '00', 't': '010', 'y': '011', 'u': '10', 'o': '11'}encoded_str = ' '.join(huff_dict1[char] for char in s)#encoded_str='00 010 11 011 00 10 11 10 011 10 00 11 10 11 11'return encoded_str, huff_dict# 解码函数
def huffman_decode(encoded_str, huff_dict):a=encoded_str.split()#['00', '010', '11', '011', '00', '10', '11', '10', '011', '10', '00', '11', '10', '11', '11']decoded_str = ""current_dict = huff_dict#huff_dict={'00':'r','010':'t','011':'y','10':'u','11':'o'}for bit in a:l = current_dict[bit]#l='r'if isinstance(l, str):#如果l是str类型就放进encoded_str里decoded_str += lreturn decoded_str# 示例使用
s = "this is an example for huffman encoding"
encoded_str, huff_dict = huffman_encode(s)
print(f"Encoded string: {encoded_str}")
print(f"Huffman dictionary: {huff_dict}")decoded_str = huffman_decode(encoded_str, huff_dict)
print(f"Decoded string: {decoded_str}")

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

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

相关文章

【Python-MP4文体提取】

Python-MP4文体提取 ■ pip 和 setuptools工具■ OpenCV和Tesseract■ Tesseract OCR V5.0安装教程(Windows)■ 1. 运行程序出现如下问题:我们需要安装Tesseract OCR■ 2. 下载Tesseract-OCR■ 3. 安装Tesseract-OCR■ 4. 添加到环境变量的系…

Golang中的上下文-context包的简介及使用

文章目录 简介context.Background()上下文取消函数上下文值传递建议Reference 简介 Go语言中的context包定义了一个名为Context的类型,它定义并传递截止日期、取消信号和其他请求范围的值,形成一个链式模型。如果我们查看官方文档,它是这样说…

Ollama利用嵌入模型实现RAG应用

Ollama支持embedding models嵌入模型,从而支持RAG(retrieval augmented generation)应用,结合文本提示词,检索到文档或相关数据。嵌入模型是通过训练生成向量嵌入,这是一长串数字数组,代表文本序…

练习 21 Web [GXYCTF2019]BabySQli

SQL联合查询,注意有源码看源码,Base64以及32的区别,MD5碰撞 打开后有登录框,先随意登录尝试 只有输入admin才是返回wrong pass! 其他返回wrong user 所以用户名字段一定要输入admin 养成好习惯,先查看源码…

kali上python3切换python2环境

一、然后打开终端输入 python --version 二、 打开终端分别输入下面两条命令: update-alternatives --install /usr/bin/python python /usr/bin/python2 100 update-alternatives --install /usr/bin/python python /usr/bin/python3 150 三、 如果需要切换python版…

Windows系统C盘空间优化进阶:磁盘清理与Docker日志管理

Windows系统C盘空间优化进阶:磁盘清理与Docker日志管理 文章目录 Windows系统C盘空间优化进阶:磁盘清理与Docker日志管理磁盘清理工具 使用“运行”命令访问磁盘清理利用存储感知自动管理空间清理WinSxS文件夹结合手动清理策略 小结删除临时文件总结&…

流式密集视频字幕

流式密集视频字幕 摘要1 IntroductionRelated Work3 Streaming Dense Video Captioning Streaming Dense Video Captioning 摘要 对于一个密集视频字幕生成模型,预测在视频中时间上定位的字幕,理想情况下应该能够处理长的输入视频,预测丰富、…

Linux系统概述与安装

Linux的介绍 Linux内核 Linux内核是 Linux 操作系统主要组件,也是计算机硬件与其软件之间的交互入口。它负责两者之间的通信,还要尽可能高效地管理资源 Linux Shell shell是系统的用户界面,提供了用户与内核进行交互操作的一种接口 Linux文…

java数组.day16(冒泡排序,稀疏数组)

冒泡排序 冒泡排序无疑是最为出名的排序算法之一,总共有八大排序! 冒泡的代码还是相当简单的,两层循环,外层冒泡轮数,里层依次比较,江湖中人人尽皆知。 我们看到嵌套循环,应该立马就可以得出这个算法的时…

2024中国航空航天暨无人机展览会8月在重庆举办

2024中国航空航天暨无人机展览会8月在重庆举办 邀请函 主办单位: 中国航空学会 重庆市南岸区人民政府 招商执行单位: 重庆港华展览有限公司 展会背景: 为更好的培养航空航天产业人才,汇聚航空教育产业创新科技,…

CTK插件框架学习-事件监听(07)

CTK插件框架学习-服务工厂(06)https://mp.csdn.net/mp_blog/creation/editor/137295686 一、简介 事件监听指当事件发生变化时所产生的通信,是动态的,对于已经发生过的事件无法监听 二、事件类型 1、框架事件 监听框架状态变化,因为监听…

usb_camera传输视频流编码的问题记录!

前言: 大家好,今天给大家分享的内容是,一个vip课程付费的朋友,在学习过程中遇到了一个usb采集的视频数据流,经过ffmpeg编码,出现了问题: 问题分析: 其实这个问题不难,关键…

git安装配置教程(小白保姆教程2024最新版)

目录 一、Git是什么?二、安装Git1.下载git2.安装git3.检测git 三、配置Git1.配置本地信息2.配置SSH1)SSH与SSH Key是什么?2)生成SSH Key3)获取ssh key公钥内容(id_rsa.pub)4)Github账号上添加公…

这段程序有点神奇,你能读懂么?

下面的程序在一个打开的文档中查找特定的字符串,这个字符串是“可以”,查找并仅保留最后的3次,抛弃其他的内容,请试运行一下,看看结果是否正确? from collections import deque def search(lines, pattern,…

【SpringBoot】配置swagger

pom.xml 安装插件 <dependency><groupId>io.springfox</groupId><artifactId>springfox-boot-starter</artifactId><version>3.0.0</version></dependency>创建swagger配置类 import org.springframework.context.annotation.…

如何使用Tomcat+cpolar搭建本地站点并发布到公网分享好友远程访问

文章目录 前言1.本地Tomcat网页搭建1.1 Tomcat安装1.2 配置环境变量1.3 环境配置1.4 Tomcat运行测试1.5 Cpolar安装和注册 2.本地网页发布2.1.Cpolar云端设置2.2 Cpolar本地设置 3.公网访问测试4.结语 前言 Tomcat作为一个轻量级的服务器拥有强大功能&#xff0c;由于其可以实…

如何使用Java和RabbitMQ实现延迟队列?

前言 今天我们使用Java和RabbitMQ实现消息队列的延迟功能。 前期准备&#xff0c;需要安装好docker、docker-compose的运行环境。 需要安装RabbitMQ的可以看下面这篇文章。 如何使用PHP和RabbitMQ实现消息队列&#xff1f;-CSDN博客 今天讲的是依赖RabbitMQ的延迟插件实现…

头歌-机器学习 第10次实验 逻辑回归

第1关&#xff1a;逻辑回归核心思想 任务描述 本关任务&#xff1a;根据本节课所学知识完成本关所设置的编程题。 相关知识 为了完成本关任务&#xff0c;你需要掌握&#xff1a; 什么是逻辑回归&#xff1b; sigmoid函数。 什么是逻辑回归 当一看到“回归”这两个字&a…

【opencv】示例-falsecolor.cpp 使用OpenCV函数动态地对图像应用不同的色彩映射

该代码是一个使用OpenCV库实现的C程序&#xff0c;主要用来展示如何通过applyColorMap函数将色彩映射应用到一个灰度图像上&#xff0c;并提供一个滑动条来实时改变色彩映射的效果。此外&#xff0c;该程序还可以绘制包含不同形状的灰度图像&#xff0c;用作applyColorMap函数的…

QT 线程之movetothread

上文列举了qt中线程的几种方法&#xff0c;其中2种方法最为常见。 这两种方法都少不了QThread类&#xff0c;前者继承于QThread类&#xff0c;后者复合QThread类。 本文以实例的方式描述了movetothread&#xff08;&#xff09;这种线程的方法&#xff0c;将QObject的子类移动…