当前位置： 首页 > news >正文

数据结构-压缩软件核心（利用哈夫曼树进行编码，对文件进行压缩与解压缩）

news 来源：原创 2024/4/29 4:16:31

文章目录

  • 压缩原件原理
  • 1. 利用哈夫曼树编码
    • 项目需要的头文件及声明common.h
    • 自定义每个字符结构体charactor.h
    • 创建哈夫曼树hufftree.h
    • 利用哈夫曼树创建哈夫曼编码encoding.h
  • 2. 编码完成后将生成的字典和原文件写入压缩文件中Zip.h
  • 3. 读取压缩文件中的字段，还原哈夫曼编码decoding.h
  • 4. 利用还原的哈夫曼树和哈夫曼编码解压缩Zip.h
  • 测试结果
    • 代码位置

压缩原件原理

前言：

  1. 压缩的原理是，把文件中的字符通过特定的编码方式保存起来，将其写入到文件中。
  2. 解压原理：根据文件的压缩规则，读取压缩后的文件，将原来的字符还原出来

eg：
原文件内容为 abbccc

  1. a对应编码11
  2. b对应编码10
  3. c对应编码0

（编码的每一个数字代表一个比特位）
这样原文件内容经过压缩后变为
11101000 00000000
不足8比特的补足8比特，也就是只需要2字节就可以保存原文件的内容了

同时可以观察到，出现次数越多的字符，编码格式最好越短。

  1. 这样的编码方式与哈夫曼树类似，哈夫曼树权值越大的节点越靠近根。
  2. 哈夫曼树只有叶子节点保存数据，所以我们可以根据根节点到叶子节点的顺序对字符进行编码

eg：
abbccc
a出现次数1次
b出现次数2次
c出现次数3次
编码过程如下：
在这里插入图片描述

所以：我们设计压缩软件流程如下：
1编码表示数据 2 出现次数多编码短,出现次数少编码长

压缩流程

  1. 分析待压缩文件,获取文件中出现的字符，字符出现次数.将这些数据组织成字典
  2. 根据字典创建哈夫曼树（核心）
  3. 根据哈夫曼树获取哈夫曼编码并写入字典中
  4. 把哈夫曼编码写入文件中

解压过程

  1. 将文件中的字典读取出来,根据字典生成哈夫曼树
  2. 按照字节读取文件,按照二进制位分析，将对应的字符写入到解压文件
  3. 关闭文件

1. 利用哈夫曼树编码

项目需要的头文件及声明common.h

#pragma once

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<string>
#include<stdio.h>
#include<assert.h>
#include<fstream>

自定义每个字符结构体charactor.h

每个字符结构体应该包括：

  1. 这个字符是什么
  2. 字符在要压缩的文件中出现次数
  3. 这个字符的哈夫曼编码
  4. 这个字符在字符字典中的位置

同时还需要一个字符字典，用于查阅每个字符对应的哈夫曼编码。同时，通过这个字典还可以找到文件中出现多少个字符。

#pragma once

#include"common.h"
//字符结构体
struct Char {
	char _character;//字符
	unsigned int _times;//字符出现次数
	std::string _code;//哈夫曼编码
	int _index;//这个字符在字符字典中的位置
	Char() = default;
	Char(char ch, int times, int index = -1)
		:_character(ch), _times(times), _index(index)
	{}
};

//字符索引，保存的是每个字符的编码，出现的字符
struct CharDict {
	int _cout = 0;//出现过的字符个数,最大MAXCHAR个
	std::vector<Char>_CharArray;//每个字符数组
};

创建哈夫曼树hufftree.h

思路：假设字典中又5类字符

  1. 首先根据找到出现次数最小的字符节点，和出现次数第二小的字符节点，这两个节点构造父节点。
  2. 新构造的父节点覆盖出现次数最少节点，出现次数第二小的字符节点制空，不参与下次循环。
  3. 之后循环上面两布，循环4次（因为字典有5类字符）
#pragma once
#include"common.h"
#include"charactor.h"

struct TreeNode {
	Char _data;
	TreeNode* _left = nullptr;
	TreeNode* _right = nullptr;
	TreeNode* _parent = nullptr;
	TreeNode(const Char&msg):
		_data(msg)
	{}
	bool _isLeaf() {
		return (_left == nullptr) && (_right == nullptr);
	}
};

class HufTree {
	typedef TreeNode Node;
	friend class Encode;
	friend class UnZip;
private:
	Node* _root = nullptr;
public:

	void creatHufTree(CharDict& dict) {
		//储存所有字符节点
		std::vector<Node*>NodeArray(dict._cout);
		Node* node = nullptr;
		for (int i = 0; i < dict._cout; i++) {
			NodeArray[i] = new Node(dict._CharArray[i]);
			//设置字符在字典中的下标
			NodeArray[i]->_data._index = i;
			dict._CharArray[i]._index = i;
		}
		
		//循环创建哈夫曼树节点 
		//如果只有一个节点
		if (dict._cout == 1) {
			_root = NodeArray[0];
		}
		else {

			//找出现次数最小的和第二小的节点
			for (int time = 0; time < dict._cout - 1; time++) {
				int minIndex = 0;
				int minSecIndex = 0;
				while (NodeArray[minIndex] == nullptr) {
					minIndex++;
				}
				for (int i = 0; i < dict._cout; i++) {
					//使用父节点结合两个节点，替换最小的节点，删除第二小的节点
					if (NodeArray[i] != nullptr && NodeArray[i]->_data._times < NodeArray[minIndex]->_data._times) {
						minIndex = i;
					}
				}
				//找次小值
				while (NodeArray[minSecIndex] == nullptr || minIndex == minSecIndex) {
					minSecIndex++;
				}
				for (int i = 0; i < dict._cout; i++) {
					if (i != minIndex) {
						if (NodeArray[i] != nullptr && NodeArray[i]->_data._times < NodeArray[minSecIndex]->_data._times) {
							minSecIndex = i;
						}
					}
				}
				/*printf("出现次数最小的字符是%c,出现次数%d\n",NodeArray[minIndex]->_data._character, NodeArray[minIndex]->_data._times);
				printf("出现次数次少的字符是%c,出现次数为%d\n", NodeArray[minSecIndex]->_data._character, NodeArray[minSecIndex]->_data._times);
				printf("============\n");*/
				//创建空节点
				_root = new Node(Char(0, NodeArray[minIndex]->_data._times + NodeArray[minSecIndex]->_data._times));

				//链接节点
				NodeArray[minIndex]->_parent = _root;
				NodeArray[minSecIndex]->_parent = _root;
				_root->_left = NodeArray[minIndex];
				_root->_right = NodeArray[minSecIndex];

				//覆盖数组最小位置，第二小位置制空
				NodeArray[minIndex] = _root;
				NodeArray[minSecIndex] = nullptr;
			}
		}
	}
};

利用哈夫曼树创建哈夫曼编码encoding.h

思路：

  1. 打开原文件，按照字节读取文件，统计文件中每个字符出现的次数
  2. 根据每个字符出现次数调用HufTree类的方法创建哈夫曼树
  3. 根据字符在树的位置，倒着遍历到根节点，创建哈夫曼编码
#pragma once

#include"common.h"
#include"charactor.h"
#include"hufftree.h"
#include"Zip.h"

class Encode {
	friend class GZip;
private:
	HufTree _tree;
	std::string _srcFile;
	CharDict _dict;
	//检测字符是出现过,返回字符所在字典的位置
public:
	Encode(std::string&srcFile)
		:_srcFile(srcFile)
	{
		_anylizeFile();
		_tree.creatHufTree(_dict);
		_creatHuffCode();
	}
private:
	//测试字典是否正确
	void _TestDict() {
		printf("共有%d个字符\n", _dict._cout);
		for (int i = 0; i < _dict._cout; i++) {
			printf("字符%c出现了%d次\n", _dict._CharArray[i]._character, _dict._CharArray[i]._times);
		}
	}
	//测试字符的哈夫曼编码
	void _TestHuffCode() {
		for (int i = 0; i < _dict._cout; i++) {
			printf("字符%c的编码为%s\n", _dict._CharArray[i]._character,_dict._CharArray[i]._code.c_str());
		}
	}
	int _findChar(const char ch) {
		for (int i = 0; i < _dict._cout; i++) {
			if (_dict._CharArray[i]._character == ch) {
				return i;
			}
		}
		return -1;
	}
	//分析文件
	void _anylizeFile() {
		FILE* fp = fopen(_srcFile.c_str(), "rb");
		if (fp == nullptr) {
			printf("%s文件打开失败", _srcFile.c_str());
		}
		assert(fp != nullptr);
		//循环按字节读取文件数据
		char ch = ' ';
		int readNum = 0;
		while (true) {
			readNum = fread(&ch, 1, 1, fp);
			if (readNum != 1) {//读取完毕
				break;
			}
			//统计字符出现次数
			int pos = _findChar(ch);
			if (pos == -1) {
				//没有出现过
				_dict._cout++;
				_dict._CharArray.push_back(Char(ch, 1));
			}
			else {
				//出现过
				_dict._CharArray[pos]._times++;
			}
		}
		fclose(fp);
	}

	//创建哈夫曼编码,遍历哈夫曼树，遍历到叶子节点，左子树设置为1，右子树设置为0
	void _setHuffCode(TreeNode* root) {
		//向上走,判断其是左孩子还是右孩子,左孩子编码为1，右孩子编码为0。最后再反转一下数组即可
		TreeNode* node = root;
		std::string& code = root->_data._code;
		while (node->_parent != nullptr) {
			if (node == node->_parent->_left) {
				code.push_back('1');
			}
			else {
				code.push_back('0');
			}
			node = node->_parent;
		}
		std::reverse(code.begin(), code.end());
		//修改字典值
		_dict._CharArray[root->_data._index]._code = code;
	}
	void _creatHuffCode() {
		_creatHuffCode(_tree._root);
	}
	void _creatHuffCode(TreeNode* root) {
		if (root != nullptr) {
			if (root->_isLeaf()) {
				//遍历到叶子节点，设置哈夫曼编码
				_setHuffCode(root);
			}
			else {
				//遍历左子树
				_creatHuffCode(root->_left);
				//遍历右子树
				_creatHuffCode(root->_right);
			}
		}
	}
	std::string _getHufCharCode(char ch) {
		for (int i = 0; i < _dict._cout; i++) {
			Char msg = _dict._CharArray[i];
			if (msg._character== ch) {
				return msg._code;
			}
		}
		return "-1";
	}
};

2. 编码完成后将生成的字典和原文件写入压缩文件中Zip.h

注意：

  1. 将编码转化为比特位是这一步的重点
  2. 同时写入压缩文件的字典需要自定义协议，方便解压缩读取
/*
* 压缩流程
1.分析待压缩文件,获取文件中出现的字符，字符出现次数.将这些数据组织成字典
2.根据字典创建哈夫曼树（核心）
3.根据哈夫曼树获取哈夫曼编码并写入字典中
4.把哈夫曼编码写入文件中
*/
#pragma once
#include"encoding.h"
#include"decoding.h"

class GZip {
private:
	Encode _encode;
public:
	GZip(std::string& srcFile)
		:_encode(srcFile)
	{}
	//保存压缩后哈夫曼编码写到文件中
	void ZipFile(const std::string& destPath) {
		//将编码组合成8位的位运算,最后编码不足8位填0即可
		//循环读取源文件字节，找到HuffCode，凑齐8位写入destPath文件中

		std::fstream fpSrc(_encode._srcFile, std::ios::in | std::ios::binary);
		if (!fpSrc.is_open()) {
			printf("DEAD:待压缩文件丢失");
			return;
		}
		std::ofstream fpDst(destPath, std::ios::out | std::ios::app | std::ios::binary);
		if (!fpDst.is_open()) {
			printf("DEAD:目标压缩路径丢失");
			return;
		}

		//将字典写入文件中
		for (int i = 0; i < _encode._dict._cout; i++) {
			Char msg = _encode._dict._CharArray[i];
			fpDst << msg._character << ";" << msg._code << ";" << msg._index << ";" << msg._times << ";\n";
		}
		fpDst << "-\n";//字典结束的标志

		char ch = 0;

		//判断是否读取完毕
		bool isEnd = false;
		//记录处理的哈夫曼编码位置
		size_t indexHufCode = 0;
		//记录处理到第几位了
		size_t indexWrite = 0;
		//记录字符的哈夫曼编码
		std::string HufCode;

		while (true) {
			if (indexHufCode == HufCode.size()) {
				fpSrc.read(&ch, 1);
				//获取某个字符的哈夫曼编码
				//std::cout << ch << ":" << _getHufCharCode(ch) << std::endl;
				HufCode = _encode._getHufCharCode(ch);
				indexHufCode = 0;
			}

			indexWrite = 0;

			//8字节写入一次
			int bite = 0;

			//储存要写入的数据
			char write = 0;

			while (bite < 8) {
				if (indexHufCode < HufCode.size()) {
					if (HufCode[indexHufCode] == '0') {
						//设置对应位为0
						write &= ~(1 << (7 - indexWrite));
					}
					else if (HufCode[indexHufCode] == '1') {
						//设置对应位为1
						write |= (1 << (7 - indexWrite));
					}
					bite++;
					indexWrite++;
					indexHufCode++;
				}
				else {
					//这个字符已经读取完毕了
					if (fpSrc.read(&ch, 1)) {
						HufCode = _encode._getHufCharCode(ch);
						indexHufCode = 0;
					}
					else {
						//文件已经读取完毕了
						isEnd = true;
						break;
					}
				}
			}
			fpDst << write;

			//测试写入的数据是否正确,一个字节8比特位,打印每个比特位
			char test_write = write;
			for (int i = 0; i < 8; i++) {
				//0x80 :1000 0000
				if ((test_write & 0x80) == 0x80) {
					printf("%d", 1);
				}
				else {
					printf("%d", 0);
				}
				test_write <<= 1;
			}

			printf("\n");

			if (isEnd == true) {
				break;
			}
		}
		fpSrc.close();
		fpDst.close();
	}
};

3. 读取压缩文件中的字段，还原哈夫曼编码decoding.h

按照自定义的协议从文件中读取字典即可

#pragma once

#include"hufftree.h"
#include"charactor.h"

class Decode {
	friend class UnZip;
public:
	Decode(std::string& srcFile) {
		_anylizeFile(srcFile);
		_tree.creatHufTree(_dict);
	}

	//通过key找到对应字符
	char findchar(std::string& key) {
		for (int i = 0; i < _dict._cout; i++) {
			if (_dict._CharArray[i]._code == key) {
				return _dict._CharArray[i]._character;
			}
		}
		return -1;
	}

	//返回总共的字符数
	int allAlph() {
		int ret = 0;
		for (int i = 0; i < _dict._cout; i++) {
			ret += _dict._CharArray[i]._times;
		}
		return ret;
	}
private:
	CharDict _dict;
	std::string _srcFile;//解压后的文件保存路径
	HufTree _tree;

	//分析压缩文件
	void _redictDict(CharDict& dict, std::string& readLine) {
		assert(readLine.size() > 0);
		Char msg;
		int begin = 0;
		int flag = 0;//标记还原到那个属性
		for (int i = 0; i < readLine.size(); i++) {
			if (readLine[i] != ';') {
				continue;
			}
			else {
				if (flag == 0) {
					msg._character = readLine[0];
				}
				else if (flag == 1) {
					msg._code = readLine.substr(begin, i - begin);
				}
				else if (flag == 2) {
					msg._index = atoi(readLine.substr(begin, i - begin).c_str());
				}
				else {
					msg._times = atoi(readLine.substr(begin, i - begin).c_str());
				}
				begin = i + 1;
				flag++;
			}
		}
		_dict._CharArray.push_back(msg);
		_dict._cout++;
	}
	void _anylizeFile(std::string& srcFile) {
		_srcFile = srcFile;
		std::fstream fpSrc(_srcFile, std::ios::in | std::ios::binary);
		if (!fpSrc.is_open()) {
			printf("DEAD:压缩文件丢失");
			return;
		}
		std::string readLine;
		//还原字典
		while (true) {
			std::getline(fpSrc, readLine);
			if (readLine=="-") {
				//字典已经全部读取完毕了
				break;
			}
			_redictDict(_dict,readLine);
		}
		fpSrc.close();
		_TestDict();
		_TestHuffCode();
	}
public:

	//测试字典是否正确
	void _TestDict() {

		printf("共有%d个字符\n", _dict._cout);
		for (int i = 0; i < _dict._cout; i++) {
			printf("字符%c出现了%d次\n", _dict._CharArray[i]._character, _dict._CharArray[i]._times);
		}
	}
	//测试字符的哈夫曼编码
	void _TestHuffCode() {
		for (int i = 0; i < _dict._cout; i++) {
			printf("字符%c的编码为%s\n", _dict._CharArray[i]._character, _dict._CharArray[i]._code.c_str());
		}
	}
};

4. 利用还原的哈夫曼树和哈夫曼编码解压缩Zip.h

思路：

  1. 先统计原文件应该有多少个字符
  2. 定位压缩文件的内容部分，按照字节分析，如果能够走到哈夫曼树的叶子节点就可以还原这个字符。
/*
解压过程
1.将文件中的字典读取出来,根据字典生成哈夫曼树
2.按照字节读取文件,按照二进制位分析，将对应的字符写入到解压文件
3.关闭文件
*/
class UnZip {
private:
	Decode _decode;
public:
	UnZip(std::string& destPath)
		:_decode(destPath)
	{}
	//解压缩文件
	void UnzipFile(const std::string& destPath) {
		/*_decode._anylizeFile(destPath);
		_decode._TestDict();
		_decode._TestHuffCode();*/
		//定位到正文部分
		FILE* fp = fopen(destPath.c_str(), "rb");
		char ch = 0;
		int readNum = 0;
		while (true) {
			readNum = fread(&ch, 1, 1, fp);
			assert(readNum != 0);
			if (ch == '-') {
				break;
			}
		}
		//把换行符读取掉
		readNum = fread(&ch, 1, 1, fp);
		assert(readNum == 1);


		//定位到正文了,读取到正文结束
		HufTree tree = _decode._tree;
		TreeNode* node = tree._root;

		//还原文件
		FILE* redict_fp = fopen("还原文件.txt", "w");

		std::string key;
		bool isFinish = false;//判断是否读取完毕

		int allAlph = _decode.allAlph();
		while (true) {
			readNum = fread(&ch, 1, 1, fp);
			if (readNum == 0) {
				break;
			}
			int num = ch;
			for (int i = 0; i < 8; i++) {
				//获取每一位
				if ((ch & 0x80) == 0x80) {
					node = node->_left;
					key.push_back('1');
				}
				else if ((ch & 0x80) == 0) {
					node = node->_right;
					key.push_back('0');
				}
				ch <<= 1;
				if (node->_isLeaf()) {
					char write = _decode.findchar(key);
					if (write == -1) {
						break;
					}
					fwrite(&write, 1, 1, redict_fp);
					node = tree._root;
					key.clear();
					allAlph -= 1;
					if (allAlph == 0) {
						isFinish = true;
						break;
					}
				}
			}
			if (isFinish == true) {
				break;
			}
		}
		fclose(redict_fp);
	}
};

测试结果

在这里插入图片描述

代码位置

Github

相关文章：

  • 月薪12.8K，零基础转行软件测试5月斩获3份过万offer，分享一些我的秘招~
  • 推荐一款新式开源的反向代理工具（FRP）
  • 复习一：基本概念和术语
  • Vue基础自学系列 | webpack中的插件
  • 稻盛和夫：让年轻人脱胎换骨的6条自我提升原则
  • HTML5新特性 day_02(8.8)
  • springboot2.0 配置ssl证书详解
  • 客群画像|解决分群与特征分类问题，试一下这个处理方法
  • 【cmake实战六】如何使用编译的库（动态库dll）——windows系统
  • 【vue3源码】九、ref源码解析
  • Input系统学习-----injectInputEvent注入事件调用流程
  • Java项目：SSM物业缴费管理系统
  • 函数指针（函数作为参数传递给其他函数）
  • 2023考研推荐新闻传播专业入门可以看的好书
  • 解决Long类型web前端精度丢失问题
  • bootstrap创建登录注册页面
  • CSS盒模型深入
  • CSS选择器——伪元素选择器之处理父元素高度及外边距溢出
  • exports和module.exports
  • Intervention/image 图片处理扩展包的安装和使用
  • Making An Indicator With Pure CSS
  • niucms就是以城市为分割单位，在上面 小区/乡村/同城论坛+58+团购
  • Vue.js源码（2）：初探List Rendering
  • 彻底搞懂浏览器Event-loop
  • 对话 CTO〡听神策数据 CTO 曹犟描绘数据分析行业的无限可能
  • 基于 Babel 的 npm 包最小化设置
  • 基于游标的分页接口实现
  • 快速体验 Sentinel 集群限流功能，只需简单几步
  • 聊聊flink的TableFactory
  • 要让cordova项目适配iphoneX + ios11.4，总共要几步？三步
  • 正则与JS中的正则
  • “十年磨一剑”--有赞的HBase平台实践和应用之路 ...
  • JavaScript 新语法详解：Class 的私有属性与私有方法 ...
  • ​​​​​​​ubuntu16.04 fastreid训练过程
  • ​Distil-Whisper：比Whisper快6倍，体积小50%的语音识别模型
  • !!【OpenCV学习】计算两幅图像的重叠区域
  • ###51单片机学习（2）-----如何通过C语言运用延时函数设计LED流水灯
  • （16）Reactor的测试——响应式Spring的道法术器
  • (zhuan) 一些RL的文献（及笔记）
  • （二）【Jmeter】专栏实战项目靶场drupal部署
  • （一）spring cloud微服务分布式云架构 - Spring Cloud简介
  • （转）程序员技术练级攻略
  • **PyTorch月学习计划 - 第一周；第6-7天: 自动梯度（Autograd）**
  • .NET 5.0正式发布，有什么功能特性(翻译)
  • .NET Core 中的路径问题
  • .Net Framework 4.x 程序到底运行在哪个 CLR 版本之上
  • .NET 将混合了多个不同平台（Windows Mac Linux）的文件 目录的路径格式化成同一个平台下的路径
  • .NET/C# 利用 Walterlv.WeakEvents 高性能地中转一个自定义的弱事件（可让任意 CLR 事件成为弱事件）
  • @Builder用法
  • @NestedConfigurationProperty 注解用法
  • @Transactional 详解
  • @拔赤：Web前端开发十日谈
  • [ NOI 2001 ] 食物链
  • [23] GaussianAvatars: Photorealistic Head Avatars with Rigged 3D Gaussians
  • [AIR] NativeExtension在IOS下的开发实例 --- IOS项目的创建 (一)