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

2024-04-11 19:44

本文主要是介绍二叉树应用——最优二叉树(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}")

这篇关于二叉树应用——最优二叉树(Huffman树)、贪心算法—— Huffman编码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/895007

相关文章

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

中文分词jieba库的使用与实景应用(一)

知识星球:https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义: 精确模式(默认模式): 全模式: 搜索引擎模式: paddle 模式(基于深度学习的分词模式): 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取

水位雨量在线监测系统概述及应用介绍

在当今社会,随着科技的飞速发展,各种智能监测系统已成为保障公共安全、促进资源管理和环境保护的重要工具。其中,水位雨量在线监测系统作为自然灾害预警、水资源管理及水利工程运行的关键技术,其重要性不言而喻。 一、水位雨量在线监测系统的基本原理 水位雨量在线监测系统主要由数据采集单元、数据传输网络、数据处理中心及用户终端四大部分构成,形成了一个完整的闭环系统。 数据采集单元:这是系统的“眼睛”,

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

zoj3820(树的直径的应用)

题意:在一颗树上找两个点,使得所有点到选择与其更近的一个点的距离的最大值最小。 思路:如果是选择一个点的话,那么点就是直径的中点。现在考虑两个点的情况,先求树的直径,再把直径最中间的边去掉,再求剩下的两个子树中直径的中点。 代码如下: #include <stdio.h>#include <string.h>#include <algorithm>#include <map>#

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an