Huffman Tree应用之文件压缩

Huffman Tree:带权路径长度（从根节点出发到叶子节点）达到最小，称这样的树为哈夫曼树或者最优二叉树。哈夫曼树是带权路径长度最小的树，权值较大的离根近，权值较小的离根远。

那么这样一颗树是怎么构建出来的？

假设有如下序列元素{1，2，3，4，5，6，7，8，9}，先从其中选出两个最小的值作为它的权值（即1，2）作为左右孩子节点，然后把左右孩子之和作为父节点的权值，同时把父节点放到序列中去，如下图所示：

 

好了，哈夫曼树就这样被构建好了，我们可以发现，序列中的每个元素都在叶子节点上，我们通过每次取出序列剩余的元素中最小的两个值来不断的构建这棵树，并且我们会发现根节点的值等于所有叶子节点之和。其实这种思想就是贪心算法，贪心算法是在每次求解问题的时候，总是做出当前看起来最好的选择，也就是说贪心算法是某种意义上的局部最优解，但是却不一定是整体最优解。

那么哈夫曼树是能够进行压缩的原理是什么呢？

首先我们来捋一下哈夫曼进行压缩的思路：

1.统计每个字符出现的次数

2.构造哈夫曼树（如下图）

3.根据哈夫曼树生成哈夫曼编码

 

4.进行压缩，这个时候我们已经得到哈夫曼编码了，那么这些编码我们应该怎么去存储它们呢？不难想到，这些编码都是有01序列组成的，用位来存储最合适不过了，我们以八位为一个字节进行存储，字符为key,key出现了多少次我们就把对应的编码写多少次，如：a对应的编码为0，出现了四次，那么我们就写4个0；b的编码为10，出现了三次，我们就写为101010;一次类推最后我们得到的完整的哈夫曼编码就是：0000 1010 1011 1111 110，可以看出原先的10个字符需要占10个字节（都是char类型）才能把它存储起来，而现在我们只需要3个字节就可以存储，节约了7个字节的空间，此时好像豁然开朗，原来哈夫曼压缩是靠这样的原理来进行压缩的，我们可以把它能够压缩文件的原理总结一下：

      出现次数多的字符哈夫曼编码越短 ，占用的空间越少，出现次数少的虽然哈夫曼编码越长，但是出现的次数少，相对来说还是可以节约空间的·；那在这里我们难免会思考一个这样的问题，如果哈夫曼编码的长度大于8，那岂不是还出现了反压缩的效果？很好，说明我们考虑问题很全面嘛，这么说吧？编码长度大于8，说明出现的次数比较少， 我们把频繁出现的字符（编码短）放在了树的最上面，它们节省的空间总的来说还是大于编码长的字符浪费的空间，所以从宏观上来看，也是可以起到一定的压缩效果的。

5.解压缩

在这个过程中，我们需要重建哈夫曼树（此处留下坑，填坑理由在后面），因为压缩和解压缩是两个相互独立的过程，刚才压缩构成的哈夫曼树现在已经销毁了，试想一下，我们给压缩文件里面存放了哈夫曼编码，我们就可以根据哈夫曼编码来依次去还原每个字符，我们每次都从根节点开始走，根据哈夫曼编码来决定如何去走，每走到一个叶子节点我们需要还原这个字符，然后再接着从根节点开始遍历，直到哈夫曼编码被遍历完成，这棵树就被还原成功。

基于上面的例子，解压缩的过程是这样的：

那么基于这样的思路，我们的哈夫曼压缩有如下两个性能上的特点：

1.  出现次数多的和出现次数小的差距特别大的时候压缩率最好，即重复率越高压缩率越好（举个例子：假设一个文件中有10个a,则生成的哈夫曼编码为:0000  0000 00,原本需要10个字节空间的内容现在只需要两个字节即可进行存储，节约了8个字节）

2. 出现次数多的和出现次数小的差距特别小的时候压缩效率最差

写到这里，我们可以开始写代码了，写代码之前，我们还有一个问题，就是在构建这棵树的时候，怎样每次选出最小的两个值，很容易啊，我们每次选取的时候只需要进行排序就好了呀？真的是这样的吗？排序算法时间复杂度最低也有N*logN了吧，假设我们偷个懒，我们直接用库里面的sort函数进行排序，sort排序底层是快排，时间复杂度为N*logN，每次选取进行排序是不是麻烦了点，接着可以继续想到，既然每次选取的都是最小的两个元素，很自然就想到了小堆，我们只要每次取堆顶元素进行pop，然后再把父节点的值插入到堆中即可，堆的插入和删除的时间复杂度都是N*logN,好像是差不多的，嗯，那在这里我们就用堆来完成构建哈夫曼树吧！鉴于我们强大的STL适配器中有一个叫做优先级队列（priority queue）的东西，但是它默认情况下是一个大堆，所以我们想要用它还需要提供一个仿函数；代码如***释已经写的很详细了呦

#include<queue>
#include<vector>

template<class W>
struct HuffmanTreeNode//每个节点需要存储的信息
{
	W _w;     //权值
	HuffmanTreeNode<W>* _left;
	HuffmanTreeNode<W>* _right;
	HuffmanTreeNode<W>* _parent;
	HuffmanTreeNode(const W& w)
		:_w(w)
		,_left(NULL)
		,_right(NULL)
		,_parent(NULL)
	{}

};
template<class W>
class HuffmanTree{
	typedef HuffmanTreeNode<W> Node;
	struct PtrNodeCompare
	{
		bool operator()(Node* n1,Node* n2)//仿函数
		{
			return n1->_w>n2->_w;//需要一个小堆
		}
	};
public:
	HuffmanTree()//构造函数
		:_root(NULL)
	{}

	HuffmanTree(W* a,size_t n,const W& invalid)
	{
		priority_queue<Node*,vector<Node*>,PtrNodeCompare> minheap;
		for(size_t i=0; i<n; ++i)//把256个字符中所有出现的文件里的字符都push进堆里面
		{
			if(a[i]!=invalid)//这里的invalid是指这个字符没有出现在要进行压缩的文件里
			{
				minheap.push(new Node(a[i]));//出现了就push进堆里面
			}
		}
			while(minheap.size()>1)
			{
				//取出出现次数最少的两个字符
				Node* left=minheap.top();
				minheap.pop();
				Node* right=minheap.top();
				minheap.pop();
				Node* parent=new Node(left->_w+right->_w);//父节点的权值=左右孩子权值之和
				//三叉链，构造树
				parent->_left=left;
				parent->_right=right;
				minheap.push(parent);//将父节点仍进堆里
			}
		_root=minheap.top();//根节点的值就是堆的顶点
}
	Node* GetRoot()//获取根节点，_root为私有成员，我们只能通过成员函数来得到它
	{
		return _root;
	}
	~HuffmanTree()//析构函数，进行清理
	{
		Destroy(_root);
		_root=NULL;
	}
	void Destroy(Node* root)//递归销毁整棵树
	{
		if(root==NULL)
		{
			return;
		}
		Destroy(root->_left);
		Destroy(root->_right);
		delete root;
	}
private://禁止进行拷贝构造和赋值运算符的重载
	HuffmanTree(const HuffmanTree<W>* h);
	HuffmanTree<W>& operator=(const HuffmanTree<W>& h);
protected:
	Node* _root;//根节点
};

在这里我们使用了模板，使用模板的好处是在构建哈夫曼树的时候可以使用我们自定义的类型进行构建。

现在我们的树生成了，接下来该构造哈夫曼编码了

typedef long long LongType;
struct CharInfo
{
	char _ch;//节点存的字符
	LongType _count;//字符出现的次数
	string _code;//哈夫曼编码
	CharInfo operator+(const CharInfo& info)
	{
		CharInfo ret;
		ret._count=_count+info._count;
		return ret;
	}
   bool operator>(const CharInfo& info)
   {
	   return _count>info._count;
   }
   bool operator!=(const CharInfo& info)
   {
	   return _count!=info._count;
   }
};
class   FileCompress{
	typedef HuffmanTreeNode<CharInfo> Node;
public:	
void GernerateHuffmanCode(Node* root)
	{
		if(root->_left==NULL&&root->_right==NULL)//叶子节点，保存哈夫曼编码
		{
			_hashInfos[(unsigned char)root->_w._ch]._code=root->_w._code;
		}
		if(root->_left!=NULL)//左边为0
		{
			root->_left->_w._code=root->_w._code+'0';
			GernerateHuffmanCode(root->_left);
		}
		if(root->_right!=NULL)//右边为1
		{
			root->_right->_w._code=root->_w._code+'1';
			GernerateHuffmanCode(root->_right);
		}
	}
protected:
	CharInfo _hashInfos[256];
};

哈夫曼编码生成好了，该进行压缩了，压缩的时候我们需要注意些什么呢？比如除了把哈夫曼编码写进压缩文件里之外，我们还需要存什么东西吗？出现的字符以及出现的次数要不要存？暂时好像没有这个必要，长远一点，在进行解压缩的时候，我们刚才提到了一个坑，是的，没错，在解压缩的过程中为了正确的还原出每一个字符，我提到了需要重新构造哈夫曼树，回忆一下 在进行压缩的时建树需要把文件中出现的字符以及它们出现的次数保存在保存在哈夫曼节点中，才能进行构建。所以在这里，我们需要把出现的字符以及它们出现的次数保存在压缩文件里，为解压缩做准备，以便重建哈夫曼树时可以成功并且正确的构建出原有的哈夫曼树来。

压缩的全过程如下：

class FileCompress
{
	typedef HuffmanTreeNode<CharInfo> Node;
	//为了解压缩时使用，保存给压缩文件里要写的字符以及每个字符出现的次数
	struct temp
		{
		    char _ch;
	        LongType _count;
		};
public:
	
	FileCompress()
	{
		for(size_t i=0; i<256; ++i)
		{
			_hashInfos[i]._ch=i;
			_hashInfos[i]._count=0;
		}
	}
	void ComPress(const char* file)
   {
		assert(file);
		FILE* fout=fopen(file,"rb");//源文件
		assert(fout);
	   char ch=fgetc(fout);
	   //统计每个字符出现的次数用来构造哈夫曼树
	   while(!feof(fout))
	   {
		   _hashInfos[(unsigned char)ch]._count++;
		   ch=fgetc(fout);
	   }
		CharInfo invalid;
		invalid._count=0;//没出现的字符
		//构建哈夫曼树
		HuffmanTree<CharInfo> tree(_hashInfos,256,invalid);
		//生成哈夫曼编码
		GernerateHuffmanCode(tree.GetRoot());
	
		//压缩
		string compressfile=file;
       //和源文件进行区分，便于我们进行后续测试
		compressfile+=".huffman";
		FILE* fin=fopen(compressfile.c_str(),"wb");//压缩文件
	    temp info;
		//将每个出现的字符以及它们各自出现的次数写进压缩文件里
		 for(size_t i=0; i<256; ++i)
		{
			if(_hashInfos[i]._count>0)
			{
				info._ch=_hashInfos[i]._ch;
				info._count=_hashInfos[i]._count;
			    fwrite(&info,sizeof(temp),1,fin);

             }
		}
		//用来标识出现的字符以及出现次数的结尾
		info._count=0;
		fwrite(&info,sizeof(temp),1,fin);

        char value=0;
		size_t pos=0;
		//刚才我们读完了fout,现在需要从头开始，SEEL_SET（文件开始）SEEK_CUR（文件当前位置）
		//SEEK_END（文件结尾）
		fseek(fout,0,SEEK_SET);
	    ch=fgetc(fout);
		//将哈夫曼编码每8位做一个字节写进压缩文件里
		while(!feof(fout))
		{
			string code=_hashInfos[(unsigned char)ch]._code;
			for(size_t i=0; i<code.size(); ++i)
			{
				if(code[i]=='0')
				{
					value&=~(1<<pos);
				}
				else if(code[i]=='1')
				{
					value|=(1<<pos);
				}
				else
				{
					throw exception("invalid huffman  code");
				}
				++pos;
				if(pos==8)//满一个字节写进压缩文件
				{
					fputc(value,fin);
					pos=0;
					value=0;
				}
			}
			ch=fgetc(fout);
		}
		if(pos>0)//不满一个字节的编码写进压缩文件里
		{
			fputc(value,fin);
		}
		fclose(fin);//养成好习惯，用完就关闭文件
		fclose(fout);
		
	}
protected:
	CharInfo _hashInfos[256];
};

最后一步就是我们的解压缩了，代码如下：

void Uncompress(const char* file)
	{
		string unfile=file;
		//rfind表示从后面开始找
		size_t pos=unfile.rfind('.');
		//如果没有找到返回string::npos,代表字符串的结束，整型的最大值，-1
		if(pos!=string::npos)
		{
			unfile.erase(pos);
		}
		//加上后缀，为了跟源文件进行区分，对比是否正确
		unfile+=".unhuffman";
		//打开这个文件进行写
		FILE* fin=fopen(unfile.c_str(),"wb");
        assert(fin);
		//打开压缩文件进行读
		FILE* fout=fopen(file,"rb");
		assert(fout);
	   //将出现的字符以及它们出现的次数记录到hashInfos里面，用来重构哈夫曼树
		while(1)
		{
			 temp info;
		     fread(&info,sizeof(temp),1,fout);
			 if(info._count>0)
			 {
			   _hashInfos[(unsigned char)info._ch]._ch=info._ch;
			    _hashInfos[(unsigned char)info._ch]._count=info._count;
			 }
			 else
			 {
				 break;
			 }
        }
		CharInfo invalid;
		invalid._count=0;
		//重建哈夫曼树
		HuffmanTree<CharInfo> tree(_hashInfos,256,invalid);
		Node* root=tree.GetRoot();
		LongType count=root->_w._count;//需要还原的总字符数

		Node* cur=root;
	    char value=fgetc(fout);
		//遍历哈夫曼树，走到叶子节点将字符写到解压缩文件里面
		while(count)
		{

			for(size_t i=0; i<8; ++i)
			{
				if(value&(1<<i))//右1
				{
					cur=cur->_right;
				}
				else//左0
				{
					cur=cur->_left;
				}
				if(cur->_left==NULL&&cur->_right==NULL)//走到叶子节点
				{
					fputc(cur->_w._ch,fin);
					//每次要从头开始遍历走到叶子节点，每个字符的哈夫曼编码都是从根节点走到叶子节点生成的
					cur=root;
					--count;
					if(count ==0)//还原完成
					{
						break;
					}

				}
			}
		     value=fgetc(fout);

		}
		fclose(fin);//好习惯时时刻刻注意
		fclose(fout);
	}

在上述所有代码中，有几个需要注意的点(这也是我在多次进行调试与测试之后差点坑死我的点）：

    1.我没有用EOF来判断文件结束，为什么？EOF这个宏其实是个大坑，它实际上就是一个-1，假如我们的文件中出现了-1这个            字符呢？岂不是被误判为文件结束了，这显然不符合我们的预期。

    2.在_hashInfos这个数组中有256个元素，有符号char的取值范围为[-128 ,+127],我们能让元素下标出现负值吗？所以要在每个用到这个数组下标的地方强转为unsigned char.

大功告成，这个简单的小项目就这样完成了，我们再来整理一下文件压缩的基本过程：

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

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

3.压缩:再次读取文件，按照哈夫曼编码写到压缩文件当中.

4.加工:将文件的长度，文件中各个字符以及他们的出现次数，写进编码文件中（给解压缩做准备）.

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

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

最后呢？我对这个项目进行了一下简单的测试：（我用的是vs,测性能的话最好在Release下测快一点）

 1.对于一个1.2M的文件，压缩到了0.8兆，节省了大约1/3的空间，用时0.318秒；

解压缩文件为：

这里可以对比一下，源文件和解压缩文件的大小一样，内容我也通过Beyond compare验证过了，没有问题

2.对于一个将近2.3M的图片，压缩到了1.2几兆，耗时0,517S