标签搜索

目 录CONTENT

文章目录

基于Huffman算法的文件解压缩.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 7 阅读 / 4,570 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

基于Huffman算法和LZ77算法的文件压缩(三)

基于Huffman算法和LZ77算法的文件压缩(一)
基于Huffman算法和LZ77算法的文件压缩(二)讲解Huffman压缩的基本原理和文件压缩的整个过程,接下来讲解文件解压缩的过程

一、 利用huffman编码对源文件进行解压缩

解压缩的整个流程:

  1. 从压缩文件中获取源文件的后缀
  2. 从压缩文件中获取字符次数的总行数
  3. 获取每个字符出现的次数
  4. 重建huffman树
  5. 解压缩

二. 从压缩文件中获取源文件的后缀

如果想要解压缩文件那么就需要Huffman树如果需要Huffman树就需要字符频度信息,最后还要把解压缩出来的数据保存在文件中,就需要获取文件后缀信息。那么这些标记信息已经在压缩文件的时候写入到压缩文件当中,接下来直接读取即可。

为了方便读取一行,先封装一个函数:

//读一行函数
void FileCompressHuffman::ReadLine(FILE* fIn, std::string& strInfo) 
{
	assert(fIn);

  //注意这里的feof是针对二进制文件的,因为我们为了解决可以压缩汉字的相关问题,
  //选择以二进制的方式打开,并不是以文本文件的方式打开,文本文件的结束标识是EOF,
  //而二进制文件的结束标识是FEOF
	while (!feof(fIn))
	{
		char ch = fgetc(fIn);
		if (ch == '\n')
			break;
		strInfo += ch;
	}
}

注意:

  • 注意这里的feof是针对二进制文件的,因为我们为了解决可以压缩汉字的相关问题,选择==以二进制的方式打开,并不是以文本文件的方式打开,文本文件的结束标识是EOF,而二进制文件的结束标识是FEOF==

读取文件后缀

//文件后缀
	std::string strFilePostFix;
	ReadLine(fIn, strFilePostFix);

三. 从压缩文件中获取字符次数的总行数

//读取文件数据的行数
	std::string strCount;
	ReadLine(fIn, strCount);
	int lineCount = atoi(strCount.c_str());

四. 获取每个字符出现的次数信息

for (int i = 0; i < lineCount; ++i) 
  {
    //记录读取每一行的数据
		std::string strchCount;
		ReadLine(fIn, strchCount);

    //如果读到的数据为空,说明可能读到了换行符
		if (strchCount.empty()) 
       {
			strchCount += '\n';
			ReadLine(fIn, strchCount);
		}

    //因为数据的格式是 A:3,记录读取到的相关字符信息方便构建哈夫曼树,
		_fileInfo[(unsigned char)strchCount[0]]._count = atoi(strchCount.c_str() + 2);
	}

注意:

  • 如果文件当中含有多行(即有人为换行),需要再向后读取一行,因为我们封装的ReadLine函数是遇到换行就break掉,没有成功把换行读到缓冲区当中,所以需要if (strchCount.empty())判断,如果没有读取到任何字符,就代表读取到了换行符,就把换行符追加到strchCount,再向下读取一行获取换行符的出现次数

五. 重建huffman树

HuffmanTree<CharInfo> t;
	t.CreateHuffmanTree(_fileInfo, CharInfo(0));//构建哈夫曼树

六. 解压缩

//解压缩后的文件名
	std::string newFileName = "3" + strFilePostFix;

	FILE* fOut = fopen(newFileName.c_str(), "wb");
  if(fOut == nullptr)
  {
    perror("open file is error\n");
    return ;
  }

	char *pReadBuff = new char[1024];
	char ch = 0;
	HuffmanTreeNode<CharInfo>* pCur = t.GetRoot();//拿到根节点,也就拿到了整个哈夫曼树的权值之和
	size_t fileSize = pCur->_Weight._count;//记录待解压的总字节数
	size_t unCount = 0;//记录已经解压字符的个数
	while (1) 
  {
		size_t rdsize = fread(pReadBuff, 1, 1024, fIn);
		if (rdsize == 0) 
    {
			break;
		}
    
		for (size_t i = 0; i < rdsize; ++i) 
    {
			ch = pReadBuff[i];
			for (int pos = 0; pos < 8; ++pos) 
      {
        //0x80--->1000 0000 所以是用来判断一个字节的高位是1还是0的
        //规定 1--->往哈夫曼树的右子树走  0--->往哈夫曼树的左子树走
				if (ch & 0x80) 
        		{
					pCur = pCur->_pRight;
				}
				else 
        		{
					pCur = pCur->_pLeft;
				}

				ch <<= 1;

        //如果pCur左右孩子都为空,说明走到叶子节点了,就可以获取到具体的字符了
				if (nullptr == pCur->_pLeft && nullptr == pCur->_pRight) 
       			{
					++unCount;
					fputc(pCur->_Weight._ch, fOut);
					pCur = t.GetRoot();

          //因为每次不一定刚好是整字节数,所以防止多读,需要进行判断
					if (unCount == fileSize)
						break;

				}
			}
		}

注意:

  • 规定1往右走,0往左走,当走到叶子节点的时候,就把解压出来的字符写入到解压缩文件当中
  • 因为存储字符信息的时候是一个字节一个字节存储的,即8bite,如果我们知道每个bite位为0还是为1,就可以控制其在Huffman中是朝左走,还是朝有走,最后走到叶子节点拿到字符信息,所以我们 ==&0x80(1000 0000)== ,如果结果为真代表该bite位为1,反之为0,这样就可以控制走 向了
  • 最后还要 根据Huffman树根节点的权值信息来获取到整个文件的大小,防止最后一个bit位解压过头, 在每成功解压出一个数据后,就对++unCount,最后判断unCount和fileSize的大小,如果相等就代表已经全部解压出来,后序bit位不是压缩数据
  • 最最最最后再说一次,==保存字符信息的相关变量要用unisigned char类型,不能用char类型==,否则在压缩或解压缩汉字时会报错
  • ==文本文件的末尾标志是EOF(-1),而压缩文件的结果是有可能FF的情况(即1111 1111 ...,32个1),那么在文本文件当中在$if(!EOF())$判断的时候就会意外终止,所以需要以二进制的方式读写文件==

解压缩完整代码

//解压缩
void FileCompressHuffman::UnCompressFile(const std::string& path) {
	FILE* fIn = fopen(path.c_str(), "rb");
	if (nullptr == fIn) {
		//assert(false);
    perror("open file is error");
		return;
	}

  //文件后缀
	std::string strFilePostFix;
	ReadLine(fIn, strFilePostFix);

  //读取文件数据的行数
	std::string strCount;
	ReadLine(fIn, strCount);

	int lineCount = atoi(strCount.c_str());
	for (int i = 0; i < lineCount; ++i) 
  {
    //记录读取每一行的数据
		std::string strchCount;
		ReadLine(fIn, strchCount);

    //如果读到的数据为空,说明可能读到了换行符
		if (strchCount.empty()) 
    {
			strchCount += '\n';
			ReadLine(fIn, strchCount);
		}

    //因为数据的格式是 A:3,记录读取到的相关字符信息方便构建哈夫曼树,
		_fileInfo[(unsigned char)strchCount[0]]._count = atoi(strchCount.c_str() + 2);
	}

	HuffmanTree<CharInfo> t;
	t.CreateHuffmanTree(_fileInfo, CharInfo(0));//构建哈夫曼树

  //解压缩后的文件名
	std::string newFileName = "3" + strFilePostFix;

	FILE* fOut = fopen(newFileName.c_str(), "wb");
  if(fOut == nullptr)
  {
    perror("open file is error\n");
    return ;
  }

	char *pReadBuff = new char[1024];
	char ch = 0;
	HuffmanTreeNode<CharInfo>* pCur = t.GetRoot();//拿到根节点,也就拿到了整个哈夫曼树的权值之和
	size_t fileSize = pCur->_Weight._count;//记录待解压的总字节数
	size_t unCount = 0;//记录已经解压字符的个数
	while (1) 
  {
		size_t rdsize = fread(pReadBuff, 1, 1024, fIn);
		if (rdsize == 0) 
    {
			break;
		}
    
		for (size_t i = 0; i < rdsize; ++i) 
    {
			ch = pReadBuff[i];
			for (int pos = 0; pos < 8; ++pos) 
      {
        //0x80--->1000 0000 所以是用来判断一个字节的高位是1还是0的
        //规定 1--->往哈夫曼树的右子树走  0--->往哈夫曼树的左子树走
				if (ch & 0x80) 
        {
					pCur = pCur->_pRight;
				}
				else 
        {
					pCur = pCur->_pLeft;
				}

				ch <<= 1;

        //如果pCur左右孩子都为空,说明走到叶子节点了,就可以获取到具体的字符了
				if (nullptr == pCur->_pLeft&&nullptr == pCur->_pRight) 
        {
					++unCount;
					fputc(pCur->_Weight._ch, fOut);
					pCur = t.GetRoot();

          //因为每次不一定刚好是整字节数,所以防止多读,需要进行判断
					if (unCount == fileSize)
						break;

				}
			}
		}

	}
	fclose(fIn);
	fclose(fOut);
	delete[] pReadBuff;
}

基于Huffman压缩还存在的问题:

  • 无法压缩视屏、图片、音频文件,只能压缩文本文件,压缩视频、图片等文件会发现压缩后等文件变大
0

评论区