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

huffman压缩

article 2025/3/10 14:54:29

基于GZIP文件压缩

文件压缩是在不丢失有用信息的前提下，缩减数据量以减少存储空间，提高传输、存储火绒处理效率，同时可以对数据加密保护（加密算法），增强数据在传输过程中的安全性

压缩的解压缩的分类有：

有损压缩，可能丢失一些信息，不能还原到与源文件一样的，适合图片压缩，压缩率会更好

无损压缩，压缩后的压缩文件可以被还原成与源文件完全相同的格式

LZ77原理：

发现在文件中的局部范围内，有些语句重复出现，对于重复出现的词语能否想办法让其变短，起到压缩的目的

压缩的过程：

对于文件中规定长度范围内重复出现的词语，可以使用<长度，距离>对方式进行替换

长度：重复文件所占字节

距离：后文中重复出现词语首字节，与前文中重复的词语首字节位置差

eg：

cfvgtbhabcdbtgyhuabcdhuijabcdbnjabcdfrv

cfvgtbhabcdbtgyhu(4,10)huij(5,18)bnj(4,26)frv（真正存储时，不会有括号和逗号）

若没有较长语句重复，但是在字节层面有一些重复

DDAB DDBC DBCD CDCC

一个字节占8个比特位，如果能够给每个字节找一个小于8比特位的编码来一环文件中的字节，以起到压缩的目的

eg：定长编码

A：00   B：01  C：10  D：11

11110001 11110110 11011011 101110110

huffman原理：

字节重复出现的次数不一样，能否让出现多的字节对应编码位数少一些，少的多一些

DDAB DDBC DBCD CDCC DDDD

eg：变长编码

A：1       B：3      C：5    D：11

A：100   B：101  C：11  D：0

所有字符对应的编码都在子节点的位置，因此不会发生某个字符编码是其他字符前缀

树的路径长度：树根到每个结点的路径长度之和

树的带权路径长度WPL：所有叶子结点的带权路径长度之和

WPL最小的二叉树称作最优二叉树或huffman树，即权值大的靠近根

解压缩：

形成编码文件后，可以使用unordered_map<string , char>根据key值也就是string查找到对应的char

也可以利用huffman树解压缩，从根节点走，左0右1，直到到达叶子结点，用这种方法就不用每次查表了，但是要在压缩文件里保存每个字符对应的次数

压缩文件格式：

txt（源文件后缀）

4（字符数量）

A:1

B:3

C:5

D:7

96 DF FC 00

如果直接解压，那么多出来的几位比特位也被解压了，所以需要考虑总文件的大小，控制真正读取的位数

代码实现：

HuffmanTree.h:

#pragma once
#include<vector>
#include<queue>

template<class W>
struct HuffmanTreeNode {
	HuffmanTreeNode<W>* _left;
	HuffmanTreeNode<W>* _right;
	HuffmanTreeNode<W>* _parent;
	W _weight;
	HuffmanTreeNode(const W& weight = W())
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_weight(weight)
	{}
};

template<class W>
struct CompareNode {
	bool operator()(const HuffmanTreeNode<W>* n1, const HuffmanTreeNode<W>* n2){
		return n1->_weight > n2->_weight;
	}
};

template<class W>
class HuffmanTree {
	typedef HuffmanTreeNode<W> Node;
public:
	HuffmanTree()
		:_root(nullptr)
	{}
	HuffmanTree(const std::vector<W>& vw, const W& valid) {
		//添加一个无效的权值

		//std::priority_queue < Node*, std::vector<Node*>, [](Node* left, Node* right) {
		//	return left->_weight > right->_weight;
		//} > q;
		std::priority_queue<Node*, std::vector<Node*>, CompareNode<W>> q;
		for (auto& e: vw) {
			if (valid != e) {
				q.push(new Node(e));
			}
		}
		if (q.empty()) {
			return;
		}
		while (q.size() > 1) {
			//取两个最小结点形成一个新的树
			Node* left = q.top();
			q.pop();
			Node* right = q.top();
			q.pop();
			Node* parent = new Node(left->_weight + right->_weight);

			parent->_left = left;
			left->_parent = parent;

			parent->_right = right;
			right->_parent = parent;
			//将新树的根放入森林
			q.push(parent);
		}
		_root = q.top();
	}
	~HuffmanTree() {
		Destroy(_root);
	}

	Node* GetRoot() {
		return _root;
	}

private:
	void Destroy(Node*& root) {
		if (root) {
			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
			root = nullptr;
		}
	}
	Node* _root;
};

//void TestHuffmanTree() {
//	std::vector<int> v = { 2,4,7,9 };
//	HuffmanTree<int> hv(v);
//}

FileCompressHuffman.h:

#pragma once
#include<string>
#include<vector>
#include"HuffmanTree.h"
#include<iostream>
using std::cout;
using std::cin;
using std::endl;
using std::string;

struct ByteInfo {
	unsigned char _ch;
	size_t _appearCount;
	string _chCode;
	ByteInfo(size_t appearCount = 0)
		:_appearCount(appearCount)
	{}
	ByteInfo operator+(const ByteInfo& x)const {
		return _appearCount + x._appearCount;
	}
	bool operator>(const ByteInfo& x)const {
		return _appearCount > x._appearCount;
	}
	bool operator!=(const ByteInfo& x)const {
		return _appearCount != x._appearCount;
	}
};
class FileCompressHuffman {
public:
	FileCompressHuffman();
	void CompressFile(const string& filePath);
	void UnCompressFile(const string& filePath);

private:
	void GenerateHuffmanCode(HuffmanTreeNode<ByteInfo>* root);
	void WriteHeadInfo(const string& filePath, FILE* fOut);
	string GetFileSuffix(const string& filePath);
	string GetFileName(const string& filePath);
	string GetLine(FILE* fIn);
	//ByteInfo _fileInfo[256];
	std::vector<ByteInfo> _fileInfo;
};

FileCompressHuffmanTree.cpp:

#define  _CRT_SECURE_NO_WARNINGS
#include"FileCompressHuffman.h"

FileCompressHuffman::FileCompressHuffman() {
	_fileInfo.resize(256);
	for (int i = 0; i < 256; ++i) {
		_fileInfo[i]._ch = i;
	}
}
void FileCompressHuffman::CompressFile(const string& filePath) {
	//1.统计源文件中每个字符出现的次数
	FILE* fIn = fopen(filePath.c_str(), "rb");
	if (fIn == nullptr) {
		cout << "待压缩文件打开失败" << endl;
		return;
	}
	unsigned char rdBuff[1024];
	while (true) {
		size_t rdSize = fread(rdBuff, 1, 1024, fIn);
		if (rdSize == 0) {
			break;
		}
		for (size_t i = 0; i < rdSize; ++i) {
			_fileInfo[rdBuff[i]]._appearCount++;
		}
	}
	//2.用统计结果创建huffman树
	//调用默认构造，使得appearCount等于0
	HuffmanTree<ByteInfo> ht(_fileInfo, ByteInfo());

	//3.获取huffman编码
	GenerateHuffmanCode(ht.GetRoot());

	//4.写方便解压的数据信息
	string name = GetFileName(filePath);
	name += "Compress.hz";
	FILE* fout = fopen(name.c_str(), "wb");

	WriteHeadInfo(filePath, fout);

	//5.用获取到的编码对源文件改写
	fseek(fIn, 0, SEEK_SET);//使文件指针从头开始读取

	int bitCount = 0;
	unsigned char bits = 0;
	while (true) {
		size_t rdSize = fread(rdBuff, 1, 1024, fIn);
		if (rdSize == 0)
			break;
		for (size_t i = 0; i < rdSize; ++i) {
			string& strCode = _fileInfo[rdBuff[i]]._chCode;
			for (size_t j = 0; j < strCode.size(); ++j) {
				bits <<= 1;
				if (strCode[j] == '1') {
					bits |= 1;
				}
				bitCount++;
				if (bitCount == 8) {
					fputc(bits, fout);
					bits = 0;
					bitCount = 0;
				}
			}
		}
	}
	//最后一个的8个比特位可能没有满
	if (bitCount > 0 && bitCount < 8) {
		bits <<= (8 - bitCount);
		fputc(bits, fout);
	}
	fclose(fIn);
	fclose(fout);
}
void FileCompressHuffman::UnCompressFile(const string& filePath) {
	if (GetFileSuffix(filePath) != "hz") {
		cout << "压缩文件类型匹配失败" << endl;
		return;
	}
	FILE* fIn = fopen(filePath.c_str(), "rb");
	if (fIn == nullptr) {
		cout << "压缩文件打开失败" << endl;
		return;
	}
	//1.读取后缀
	string UnCompressFileName = GetFileName(filePath) + "Un";
	string suffixFile = GetLine(fIn);
	UnCompressFileName += ".";
	UnCompressFileName += suffixFile;

	//2.读取频次信息总行数
	size_t lineCount = atoi(GetLine(fIn).c_str());
	for (size_t i = 0; i < lineCount; ++i) {
		string str = GetLine(fIn);//A:1
		//注意换行字符的处理
		if (str == "") {
			str += '\n';
			str += GetLine(fIn);
		}
		//_fileInfo[str[0]]._ch = str[0];
		//_fileInfo[str[0]]._appearCount = atoi(str.substr(2).c_str());
		_fileInfo[str[0]]._appearCount = atoi(str.c_str()+2);//都可以
		unsigned char ch = str[0];
		_fileInfo[ch]._ch = ch;
		_fileInfo[ch]._appearCount = atoi(str.substr(2).c_str());
	}
	//3.还原树
	HuffmanTree<ByteInfo> ht(_fileInfo, ByteInfo());

	//4.解压缩
	HuffmanTreeNode<ByteInfo>* cur = ht.GetRoot();
	FILE* fout = fopen(UnCompressFileName.c_str(), "wb");
	size_t Size = 0;
	unsigned char rdBuff[1024];
	while (true) {
		size_t rdSize = fread(rdBuff, 1, 1024, fIn);
		if (rdSize == 0)
			break;
		for (size_t i = 0; i < rdSize; i++) {
			char ch = rdBuff[i];
			for (size_t j = 0; j < 8; j++) {
				if (ch & 0x80)//如果结果为 0，则说明最高位是 0
					//结果是1
					cur = cur->_right;
				else
					cur = cur->_left;
				ch <<= 1;
				//找到叶子结点
				if (cur->_left == nullptr && cur->_right == nullptr) {
					fputc(cur->_weight._ch, fout);
					cur = ht.GetRoot();
					Size++;
					if (Size == cur->_weight._appearCount)
						break;
				}
			}
			
		}
	}
	fclose(fout);
	fclose(fIn);
}

string FileCompressHuffman::GetLine(FILE* fIn) {
	string line;
	char ch;
	while ((ch = fgetc(fIn)) != EOF) {
		//ch = fgetc(fIn);
		if (ch != '\n')
			line += ch;
		else
			break;
	}
	return line;
}

string FileCompressHuffman::GetFileName(const string& filePath) {
	return filePath.substr(0, filePath.rfind('.'));
}


string FileCompressHuffman::GetFileSuffix(const string& filePath) {
	return filePath.substr(filePath.rfind('.') + 1);
}

void FileCompressHuffman::WriteHeadInfo(const string& filePath, FILE* fOut) {
	//1.获取原文件后缀
	string headInfo;
	headInfo += GetFileSuffix(filePath);
	headInfo += '\n';

	//2.获取频次信息
	size_t LineCount = 0;
	string chInfo;
	for (auto e : _fileInfo) {
		if (e._appearCount == 0)
			continue;
		chInfo += e._ch;
		chInfo += ':';
		chInfo += std::to_string(e._appearCount);
		chInfo += '\n';
		LineCount++;
	}
	headInfo += std::to_string(LineCount);
	headInfo += '\n';
	headInfo += chInfo;
	fwrite(headInfo.c_str(), 1, headInfo.size(), fOut);
}

void FileCompressHuffman::GenerateHuffmanCode(HuffmanTreeNode<ByteInfo>* root) {
	if (root == nullptr)
		return;
	GenerateHuffmanCode(root->_left);
	GenerateHuffmanCode(root->_right);

	//找叶子结点
	if (root->_left == nullptr && root->_right == nullptr) {
		string& chCode = _fileInfo[root->_weight._ch]._chCode;
		HuffmanTreeNode<ByteInfo>* cur = root;
		HuffmanTreeNode<ByteInfo>* parent = cur->_parent;
		while (parent) {
			if (parent->_left == cur) {
				chCode += '0';
			}
			else {
				chCode += '1';
			}
			cur = parent;
			parent = cur->_parent;
		}
		reverse(chCode.begin(), chCode.end());
	}
}

Text.cpp:

#define  _CRT_SECURE_NO_WARNINGS
//#include"HuffmanTree.h"
#include"FileCompressHuffman.h"


void menu() {
	cout << "************************************************" << endl;
	cout << "************************************************" << endl;
	cout << "*******    0.退出           *******************" << endl;
	cout << "*******    1.huffman压缩    *******************" << endl;
	cout << "*******    2.huffman解压    *******************" << endl;
	cout << "************************************************" << endl;
	cout << "************************************************" << endl;
}
int main() {
	int input = 0;
	bool isQuit = false;
	FileCompressHuffman fc;
	string fileName;


	while (true) {
		menu();
		cin >> input;
		switch (input)
		{
		case 0:
			isQuit = true;
			break;
		case 1:
			cout << "输入压缩文件名：" << endl;
			cin >> fileName;
			fc.CompressFile(fileName);
			break;
		case 2:
			cout << "输入解压缩文件名：" << endl;
			cin >> fileName;
			fc.UnCompressFile(fileName);
			break;
		}
		if (isQuit)
			break;
	}

	return 0;
}

遇到的问题：

1.读不了换行后的数据

解决：在读取新一行数据时，判断如果取到的是空，说明此时是换行，那么手动加上'\n'，然后再读一遍，取到 :次数，就可以继续正确读取了

2.读不了汉字

常见的汉字编码如 UTF - 8、GBK 等，通常使用多个字节来表示一个汉字。以 UTF - 8 为例，它是一种变长编码，一个汉字可能由 2 到 4 个字节组成，并且这些字节的最高位通常为 1，而char类型通常是 1 个字节，是有符号类型，其取值范围一般是 -128 到 127，也就是说这意味着char的最高位（第 7 位）被用作符号位，0 代表正数，1 代表负数

因为unsigned char是无符号类型，取值范围是 0 到 255。它没有符号位，所有 8 位都用于表示数值

解决：将char换成unsigned char

3.大文件压缩后只有一部分被解压缩了

打开、写入的是文本文件，检测有没有读到末尾，就是看是否到EOF

压缩文件本质是二进制类型的文件，一旦读到文本文件转换成的FF，就认为结束不往后走了

解决：将读取、写入的方式从文本文件改成二进制文件，r/w改成rb/wb

压缩率：

文本文件：

        huffman 约等于37%，zip约等于75%

二进制文件：

        huffman 约等于24%，zip约等于41%

多次压缩的结果可能会改变，也取决于字符种类的多少，字符种类的多少会影响哈夫曼树的结构和数据分布的复杂性。其中，平均下来要是每个字节的编码小于8位，那么文件会变小，要是多余8位，就会变大

扩展：

范式huffman树：

huffman树压缩完成后，必须在压缩文件中保存字节频率信息后，才可以解压缩，如果字节频率信息比较大，也会影响压缩率。且解压时需要通过不断遍历还原的huffman树，效率也会打折扣，因此在工程中一般很少使用huffman直接进行压缩，而是使用范式huffman树

范式huffman树，是在huffman树的基础之上，进行了一些强制性的约定，即：对于同一层节点中，所有的叶子节点都调整到左边，然后，对于同一层的叶子节点按照符号顺序从小到大调整，最后按照左0右1的方式分配编码。

使用范式huffman树，可以提高压缩效率，提高不了压缩率，就不用从叶子往根去推，编码可以算出来，同一层的编码位长一样，从左往右编码加一，下一层编码加一，再左移层数差位

怎么得到编码表？排序字节频率表，以编码位长为第一字段，编码大小为第二字段，不用保存频率，也就是说只需要保存256个字节，同时也不用走递归了

解压缩时，也只需要编码和编码位长，算出编码，得出解码表

zip压缩算法的原理：


http://www.kler.cn/a/567384.html

相关文章：

  • 在idea中使用spring boot devtools开发工具的问题
  • 智能图像处理平台：图像处理配置类
  • 基于机器学习的结构MRI分析：预测轻度认知障碍向阿尔茨海默病的转化
  • 易错点abc
  • 分享一套适合做课设的SpringBoot商城系统
  • Kotlin协变与逆变区别
  • yolov12 部署瑞芯微 rk3588、RKNN 部署工程难度小、模型推理速度快
  • 大模型应用案例 | 大模型+金融运维，擎创携手某证券创新运维能力新范式
  • Proser：新增CRC计算辅助功能
  • 从UNIX到Linux：操作系统进化史与开源革命
  • 加油站小程序实战05地图加载
  • 计算机毕业设计SpringBoot+Vue.js社团管理系统(源码+文档+PPT+讲解)
  • 如何在工控机上实现机器视觉检测？
  • YOLOv11-ultralytics-8.3.67部分代码阅读笔记-loss.py
  • Kubernetes (K8S) 高效使用技巧与实践指南
  • MySQL 主从同步配置及操作步骤
  • 20250226-代码笔记05-class CVRP_Decoder
  • (十 四)趣学设计模式 之 策略模式！
  • 蓝桥杯试题：二分查找数组元素
  • Leetcode-最大矩形（单调栈）