[数据结构与算法]关于文件压缩解压缩与文件加密解密的项目

前言

该文章是关于Huffman树的一种无损算法，基于以前文章中介绍的Huffman树的改良，具体代码可以看此处文章哈夫曼编码的实现

1. 什么是文件压缩

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

2. 为什么需要压缩

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

3. 压缩的分类

有损压缩

有损压缩是利用了人类对图像或声波中的某些频率成分不敏感的特性，允许压缩过程中损失一定的信息；虽然不能完全恢复原始数据，但是所损失的部分对理解原始图像的影响缩小，却换来了大得多的压缩比，即指使用压缩后的数据进行重构，重构后的数据与原来的数据有所不同，但不影响人对原始资料表达的信息造成误解。

无损压缩

对文件中数据按照特定的编码格式进行重新组织，压缩后的压缩文件可以被还原成与源文件完全相同的格式，不会影响文件内容，对于数码图像而言，不会使图像细节有任何损失。
此项目中用的的就是无损压缩算法

4. Huffman编码的实现原理

哈夫曼编码的实现需要通过构造哈夫曼树，通过遍历哈夫曼的子树来确定每个字符的编码。
在构建哈夫曼树时，需要取出权值最小的两颗子树，可以利用队列从队头取元素的特性，将树节点按照权值由小到大的存储在队列中，在构造哈夫曼树时，从队头取出两个权值最小的子树进行哈夫曼树的构造，并将构造好的子树继续根据权值大小放入队列中，用于下一次构造，直至队列为空。

步骤:

1.由给定的n个权值{ w1, w2, w3, … , wn}构造n棵只有根节点的二叉树森林F={T1, T2 , T3, … ,Tn},每棵二叉树Ti只有一个带权值wi的根节点，左右孩子均为空。
2.重复以下步骤，直到F中只剩下一棵树为止

• 在F中选取两棵根节点权值最小的二叉树，作为左右子树构造一棵新的二叉树,新二叉树根节点的权值为其左右子树根节点的权值之和
• 在F中删除这两棵二叉树
• 把新的二叉树加入到F中

4.1 创建Huffman树用的的数据结构

因为再STL标准模板库中，有优先级队列，其底层结构是堆结构，刚好符合我们需要的创建时取出最小的两个结点。

5. 压缩流程与解压流程

5.1 压缩流程

1. 统计源文件中每个字节的出现次数，用于创建Huffman树

uchar readBuffer[1024];
	while (true)
	{
		// readSize实际读取到的字节数，如果读取文件的字节数少于预期则达到文件末尾
		size_t readSize = fread(readBuffer, 1, sizeof(readBuffer), fpIn);
		if (0 == readSize)
		{
			// 读取到文件末尾
			break;
		}

		// 统计个数
		for (size_t i = 0; i < readSize; i++)
		{
			// 哈希直接定值法，以字符的acsii码值作为下标
			fileByInfo[readBuffer[i]].appearCount++;
		}
	}

2. 使用优先级队列创建Huffman树

void CreateHuffmanTree(const W array[], size_t size, const W& invalid)
	{
		// 指定优先级队列为小堆的排序方式
		std::priority_queue<Node*, std::vector<Node*>, Compare<W>> pq;

		// 1.使用权值创建二叉树森林，即将含有权值的二叉树放入优先级队列中，优先级队列会自动进行排序
		for (size_t i = 0; i < size; i++)
		{
			if (array[i] != invalid)
			{
				pq.push(new Node(array[i]));
			}
		}

		// 2.不断从队列中取出最小的两个节点，构建子树，构建好后放入队列中，直至队列中只有一棵树
		while (pq.size() > 1)
		{
			// 2.1 取出左右子树，左子树就是小
			Node* pLeft = pq.top();
			pq.pop();

			Node* pRight = pq.top();
			pq.pop();

			// 2.2 利用左右子树节点，构造新二叉树，并继续放入队列中
			Node* pParent = new Node(pLeft->_weight + pRight->_weight);	// 自定义类型，需要重载对应的运算符
			pParent->_pLeft = pLeft;
			pParent->_pRight = pRight;
			pLeft->_pParent = pParent;
			pRight->_pParent = pParent;

			pq.push(pParent);
		}

		pRoot = pq.top();
	}

3. 通过Huffman树获取每个字节的编码
采用DFS深度有限遍历，将每个叶子结点存放到对应的存储结构中

void CompressionFile::GenerateHuffmanTreeByDFSHelper(HuffmanTreeNode<ByteInfo>* node, std::string chain)
{
	// 截至条件
	if (nullptr == node->_pLeft && nullptr == node->_pRight)
	{
		fileByInfo[node->_weight.ch].strCode = chain;
		return;
	}

	// 候选结点
	if (nullptr != node->_pLeft)
	{
		chain += '0';
		GenerateHuffmanTreeByDFSHelper(node->_pLeft, chain);
		chain.erase(chain.end() - 1);
	}

	if (nullptr != node->_pRight)
	{
		chain += '1';
		GenerateHuffmanTreeByDFSHelper(node->_pRight, chain);
		chain.erase(chain.end() - 1);
	}
}

4. 使用Huffman生成的编码，对源文件进行压缩
压缩时，将解压用到的信息头加入到压缩文件的头部，方便解压缩时根据头部重建Huffman树。

5.2 解压流程

1. 根据压缩文件中的头部信息，重构Huffman树
2. 根据头部信息的后缀，新建解压后文件
3. 根据压缩文件中的二进制数据遍历Huffman树，遍历到叶子结点就恢复出一个字符

• a. 从压缩文件中读取一个字节的获取压缩数据ch
• b. 从根节点开始，按照ch的8个比特位信息从高到低遍历huffman树：该比特位是0，取当前节点的左孩子，否则取右孩子，直到遍历到叶子节点位置，该字符就被解析成功。将解压出的字符写入文件
  如果在遍历huffman过程中，8个比特位已经比较完毕还没有到达叶子节点，从a开始执行
• c. 重复以上过程，直到所有的数据解析完毕。

6. 加密解密流程

加密解密使用的是网上开源的算法，所以这一部分只负责文件IO即可
根据提供的加密解密接口，合适的去调用接口实现对文件的加密解密。

开发时遇到的问题

1. 创建Huffman树时，使用优先级队列创建，创建时采用默认比较方法，Huffman创建出结果错误

采用默认的比较方式，底层是直接拿着数据进行比较，而传入的数据又为指针，所以直接拿着地址去进行比较了。所以需要新建一个关于比较的类，该类中定义仿函数，自定义比较方法。在创建优先级队列时传入该比较方法。

2. 涉及到自定义类型的加减乘除，比较都要重载对应的运算符

在创建Huffman树时，由于忘记重载结点结构的运算符，导致错误频出，建树出现错误，比较权值错误等等

3. 发现好多没有用到的字符全都放入了Huffman树中

创建Huffman树时，由于统计时使用的是256个字节的统计方式，一定会出现一些文件中没有出现过的字符，但是由于没有过滤这些出现次数为0的字符，所以造成了无用结点放入了树中。
在创建时需要过滤到字符出现次数为零的字符，传入一个次数为0的结点，作为无效字符的判断标准。

4. 在压缩时，如果最后一个字节的编码不足8位，那么如果存入的8位数据，在解压时会影响解压结果

解压时，如果解压缩出的字节总数与源文件大小相同那么就说明文件已经解压缩完成了，后面的字符就不要了。源文件的大小起始就是根节点的权值。

5. 中文解压时出现了乱码

因为文件压缩使用的是，ACSII表中的字符，那么如果是这个表中的字符当然没有问题，但是汉字没有在这个表中出现，并且汉字不是一个字节就能显示完的，可能用到了多个字节，而且每个字节都排在了ACSII表中的后面，所以使用char可能就会出现负值(-128~127)，所以将char更改为unsigned char，一个字节8位最大就是255，不会出现负值了。

6. 多行文本解析式出现了问题

经过排查，对比压缩时和解压缩用到的Huffman树，发现对\n的处理存在问题，导致两颗Huffman树的频次信息不同，导致解码时出错。所以更改了读到\n的处理方式，因为读到\n但是没有读到频次信息，消耗掉了一次读取频次机会，就造成了频次信息的错误。

7. 如何判断解压前后两个文件数据是否一致

对比两文件是否相同的工具很多了，随便找一个就能比较

8. 文件解压到一般就停止了解压

经排查发现，文件解压到一般就停止了，是因为在读取源文件时，以文本方式进行读取，而读取到-1，程序就认为读取到了末尾，就停止了读取，解压工作也就停止了。将程序中所有的打开文件方式按照二进制方式的读写打开就可以避免此种问题。

feof()的原理：

• feof()函数，并不是通过读取到文件的EOF来评判，这个文件是否为空。
  一般EOF = -1
• 对feof()来说,它的工作原理是，站在光标所在位置，向后看看还有没有字符。如果有，返回0；如果没有，返回非0。它并不会读取相关信息，只是查看光标后是否还有内容。

9. 关于压缩有没有可能出现压缩结果变大的情况

如果文件中字节的种类多，并且出现次数平均，那么压缩后文件变大的可能性就非常高，Huffman树越接近平衡二叉树，压缩效果就越不明显。
在压缩时，通过Huffman树获取每个字节的Huffman编码，有些字节编码的长度可能小于8个比特位，有些字节的编码长度超过了8个比特位，如果平均下来：编码长度小于8比特位的字节总数 < 编码长度大于8比特位的字节总数，这种情况下压缩结果一定变大