C++實現文件壓縮及解壓縮

    原理：Huffman樹的應用：Huffman編碼，為出現頻率較高的字符指定較短的碼字，而為出現頻率較低的字符指定較短的碼字，可以實現二進制文件的壓縮。

Heap.h

#pragma once

#include <vector>

//仿函數
template<class T>
struct Lesser
{
	bool operator()(const T& l, const T& r)
	{
		return l < r;
	}
};

template<class T>
struct Greater
{
	bool operator()(const T& l, const T& r)
	{
		return l > r;
	}
};

template<class T, class Compare = Lesser<T>>
class Heap
{
public:
	Heap()
	{}

	Heap(const T* a, size_t size)
	{
		for (size_t i = 0; i < size; ++i)
		{
			_a.push_back(a[i]);
		}
		for (int i = (_a.size()-2)/2; i >= 0; --i)
		{
			_AdjustDown(i);
		}
	}

	void Push(const T& x)
	{
		_a.push_back(x);
		_AdjustUp(_a.size()-1);
	}

	void Pop()
	{
		assert(!_a.empty());

		swap(_a[0], _a[_a.size()-1]);
		_a.pop_back();
		_AdjustDown(0);
	}

	T& Top()
	{
		assert(!_a.empty());

		return _a[0];
	}

	bool Empty()
	{
		return _a.empty();
	}

	size_t Size()
	{
		return _a.size();
	}

protected:
	void _AdjustUp(int child)
	{
		Compare cmp;
		int parent = (child-1)/2;

		while (child > 0)//parent>=0 ?
		{
			if (cmp(_a[child], _a[parent]))
			{
				swap(_a[child], _a[parent]);
				child = parent;
				parent = (child-1) / 2;
			}
			else
			{
				break;
			}
		}
	}

	void _AdjustDown(int parent)
	{
		Compare cmp;
		int child = parent*2 + 1;

		while (child < _a.size())
		{
			if (child+1 < _a.size() && cmp(_a[child+1], _a[child]))
			{
				++child;
			}

			if (cmp(_a[child], _a[parent]))
			{
				swap(_a[child], _a[parent]);
				parent = child;
				child = parent*2 + 1;
			}
			else
			{
				break;
			}
		}
	}

protected:
	vector<T> _a;
};

HuffmanTree.h

#pragma once

#include "Heap.h"

template<class T>
struct HuffmanTreeNode
{
	HuffmanTreeNode<T>* _left;
	HuffmanTreeNode<T>* _right;
	HuffmanTreeNode<T>* _parent;
	T _weight;

	HuffmanTreeNode(const T& weight)
		:_left(NULL)
		,_right(NULL)
		,_parent(NULL)
		,_weight(weight)
	{}
};

template<class T>
class HuffmanTree
{
	typedef HuffmanTreeNode<T> Node;

public:
	HuffmanTree()
		:_root(NULL)
	{}

	~HuffmanTree()
	{
		_Destory(_root);
	}

	HuffmanTree(const T* a, size_t size, const T& invalid)
	{
		_root = _CreateTree(a, size, invalid);
	}

	Node* GetRoot()
	{
		return _root;
	}

protected:
	Node* _CreateTree(const T* a,size_t size, const T& invalid)
	{
		assert(a);

		struct Compare
		{
			bool operator()(const Node* l, const Node* r)
			{
				return l->_weight < r->_weight;
			}
		};

		Heap<Node*, Compare> minHeap;
		for (size_t i = 0; i < size; ++i)
		{
			if (a[i] != invalid)
			{
				minHeap.Push(new Node(a[i]));
			}
		}

		while (minHeap.Size() > 1)
		{
			Node* left = minHeap.Top();
			minHeap.Pop();
			Node* right = minHeap.Top();
			minHeap.Pop();

			Node* parent = new Node(left->_weight + right->_weight);
			parent->_left = left;
			parent->_right = right; 
			left->_parent = parent;
			right->_parent = parent;

			minHeap.Push(parent);
		}

		return minHeap.Top();
	}

	void _Destory(Node* root)
	{
		if (root == NULL)
			return;

		_Destory(root->_left);
		_Destory(root->_right);
	}

protected:
	Node* _root;
};

void HuffmanTreeTest()
{
	int a[] = {0,1,2,3,4,5,6,7,8,9};
	HuffmanTree<int> ht(a, 10, -1);

}

FileCompress.h

#pragma once
#include "HuffmanTree.h"
#include <Windows.h>

struct CharInfo
{
	char _ch;
	int _count;
	string _code;

	CharInfo(unsigned char ch = 0)
		:_ch(ch)
		,_count(0)
	{}

	CharInfo operator+(const CharInfo& x)
	{
		CharInfo tmp;
		tmp._count = _count + x._count;
		return tmp;
	}

	bool operator!=(const CharInfo& x) const
	{
		return _count != x._count;
	}

	bool operator<(const CharInfo& x) const
	{
		return _count < x._count;
	}

};

template<class T>
class FileCompress
{
public:
	FileCompress()
	{
		for (size_t i = 0; i < 256; ++i)
		{
			_infos[i] = i;
		}
	}

	void Compress(const char* filename)
	{
		assert(filename);

		FILE* fOutFile = fopen(filename, "rb");
		assert(fOutFile);

		char ch = fgetc(fOutFile);

		int charCount = 0;//統計字符總數
		
		while (!feof(fOutFile))
		{
			++charCount;
			_infos[(unsigned char)ch]._count++;

			ch = fgetc(fOutFile);
		}

		//創建Huffman樹
		CharInfo invalid(0);
		HuffmanTree<CharInfo> t(_infos, 256, invalid);
		//由Huffman樹生成Huffman編碼
		_GenerateHuffmanCode(t.GetRoot());

		//壓縮
		string compressFilename = filename;
		compressFilename += ".compress";
		FILE* fInCompress = fopen(compressFilename.c_str(), "wb");
		assert(fInCompress);

		fseek(fOutFile, 0, SEEK_SET);
		ch = fgetc(fOutFile);
		char value = 0;
		int size = 0;
		while (!feof(fOutFile))
		{
			string& code = _infos[(unsigned char)ch]._code;

			for (size_t i = 0; i < code.size(); ++i)
			{
				value <<= 1;
				
				if (code[i] == '1')
				{
					value |= 1;
				}

				++size;

				if (size == 8)
				{
					fputc(value, fInCompress);
					size = 0;
					value = 0;
				}
			}

			ch = fgetc(fOutFile);
		}

		if (size > 0)//補位
		{
			value <<= (8-size);
			fputc(value, fInCompress);
		}

		//寫配置文件，方便解壓縮時讀取
		string configFilename = filename;
		configFilename += ".config";
		FILE* fInConfig = fopen(configFilename.c_str(), "wb");
		assert(fInConfig);

		string line;
		char buffer[128];
		
		//將字符總數寫入配置文件第一行
		line += itoa(charCount, buffer, 10);
		line += "\n";
		fputs(line.c_str(), fInConfig);
		line.clear();

		for (size_t i = 0; i < 256; ++i)
		{
			if (_infos[i]._count)
			{
				line += _infos[i]._ch;
				line += ',';
				line += itoa(_infos[i]._count, buffer, 10);
				line += '\n';

				fputs(line.c_str(), fInConfig);
			}

			line.clear();
		}

		fclose(fOutFile);
		fclose(fInCompress);
		fclose(fInConfig);
	}

	void UnCompress(const char* filename)
	{
		//讀取配置文件
		string configFilename = filename;
		configFilename += ".config";
		FILE* fOutConfig = fopen(configFilename.c_str(), "rb");
		assert(fOutConfig);

		string line;
		
		//讀取字符總數
		_ReadLine(fOutConfig, line);
		int charCount = atoi(line.c_str());
		line.clear();

		while (_ReadLine(fOutConfig, line))
		{
			if (!line.empty())
			{
				unsigned char ch = line[0];
				_infos[ch]._count = atoi(line.substr(2).c_str());
				
				line.clear();
			}
			else
			{
				line.clear();
				_ReadLine(fOutConfig, line);

				unsigned char ch = '\n';
				_infos[ch]._count = atoi(line.substr(1).c_str());

				line.clear();
			}
		}

		//重建Huffman樹
		CharInfo invalid(0);
		HuffmanTree<CharInfo> t(_infos, 256, invalid);
		
		//讀.compress文件，寫.uncompress文件
		string compressFilename = filename;
		compressFilename += ".compress";
		FILE* fOutCompress = fopen(compressFilename.c_str(), "rb");
		assert(fOutCompress);

		string uncompressFilename = filename;
		uncompressFilename += ".uncompress";
		FILE* fInUncompress = fopen(uncompressFilename.c_str(), "wb");
		assert(fInUncompress);

		HuffmanTreeNode<CharInfo>* root = t.GetRoot();
		HuffmanTreeNode<CharInfo>* cur = root;

		int pos = 7;
		char ch = fgetc(fOutCompress);
		while (1)
		{
			if (ch & (1<<pos))
				cur = cur->_right;
			else
				cur = cur->_left;

			if (cur->_left == NULL && cur->_right == NULL)
			{
				fputc(cur->_weight._ch, fInUncompress);

				cur = root;

				if (--charCount == 0)//字符已讀取完，遇到補位的0不再讀取
				{
					break;
				}
			}

			--pos;
			if (pos == -1)
			{
				ch = fgetc(fOutCompress);
				pos = 7;
			}
		}

		fclose(fOutCompress);
		fclose(fInUncompress);

	}


protected:
	void _GenerateHuffmanCode(HuffmanTreeNode<CharInfo>* root)
	{
		if (root == NULL)
			return;
		
		_GenerateHuffmanCode(root->_left);
		_GenerateHuffmanCode(root->_right);

		if (root->_left == NULL && root->_right == NULL)
		{
			HuffmanTreeNode<CharInfo>* cur = root;
			HuffmanTreeNode<CharInfo>* parent = root->_parent;
			string& code = _infos[(unsigned char)cur->_weight._ch]._code;

			while (parent)
			{
				if (parent->_left == cur)
					code += '0';
				if (parent->_right == cur)
					code += '1';

				cur = parent;
				parent = cur->_parent;
			}

			reverse(code.begin(), code.end());
		}

	}

	bool _ReadLine(FILE* filename, string& line)
	{
		char ch = fgetc(filename);
		
		if (ch == EOF)
			return false;

		while (ch != EOF && ch != '\n')
		{
			line += ch;
			ch = fgetc(filename);
		}

		return true;
	}

protected:
	CharInfo _infos[256];
};

void CompressTest()
{
	//壓縮
	FileCompress<CharInfo> compress;

	int CompressBegin = GetTickCount();

	compress.Compress("Input.BIG");

	int CompressEnd = GetTickCount();

	cout<<"壓縮用時："<<CompressEnd-CompressBegin<<" ms"<<endl;
}

void UncompressTest()
{
	//解壓縮
	FileCompress<CharInfo> uncompress;

	int UncompressBegin = GetTickCount();

	uncompress.UnCompress("Input.BIG");

	int UncompressEnd = GetTickCount();

	cout<<"解壓縮用時："<<UncompressEnd-UncompressBegin<<" ms"<<endl;
}

Test.cpp

#include <iostream>
using namespace std;
#include <assert.h>

#include "FileCompress.h"

int main()
{
	CompressTest();

	UncompressTest();
	return 0;
}

下面是對一個大小為8.04MB文件的測試：

結果成功壓縮、解壓縮：

壓縮后的文件大小：

壓縮后的文件：

配置文件：

用Beyond Compare文本比較工具檢查原文件與解壓后的文件：

無差異