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

前言

一、文件压缩

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.Hu

以上就是C++项目基于HuffmanTree实现文件的压缩与解压缩功能的详细内容，更多请关注0133技术站其它相关文章！