文件压缩 ——— Huffman

文件压缩  —— Huffman

我用自己实现的堆和Huffman树，开始着手对文件里面的内容进行一系列操作

压缩原理：由huffman的贪心决定

创建一个文件input.txt，内容为aaaabbbccd

      我们已经得到了字符串中abcd的huffman编码了，它们分别是: '0' '11' '101' '100'，由于这里的huffman编码都是01组成的，所以我们很容易想到按位存储，这个时候这个字符串的huffman编码形式就是0000111111101101100,我们将它按位写进文件中，这个文件占用19个比特位，所以占用3个字节.   

而原文件中有10个字符他们都是char类型，所以占用10个字节. 这就是huffman压缩算法的基本思想.

      所以出现的越频繁次数越多的字符它的huffman编码越短，占用的空间越少. 出现较为少的字符他们的huffman的编码虽然长，但是出现的次数少.并且我们的huffman编码是按位存储的，所以这里的压缩效率就显现出来了. 

huffman压缩算法压缩率高的情况就是 出现特别多的重复字符，只有极少数的是别的字符(比如 abbbbbbbbbbbbbbbb). 

效率低的情况下就是每个字符出现的次数都差不多很平均.(比如abcdabcd）

现在项目的思路渐渐地清晰了起来了:

    1.统计:首先读取一个文件，统计出256个字符中各个字符出现的次数.

    2.建树:按照字符出现的次数，并以次数作为权值遍历哈夫曼编码树，然后产生各个字符的huffman编码.

    3.压缩:再次读取文件，按照该字符对应的编码写到新的编码文件当中.

    4.加工:将文件的长度，文件中各个字符以及他们的出现次数，写进编码文件中.

    5.解压:利用压缩文件和配置文件恢复出原文件.

    6.测试:观察解压出的文件和原文件是否相同，再通过Beyond Compare 4软件进行对比，验证程序的正确性.

首先我们先建堆

template<class T>
struct Less
{
	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>//编写与类型无关的代码
class Heap
{
public:
	Heap()
	{}

	Heap(T* a, size_t n)
	{
		_a.reserve(n);  //reserve()只开空间   resize()开空间并初始化
		for (size_t i = 0; i < n; 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()
	{
		swap(_a[0], _a[_a.size() - 1]);
		_a.pop_back();
		AdjustDown(0);
	}

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

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

	const T& Top()
	{
		return _a[0];
	}

	void Print()
	{
		for (size_t i = 0; i < _a.size(); i++)
		{
			cout << _a[i] << " ";
		}
	}

protected:
	void AdjustDown(size_t root)//向下调整算法
	{
		Compare com;
		size_t  parent = root;
		size_t  child = parent * 2 + 1;
		while (child < _a.size())
		{
			if (child + 1 < _a.size() && com(_a[child + 1], _a[child]))
			//if ((child + 1 < _a.size()) && (_a[child + 1] > _a[child]))
			{
				child++;   //只需得到大的（小的）孩子的下标即可
			}
			if (com(_a[child], _a[parent]))
			//if (_a[child] > _a[parent])
			{
				swap(_a[child], _a[parent]);
				parent = child;        //子问题
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

	void AdjustUp(size_t child)//向上调整算法
	{
		Compare com;
		size_t parent = (child - 1) / 2;
		while (child > 0)
		{
			if (com(_a[child], _a[parent]))
			//if (_a[child] > _a[parent])
			{
				swap(_a[child], _a[parent]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}
		}
	}

private:
	//T* _a;
	//size_t _size;
	//size_t _capacity;
	vector<T> _a;
};

构建哈夫曼树

//构造哈夫曼树结点的结构体
template<class W>
struct HuffmanTreeNode
{
	HuffmanTreeNode<W>* _left;
	HuffmanTreeNode<W>* _right;
	W _weight;  //权值

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

template<class W>
class HuffmanTree
{
	typedef HuffmanTreeNode<W> Node;
public:
	HuffmanTree()
		:_root(NULL)
	{}

	//W-> CharInfo
	HuffmanTree(W* w, size_t n,const W& invalid)
	{
		struct PNodeCompare
		{
			bool operator()(Node* l, Node* r)
			{
				return l->_weight < r->_weight;
			}
		};
		//构建Huffman树
		Heap<Node*,PNodeCompare> minheap;  //传结点的指针
		for (size_t i = 0;  i < n; i++)
		{
			if (w[i] != invalid)
			     minheap.Push(new Node(w[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;

			minheap.Push(parent);
		}

		_root = minheap.Top();		
	}

	~HuffmanTree()
	{
		Destory(_root);
		_root = NULL;
	}
	void Destory(Node* root)
	{
		if (root == NULL)
			return;
		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}

	Node* GetRoot()
	{
		return _root;
	}

private:
	HuffmanTree(const HuffmanTree<W>&);
	HuffmanTree<W>& operator=(const HuffmanTree<W>&);
protected:
	Node* _root;
};

压缩和解压缩

typedef long long LongType;
//要用到的自定义类型，存放所有字符，字符出现的次数，还有它的Huffman编码
struct CharInfo
{
    char _ch;  //字符
	LongType _count;  //出现次数
	string _code;   //Huffman  Code

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

	CharInfo operator+(const CharInfo& info)
	{
		CharInfo ret;
		ret._count = _count + info._count;
		return ret;
	}

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

class FileComparess
{
	typedef HuffmanTreeNode<CharInfo> Node; 

	struct TmpInfo
	{
		char _ch;
		LongType _count;
	};

public:
	FileComparess()   
	{
		for (size_t i = 0; i < 256; i++)
		{
			_infos[i]._ch = i;
			_infos[i]._count = 0;
		}
	}

	void GenerateHuffmanCode(Node* root, string code)
	{
		if (root == NULL)
			return;
		if (root->_left == NULL && root->_right == NULL)
		{
			_infos[(unsigned char)root->_weight._ch]._code = code;
			return;
		}
		GenerateHuffmanCode(root->_left, code + '0');
		GenerateHuffmanCode(root->_right, code + '1');
	}

	void Compress(const char* file)   //压缩文件
	{
		//1.统计字符出现的次数
		FILE* fout = fopen(file, "rb");    //二进制文件
		assert(fout);

	    char ch = fgetc(fout);
		while (!feof(fout))
		{
			//_infos[]是一个CharInfo类型的数组，一共有256个元素，每一个元素都维护一个字符
			_infos[(unsigned char)ch]._count++;
			ch = fgetc(fout);
		}

		//2.构建Huffman Tree 
		CharInfo invalid;
		invalid._count = 0;
		HuffmanTree<CharInfo> tree(_infos, 256, invalid);

		//生成Huffman编码
		string code;
		GenerateHuffmanCode(tree.GetRoot(), code);
		
		//开始压缩文件
		string compressfile = file;
		compressfile += ".huffman";
		FILE* fin = fopen(compressfile.c_str(), "wb");//c_str()的用法就是返回一个正规的C字符串指针，内容和string相等
		assert(fin);

		//写入字符出现的信息
		//fwrite(_infos, sizeof(CharInfo), 256, fin);
		for (size_t i = 0; i < 256;  i++)
		{
			if (_infos[i]._count > 0)
			{
				TmpInfo info;
				info._ch = _infos[i]._ch;
				info._count = _infos[i]._count;
				fwrite(&info, sizeof(TmpInfo), 1, fin);
			}
		}

		TmpInfo info;
		info._count = -1;
		fwrite(&info, sizeof(TmpInfo), 1, fin);

		//3.压缩  
		fseek(fout, 0, SEEK_SET);
		ch = fgetc(fout);
		char value = 0;
		size_t pos = 0;
		while (!feof(fout))
		{
			string& code = _infos[(unsigned char)ch]._code;
			for (size_t i = 0; i < code.size();  i++)
			{
				if (code[i] == '1')
					value |= (1 << pos);
				else if (code[i] == '0')
					value &= ~(1 << pos);
				else
					assert(false);

				++pos;
				if (pos == 8)//满8位就往里写
				{
					fputc(value, fin);
					value = 0;
					pos = 0;
				}
			}
			ch = fgetc(fout);
		}
		if (pos > 0)
		{
			fputc(value, fin);
		}
		fclose(fout);
		fclose(fin);
	}
	//解压缩
	void Uncompress(const char* file)
	{
		string uncompressfile = file;
		size_t pos = uncompressfile.rfind('.');
		assert(pos != string::npos); 
		uncompressfile.erase(pos);
	
		uncompressfile += ".unhuffman";
		FILE* fin = fopen(uncompressfile.c_str(), "wb");
		assert(fin);

		FILE* fout = fopen(file,"rb");
		assert(fout);

		//fread(_infos, sizeof(CharInfo), 256, fout);

		TmpInfo info;
		fread(&info, sizeof(TmpInfo), 1, fout);
		while (info._count != -1)
		{
			_infos[(unsigned char)info._ch]._ch = info._ch;
			_infos[(unsigned char)info._ch]._count = info._count;

			fread(&info, sizeof(TmpInfo), 1, fout);
		}

		//重建Huffman树
		CharInfo invalid;
		invalid._count = 0;
		HuffmanTree<CharInfo> tree(_infos, 256,invalid);

		Node* root = tree.GetRoot();
		Node* cur = root;
		LongType n = root->_weight._count;
		char ch = fgetc(fout); 
		while (!feof(fout))
		{
			for (size_t i = 0; i < 8; i++)
			{
				if ((ch & (1 << i)) == 0)
					cur = cur->_left;
				else
					cur = cur->_right;
				if (cur->_left == NULL && cur->_right == NULL)
				{
					fputc(cur->_weight._ch, fin);
					cur = root;

					if (--n == 0)
					{
						break;
					}
				} 
			}
			ch = fgetc(fout);
		}
		fclose(fin);
		fclose(fout);
	}
protected:
	CharInfo _infos[256];
};

(1)刚开始写的时候测试发现如果待压缩文件中出现了中文，程序就会崩溃，将错误定位到构建哈夫曼编码的函数处，最后发现是数组越界的错误，因为如果只是字符，它的范围是-128~127，程序中使用char类型为数组下标(0~127)，所以字符没有问题. 但是汉字的编码是两个字节，所以可能会出现越界，解决方法就是将char类型强转unsigned char，可表示范围为0~255.

(2)解压缩文件生成后大部分的内容丢失了，这个是因为程序读到了EOF（文件结束标志），EOF通常用来判断文本文件的结尾，因为EOF的值为-1，ASCII都是字符型，不可能出现-1的情况。而在二进制文件中，信息以数值存放，使用EOF就可能会异常。

解决方案: 使用feof()函数，feof函数既可用以判断二进制文件又可用以判断文本文件。

使用方法是 feof(fp)，fp为指向需要判断的文件的指针。如果不到文件结尾，返回0值；如果是文件结尾，返回非0.