C++项目基于HuffmanTree实现文件的压缩与解压缩功能

编辑: admin 分类: c#语言发布时间: 2022-03-15 来源:互联网

1.创建优先级队列要使用自己写的仿函数
2.自定义类型结构体类型相加和仿函数要重载operator+和operator>
3.剔除在HuffmanTree出现0次的字符，不用统计出现0次的字符
4.如果在解压缩时，最后一个字节的压缩数据不满8个比特位，则在解压缩过程中如何处理？
5.在解压缩源文件中有汉字，解压缩过时出现乱码，怎么处理？
6.文件中包含多行文本时解压缩出现乱码

四、测试结果

1.字符文件
2.文本文件
3.图片文件
4.如果对压缩结果二次或者多次压缩，会不会每次都变小
5.Huffman压缩有无出现压缩结果变大的可能

前言

一、文件压缩

1.文件压缩的概念

在这里插入图片描述

文件压缩是指在不丢失有用信息的前提下，缩减数据量以减少存储空间，提高其传输、存储和处理效率，或按照一定的算法对文件中数据进行重新组织，减少数据的冗余和存储的空间的一种技术方法。

2.为什么需要压缩

①紧缩数据存储容量，减少存储空间。
②可以提高数据传输的速度，减少带宽占用量，提高通讯效率。
③对数据的一种加密保护，增强数据在传输过程中的安全性。

3.压缩的分类

有损压缩:有损压缩是利用了人类对图像或声波中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息；虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响缩小，却换来了大得多的压缩比，即指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。
无损压缩:对文件中数据按照特定的编码格式进行重新组织，压缩后的压缩文件可以被还原成与源文件完全相同的格式，不会影响文件内容，对于数码图像而言，不会使图像细节有任何损失。

在这里插入图片描述

4.压缩的方法

压缩的目的是让文件变小，减少文件所占的存储空间。

专有名词采用的固定短语：比如：南昌大学，简称南大或者昌大，就可以提到压缩的目的，但只能针对于大家所熟知的专有名词。

缩短文件中重复的数据：比如文件中存放数据为：mnoabczxyuvwabc123456abczxydefgh
对文件中重复数据使用(距离，长度)对进行替换，压缩之后的结果为：mnoabczxyuvw(9,3)123456(18, 6)defgh。

在这里插入图片描述

给文件中每个字节找一个更短的编码：比如文件中存放数据为：ABBBCCCCCDDDDDDD。

采用静态等长编码压缩： 00010101 10101010 10000000 00000000。

在这里插入图片描述

采用动态不等长编码压缩：10010110 11011111 11111100 00000000。

在这里插入图片描述

文件16个字节，压缩完成之后占4个字节，可以起到压缩的目的。

二、HuffmanTree文件压缩与解压缩

1.HuffmanTree的概念

在认识哈夫曼树之前，你必须知道以下几个基本术语：

①什么是路径？

在一棵树中，从一个结点往下可以达到的结点之间的通路，称为路径。
在这里插入图片描述

②什么是路径长度？

某一路径所经过的“边”的数量，称为该路径的路径长度。
在这里插入图片描述
如图，该路径经过了3条边，因此该路径的路径长度为3。

③什么是结点的带权路径长度？

若将树中结点赋给一个带有某种含义的数值，则该数值称为该结点的权。从根结点到该结点之间的路径长度与该结点的权的乘积，称为该结点的带权路径长度。
在这里插入图片描述
如图，叶子结点I的带权路径长度为 3 × 3 = 9 。

④什么是树的带权路径长度？

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
在这里插入图片描述
如图，该二叉树的带权路径长度 WPL= 2 × 2 + 2 × 6 + 3 × 1 + 3 × 3 + 2 × 2 = 32

⑤什么是哈夫曼树？

给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，则称该二叉树为哈夫曼树，也被称为最优二叉树。

根据树的带权路径长度的计算规则，我们不难理解：树的带权路径长度与其叶子结点的分布有关。
即便是两棵结构相同的二叉树，也会因为其叶子结点的分布不同，而导致两棵二叉树的带权路径长度不同。

在这里插入图片描述

那如何才能使一棵二叉树的带权路径长度达到最小呢？
根据树的带权路径长度的计算规则，我们应该尽可能地让权值大的叶子结点靠近根结点，让权值小的叶子结点远离根结点，这样便能使得这棵二叉树的带权路径长度达到最小。

2.HuffmanTree的构建

下面给出一个非常简洁易操作的算法，来构造一棵哈夫曼树：
1、初始状态下共有n个结点，结点的权值分别是给定的n个数，将他们视作n棵只有根结点的树。
2、合并其中根结点权值最小的两棵树，生成这两棵树的父结点，权值为这两个根结点的权值之和，这样树的数量就减少了一个。
3、重复操作2，直到只剩下一棵树为止，这棵树就是哈夫曼树。

例如，现给定5个数，分别为1、2、2、3、6，要求构建一棵哈夫曼树。
动图演示：

在这里插入图片描述