数据结构历年考研真题对应知识点(哈夫曼树和哈夫曼编码)

目录

5.5.1哈夫曼树和哈夫曼编码

1.哈夫曼树的定义

2.哈夫曼树的构造

【分析哈夫曼树的路径上权值序列的合法性(2010)】

【哈夫曼树的性质(2010、2019)】

3.哈夫曼编码

【根据哈夫曼编码对编码序列进行译码(2017)】

【哈夫曼树的构造及相关的分析(2012、2018、2021、2023)】

【前缀编码的分析及应用(2014、2020)】

【哈夫曼编码和定长编码的差异(2022)】

5.5.2并查集(补充)

1.并查集的概念

2.并查集的存储结构

 3.并查集的基本实现

4.并查集实现的优化


5.5.1哈夫曼树和哈夫曼编码

1.哈夫曼树的定义

在介绍哈夫曼树之前,先介绍几个相关的概念:

从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径

路径上的分支数目称为路径长度

在许多应用中,树中结点常常被赋予一个表示某种意义的数值,称为该结点的

从树的根到一个结点的路径长度与该结点上权值的乘积,称为该结点的带权路径长度

树中所有叶结点的带权路径长度之和称为该树的带权路径长度,记为

WPL=\sum_{i=1}^{n}w_{i}l_{i}

式中,wi是第i个叶结点所带的权值,li是该叶结点到根结点的路径长度。

在含有n个带权叶结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树

例如,图 5.25 中的3棵二叉树都有4个叶结点 a,b,c,d,分别带权 7,5,2,4,

它们的带权路径长度分别为

(a) WPL=7x2+5x2+2x2+4x2 =36。

(b) WPL=4x2+ 7x3+5x3+ 2x1=46。

(c) WPL=7x1+5x2+2x3+4x3=35。

其中,图 5.25(c)树的 WPL 最小。可以验证,它恰好为哈夫曼树

2.哈夫曼树的构造

给定n个权值分别为w1,w2,…wn的结点,构造哈夫曼树的算法描述如下:

1) 将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F。

分析哈夫曼树的路径上权值序列的合法性(2010)

2) 构造一个新结点,从F中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和。

3) 从F中删除刚才选出的两棵树,同时将新得到的树加入F中。

4) 重复步骤2) 和 3),直至F中只剩下一棵树为止。

哈夫曼树的性质(2010、2019)

从上述构造过程中可以看出哈夫曼树具有如下特点:

1) 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越大。

2) 构造过程中共新建了n-1个结点(双分支结点),因此哈夫曼树的结点总数为2n-1。

3) 每次构造都选择2棵树作为新结点的孩子,因此哈夫曼树中不存在度为1的结点。

例如,权值{7,5,2,4}的哈夫曼树的构造过程如图 5.26 所示。

3.哈夫曼编码

在数据通信中,若对每个字符用相等长度的二进制位表示,称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制位表示,则这种编码方式称为可变长度编码

可变长度编码比固定长度编码要好得多,其特点是对频率高的字符赋以短编码,而对频率较低的字符则赋以较长一些的编码,从而可以使字符的平均编码长度减短,起到压缩数据的效果。

根据哈夫曼编码对编码序列进行译码(2017)

若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。举例:设计字符A,B和 C对应的编码 0,10 和 110是前缀编码。

对前缀编码的解码很简单,因为没有一个编码是其他编码的前缀。所以识别出第一个编码,将它翻译为原字符,再对剩余的码串执行同样的解码操作。

例如,码串 0010110 可被唯一地翻译为A,A,B和C。另举反例:若再将字符D 的编码设计为 11,此时11是110的前缀,则上述码串的后三位就无法唯一翻译。

夫曼树的构造及相关的分析(2012、2018、2021、2023)

前缀编码的分析及应用(2014、2020)

可以利用二叉树来设计二进制前缀编码。假设为A,B,C,D四个字符设计前缀编码,可以用图 5.27 所示的二叉树来表示,4个叶结点分别表示4个字符,且约定左分支表示 0,右分支表示1,从根到叶结点的路径上用分支标记组成的序列作为该叶结点字符的编码,可以证明如此得到的必为前缀编码。

由图5.27 得到字符 A,B,C,D的前缀编码分别为 0,10,110,111。

哈夫曼编码和定长编码的差异(2022)

哈夫曼编码是一种非常有效的数据压缩编码。由哈夫曼树得到哈夫曼编码是很自然的过程。

首先,将每个字符当作一个独立的结点,其权值为它出现的频度(或次数),构造出对应的哈夫曼树。

然后,将从根到叶结点的路径上分支标记的字符串作为该字符的编码。

图 5.28 所示为一个由哈夫曼树构造哈夫曼编码的示例,矩形方块表示字符及其出现的次数。

这棵哈夫曼树的 WPL为

WPL=1x45+3x(13+12+16)+4x(5 +9)=224

此处的 WPL 可视为最终编码得到二进制编码的长度,共 224位。若采用3位固定长度编码,则得到的二进制编码长度为 300 位,因此哈夫曼编码共压缩了 25%的数据。

利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

注意:左分支和右分支究竟是表示0还是表示1没有明确规定,因此构造出的哈夫曼树并不唯一,但各哈夫曼树的带权路径长度 WPL 相同且为最优

此外,如有若干权值相同的结点,则构造出的哈夫曼树更可能不同,但WPL 必然相同且为最优

5.5.2并查集(补充)

1.并查集的概念

并查集是一种简单的集合表示,它支持以下3种操作:

1) Initial(S):将集合S中的每个元素都初始化为只有一个单元素的子集合。

2) Union(S,Root1,Root2):把集合S中的子集合 Root2并入子集合 Root1。要求 Root1和 Root2 互不相交,否则不执行合并

3) Find(S,x):查找集合S中单元素x所在的子集合,并返回该子集合的根结点。

2.并查集的存储结构

通常用树的双亲表示作为并查集的存储结构,每个子集合以一棵树表示。所有表示子集合的树,构成表示全集合的森林,存放在双亲表示数组内。

通常用数组元素的下标代表元素名,用根结点的下标代表子集合名,根结点的双亲域为负数(可设置为该子集合元素数量的相反数)。

例如,若设有一个全集合为S=(0,1,2,3,4,5,6,7,8,9},初始化时每个元素自成一个单元素子集合,每个子集合的数组值为-1,如图5.29所示。

经过一段时间的计算后,这些子集合合并为3个更大的子集合,即S1=(0,6,7,8},S2={1,4,9},S3={2,3,5},此时并查集的树形和存储结构如图 5.30 所示。

 

为了得到两个子集合的并,只需将其中一个子集合根结点的双亲指针指向另一个集合的根结点。因此,S1 U S2(S1并S2),可以具有如图 5.31所示的表示。

 

在采用树的双亲指针数组表示作为并查集的存储表示时,集合元素的编号从0到SIZE-1。其中 SIZE 是最大元素的个数。

 3.并查集的基本实现

并查集的结构定义如下:

#define SIZE 100
int    UFSets[SIZE];    //集合元素数组(双亲指针数组)

下面是并查集主要运算的实现。

(1) 并查集的初始化操作

void Initial(int S[]){        //S即为并查集for(int i=0;i<SIZE;i++)   //每个自成单元素集合S[i]=-1;
}

(2) 并查集的 Find 操作

在并查集S中查找并返回包含元素x的树的根。

int Find(int S[],int x){while(S[x]>=0)        //循环寻找x的根x=S [x];return x;             //根的 s[]小于 0
}

判断两个元素是否属于同一集合,只需分别找到它们的根,再比较根是否相同即可。

(3) 并查集的 Union 操作

求两个不相交子集合的并集。若将两个元素所在的集合合并为一个集合,则需要先找到两个元素的根,再令一棵子集树的根指向另一棵子集树的根。

void Union(int S[],int Rootl,int Root2){if(Root1==Root2) return;     //要求 Root1与Root2 是不同的集合S [Root2]=Root1;             //将根 Root2连接到另一根 Root1下面
}

Find 操作和 Union 操作的时间复杂度分别为 O(d)和 O(1),其中d为树的深度。

4.并查集实现的优化

在极端情况下,n个元素构成的集合树的深度为n,则 Find 操作的最坏时间复杂度为 O(n)。

改进的办法是:在做 Union 操作之前,首先判别子集中的成员数量,然后令成员少的根指向成员多的根,即把小树合并到大树,为此可令根结点的绝对值保存集合树中的成员数量。

(1) 改进的 Union 操作

void Union(int S[],int Rootl,int Root2){if(Root1==Root2) return;if(S[Root2]>S[Root1]){       //Root2 结点数更少S[Root1]+=S[Root2];      //累加集合树的结点总数S[Root2]=Root1;          //小树合并到大树}else{                        //Root1结点数更少S[Root2]+=S[Root1];      //累加结点总数S[Root1]=Root2;          //小树合并到大树}
}

采用这种方法构造得到的集合树,其深度不超过\left \lfloor log_{2}n \right \rfloor+1

随着子集逐对合并,集合树的深度越来越大,为了进一步减少确定元素所在集合的时间,还可进一步对上述 Find 操作进行优化,当所査元素x不在树的第二层时,在算法中增加一个“压缩路径”的功能,即将从根到元素x路径上的所有元素都变成根的孩子。

(2) 改进的 Find 操作

int Find(int S[],int x){int root=x;while(s[root]>=0)    //循环找到根root=s[root];while(x!=root){      //压缩路径int t=S[x];      //t指向x的父结点S[x]=root;       //x直接挂到根结点下面x=t;}return root;         //返回根结点编号
}

通过 Find 操作的“压缩路径”优化后,可使集合树的深度不超过 O(α(n)),其中 α(n)是一个增长极其缓慢的函数,对于常见的正整数 n,通常 α(n)<=4。

 

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

乘积量化pq:将高维向量压缩 97%

向量相似性搜索在处理大规模数据集时&#xff0c;往往面临着内存消耗的挑战。例如&#xff0c;即使是一个包含100万个密集向量的小数据集&#xff0c;其索引也可能需要数GB的内存。随着数据集规模的增长&#xff0c;尤其是高维数据&#xff0c;内存使用量会迅速增加&#xff0c…

达梦 ./disql SYSDBA/SYSDBA报错[-70028]:创建SOCKET连接失败. 解决方法

原因 达梦命令./disql SYSDBA/SYSDBA默认访问端口5236&#xff0c;如果初始化实例的时候修改了端口&#xff0c;需要指定端口访问 解决 ./disql SYSDBA/SYSDBA192.168.10.123:5237

数据结构(5.2_1)——二叉树的基本定义和术语

二叉树的基本概念 二叉树是n(n>0)个结点的有限集合: 或者为空二叉树&#xff0c;即n0&#xff1b;或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一颗二叉树。 特点:每个结点至多只有两颗字数&#xff1b;左子树不能颠倒(二叉树…

09 深度推荐模型演化中的“平衡与不平衡“规律

你好&#xff0c;我是大壮。08 讲我们介绍了深度推荐算法中的范式方法&#xff0c;并简单讲解了组合范式推荐方法&#xff0c;其中还提到了多层感知器&#xff08;MLP&#xff09;。因此&#xff0c;这一讲我们就以 MLP 组件为基础&#xff0c;讲解深度学习范式的其他组合推荐方…

pico+unity3d手部动画

在 Unity 开发中&#xff0c;输入系统的选择和运用对于实现丰富的交互体验至关重要。本文将深入探讨 Unity 中的 Input System 和 XR Input Subsystem 这两种不同的输入系统&#xff0c;并详细介绍它们在控制手部动画方面的应用。 一、Input System 和 XR Input Subsystem 的区…

每日练习,不要放弃

目录 题目1.下面叙述错误的是 ( )2.java如何返回request范围内存在的对象&#xff1f;3.以下代码将打印出4.下列类定义中哪些是合法的抽象类的定义&#xff1f;&#xff08;&#xff09;5.以下代码段执行后的输出结果为6.以下代码运行输出的是总结 题目 选自牛客网 1.下面叙述…

【node-RED 4.0.2】连接操作 Oracle 数据库实现 增 删 改 查【新版,使用新插件:@hylink/node-red-oracle】

总览 上节课&#xff0c;我们说到&#xff0c;在 node-red 上链接 oracle 数据库 我们使用的插件是 node-red-contrib-agur-connector。 其实后来我发现&#xff0c;有一个插件更简便&#xff0c;并且也更好用&#xff1a;hylink/node-red-oracle &#xff01;&#xff01;&am…

Linux--网络基础

计算机网络背景 计算机网络背景是一个复杂而丰富的领域&#xff0c;涵盖了从计算机单机模式到网络互联的演变过程&#xff0c;以及网络技术的不断发展和创新。 计算机单机模式和独立发展 在早期&#xff0c;计算机主要以单机模式存在&#xff0c;即每台计算机都是独立的&…

传知代码-揭秘AI如何揪出图片中的“李鬼”(论文复现)

代码以及视频讲解 本文所涉及所有资源均在传知代码平台可获取 文字篡改图像的“照妖镜”&#xff1a;揭秘AI如何揪出图片中的“李鬼” 在数字化时代&#xff0c;我们时常被各种图像信息所包围。然而&#xff0c;这些图像中有时隐藏着不为人知的秘密——被篡改的文字或图像。这…

C++ | Leetcode C++题解之第238题除自身以外数组的乘积

题目&#xff1a; 题解&#xff1a; class Solution { public:vector<int> productExceptSelf(vector<int>& nums) {int length nums.size();// L 和 R 分别表示左右两侧的乘积列表vector<int> L(length, 0), R(length, 0);vector<int> answer(l…

188数码管轮询扫描

前言 最近用到了188数码管&#xff0c;总结一下。 188数码管&#xff0c;用5个IO&#xff0c;在不借助外部驱动芯片的情况下&#xff0c;可以点亮20个灯。188数码管广泛应用于电子烟、充电器、充电宝、DVD、高级音响、工业设备控制面板、医疗器械等多个领域&#xff0c;满足不…

【iOS】——TaggedPointer

TaggedPointer介绍 在为了改进从 32位CPU 迁移到 64位CPU 的内存浪费和效率问题&#xff0c;在 64位CPU 环境下&#xff0c;引入了 Tagged Pointer 。旨在提高内存效率和运行性能&#xff0c;尤其针对小的、频繁使用的对象&#xff0c;如NSNumber, NSDate, 和NSString等。在64…

昇思学习打卡-19-生成式/Pix2Pix实现图像转换

文章目录 网络介绍训练推理结果 网络介绍 Pix2Pix是基于条件生成对抗网络&#xff08;cGAN, Condition Generative Adversarial Networks &#xff09;实现的一种深度学习图像转换模型&#xff0c;可以实现语义/标签到真实图片、灰度图到彩色图、航空图到地图、白天到黑夜、线…

mmdetection

首先下载mmdetection 3.2.0版本的 https://github.com/open-mmlab/mmdetection/tree/v3.2.0 第二步&#xff1a;创建虚拟环境 conda create -n mmdetection python3.8 -y conda activate mmdetection第三步&#xff1a;安装包 pip install torch2.0.1cu118 -f https://downl…

【c++】新领域:“智能数组 ” 问世

引入: 大家有没有发现每次创建和使用数组时很麻烦,因为数组长度一般只能用静态常量,太过局限,不满足大部分开发者的需求。而且遍历数组也很麻烦,又要for循环,又要在其他使用数组的地方检查边界。 于是我就构想了一种“智能数组” 就解决了大部分的难题 这样的语言风格是…

分布式IO系统2通道串口通信模块M602x

现场总线耦合器本身包含一个电源模块&#xff0c;它有 2 个串口通道&#xff0c;通过 Modbus RTU&#xff08;Master&#xff09;协议连接外部串行设备&#xff0c;实现耦合器与外部串行设备通信&#xff0c;现以连接设备的示例带大家了解我们钡铼的2 通道串口通信模块 M602x。…

自闭症孩子为什么容易出现饮食问题?

在星启帆自闭症学校&#xff0c;我们深知自闭症孩子在日常生活中常常面临饮食问题的挑战。这些问题不仅影响孩子的营养摄入和健康成长&#xff0c;也给家庭和学校带来了不小的困扰。以下是我对自闭症孩子容易出现饮食问题的几点分析&#xff1a; 一、感官敏感性 自闭症孩子往往…

【NetTopologySuite类库】合并所有几何的包围盒AABB

流程示意图 示例代码 using GeoAPI.Geometries; using Microsoft.VisualStudio.TestTools.UnitTesting; using NetTopologySuite.Geometries; using NetTopologySuite.IO; using System.Collections.Generic; using System.Linq;namespace Test472 {[TestClass]public class T…

vim网络和安全的操作及shell的使用

目录 vim模式 一般模式下的基本操作&#xff1a; 一般模式切换到编辑模式&#xff1a; 一般模式切换到命令模式&#xff1a; Vim多窗口使用技巧 横向切割打开&#xff1a; 纵向切割打开&#xff1a; 关闭多窗口&#xff1a; 窗口的切换&#xff1a; 网络&#xff1a;…

使用 Flask 3 搭建问答平台(二):User 模型搭建

前言 以下所有代码均是在之前的基础上添加&#xff01;&#xff01;&#xff01; 后面的章节均是如此 知识点 1. 使用 pymysql 模块连接数据库 2. 在模型中创建用户数据表 3. 初始化数据库、创建初始迁移脚本、应用初始迁移脚本 一、User 模型搭建 1.1 准备数据库 1.2 …