利用huffman算法对文件进行压缩

Huffman算法简介

Huffman算法是一种基于统计的压缩方法。它的本质就是对文本文件中的字符进行重新编码,对于使用频率越高的字符,其编码也越短。但是任何2个字符的编码,是不能出现向前包含的。也就是说字符A的编码的前段,不可能为字符B的编码。经过编码后的文本文件,主要包含2个部分:Huffman码表部分和压缩内容部分。解压缩的时候,先把Huffman码表取出来,然后对压缩内容部分各个字符进行逐一解码,形成源文件。

由此可见,使用Huffman算法的关键是形成Huffman码表。怎样才能生成一个“使用频率越高的字符,其编码也越短”的码表呢?这里就要用到Huffman树的数据结构。当把一棵Huffman树生成后,码表也就生成了。以下举例说明,假定我们的原始文本为”abcbbcccc”

Huffman树生成步骤:

1.扫描源文件,对字符频率进行统计。

对于我们的样例,统计结果是:a:1  b:3 c:5 (按频率升序排列)

huf1

2.从上述队列中取出频率最低的2个节点,合并成一个频率为2节点频率之和的树枝节点X,加入到原队列中,加入后,继续保持队列按频率升序排列.

huf2

3.重复步骤2,直到队列中只有一个节点。

huf3

4.这样,我们就形成了一棵Huffman树。叶子节点为字符,从树根节点到叶子节点的路径即为该字符的Huffman编码。从一个节点导航到其左孩子,该段路径为0,导航到右孩子,该段路径为1.所以,a字符的编码就是00,b字符的编码为01,c字符的编码为1,符合”使用频率越高的字符,编码越短”的要求。理论论证过程见<算法导论>P233

5.Huffman码表生成后,原文本”abcbbcccc”就变成了0001101011111的位串,按每个字符占用2个byte计算,大小由原来的18个字节(9*2),共144个bit,变成了13个bit,2个字节。达到了压缩的目的。

解压缩过程:

解压缩也分成2部分进行,首先是根据压缩文件中的Huffman码表,在内存中生成一棵Huffman树,然后,根据Huffman树,对压缩内容进行解压缩。比如如果压缩内容为位串0001101011111,那么从树根节点起,因为第一个bit为0,先转向左子树,第二个bit为0,再转向左子树,到达叶子a,所以解码出来的第一个字符就是a,每次解压一个字符,都从根节点起,根据bit流,向左或向右转,直到到达叶子节点,也就是解压出来的字符。一直重复此过程,直到所有的字符都被解压缩。

压缩文件格式

使用Huffman压缩算法对文本文件压缩后,就形成了一个压缩文件,该压缩文件包含2部分,一部分为Huffman码表,也就是Huffman树,第二部分为根据码表生成的内容位串。如何设计Huffman树的存储格式呢?本文采用从上到下,从左到右分层遍历节点,顺序存储的方式。如下图:

huf4

也就是说,对于前述的Huffman树,其持久化形式为:0xfffe 0xfffe 0x0063  0x0061  0x0062,其中0xfffe代表树枝节点,而0x0061,0x0062,0x0063分别为a,b,c的Unicode码。因为所有的树枝节点的值都是0xfffe,所有树枝节点都有2个孩子,节点排列方式是按从上到下,从左到右分层排列,所以能根据此持久化字节数组,把Huffman树在内存中重新生成。

一、利用huffman树对文件进行压缩主要分为以下两部分:

压缩:

1、统计字符出现的次数

因为文件的底层都是有256个字符存储的,所以我们使用一个256的数组来统计字符出现的次数。可以使用结构体,将次数,字符,huffman编码对应 起来。要注意,不管是文件、图片、音频、视频他们的底层都是以字符形式存储的。我们读的时候不管是以文本形式还是以二进制形式都是按字符读取的。

2、构建huffman树

采用huffman算法,将一组集合中权值最小的两个树拿出来构建成一棵树,将他们的权值之和作为父节点插入到这个集合中,不断重复这个过程,直到集合 中只有一颗树,这棵树就是huffman树,由于每次都要寻找最小的两个数,我们可以使用最小堆来寻找最小的两个数。在这里,我们可以用字符出现的次数作 为权值。

3、得到huffman编码

从根节点出发,向左走位0,向右走为1,找到一个叶子结点,就将他对应字符的huffman编码存到数组里面。

4、将huffman编码写入文件

使用哈希表,可以在O(1)时间内找到字符所对应的编码,将每8位编码构成一个字符写入文件中。如果最后的几位编码不够8位,那么我们就要在后面几位中补0.

5、编写配置文件

由于在解压时往往是没有源文件的,而我们要解压的话必须要知道这棵huffman树,所以在我们压缩的时候编写一个配置文件来存储huffman树的信息。在配置文件里面将:字符+出现的次数存在一行。在这里要使用itoa这个函数 将次数转换成一个字符串存储。

解压缩:

1、读取配置文件

由于解压和压缩往往不是一起的,所以在解压之前我们要先还原huffman这棵树,读取配置文件时我们是一行一行进行存储的,所以读的时候我么最好一行 一行的读。但是这里要注意两个问题。第一:因为string底层是char*,而每一行的第一个字符是0—255,所以这一块我们要进行处理,可以单独读 取。第二:将字符串转换为数字,使用atoi函数。

2、构建huffman树

构建huffman树和压缩时是一样的。

3、解压缩

首先在压缩文件里面读取一个字符,然后解析这个字符的每一位,采用贪心法,只要遇到一个叶子结点,就代表我们还原了一个字符,这时候我们就要将这个字符 写到解压缩文件里面。但是在这里要注意,有可能最后的几位编码是我们补上去的,所以在这里我们要以源文件中字符出现的次数来控制解压缩,根据 huffman的性质可知,根节点的权重就是字符出现的次数。

二、在项目中遇到的问题

1、解压缩时解压不完全

由于使用文本形式读取压缩文件,有可能提前遇到文件结束标志,所以要改为二进制形式读写。二进制形式是读取二进制编码。

如果以文本形式读取的话,回车会被当成一个字符’n’,而二进制形式则会认为它是两个字符即’r’回车、’n’换行;如果在文本形式中遇到0x1B的话,文本形式会认为这是文本结束符,而二进制模型则不会对它产生处理。

2、得到huffman编码

在压缩时我们要求解huffman编码,在这里可以使用stl中的string和reverse求解。也可以使用后序递归直接求解。

3、二次压缩效率很低

因为压缩一次之后,这时因为配置文件中字符出现的次数相差都不是很大,体现不出来huffman的特性。所以这时候再压缩的话效率会非常低下。

4、压缩汉字时出现问题

因为汉字是由多个字符表示,这些字符的范围是0—255,所以在结构体中要用unsigned char表示。

三、项目改进

1、解压缩的时候有可能要解压缩文件的不是用huffman进行压缩的文件。所以再解压文件之前先判断是不是用huffman进行压缩的。

2、不使用配置文件时如何解压

可以将huffman树的信息写入到压缩文件中。

//heap

#pragma once
#include<cassert>
#include<vector>
using namespace std;

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

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



//通过仿函数,可以建最小堆也可以建最大堆
template<typename T, class Compare = Less<T>>
class Heap
{
public:
	Heap()
	{}
	Heap(T *a, int size)
	{
		_a.reserve(size);
		for (int i = 0; i < size; i++)
		{
			_a.push_back(a[i]);
		}

		//建堆
		for (int i = (size - 2) / 2; i >= 0; --i)     //从最后一个非叶结点开始调整
		{
			AdjustDown(i, size);
		}
	}

	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();
		if (_a.size()>1)         //如果堆中的元素大于一个,再进行调整
		{
			AdjustDown(0, _a.size());
		}
	}

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

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

	const T& Top()
	{
		assert(!_a.empty());
		return _a[0];
	}
protected:
	void AdjustDown(int root, int size)      //向下调整算法
	{
		assert(!_a.empty());
		int parent = root;
		int child = parent * 2 + 1;
		while (child<size)
		{

			if ((child + 1) < size
				&&Compare()(_a[child + 1], _a[child]))  //找左右孩子中最大的下标
				child++;
			if (Compare()(_a[child], _a[parent]))
			{
				swap(_a[parent], _a[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
			{
				break;
			}
		}
	}

	void AdjustUp(int child)    //向上调整算法
	{
		assert(!_a.empty());
		while (child>0)
		{
			int parent = (child - 1) / 2;
			if (Compare()(_a[child], _a[parent]))
			{
				swap(_a[parent], _a[child]);
				child = parent;
			}
			else
			{
				break;
			}
		}
	}
private:
	vector<T> _a;
};

//huffman

#pragma once
#include"heap.h"

template<typename T>
struct HuffmanNode
{
	T _data;
	HuffmanNode<T>* _left;
	HuffmanNode<T>* _right;
	HuffmanNode<T>* _parent;
	HuffmanNode(const T& data = T())
		:_data(data)
		, _left(NULL)
		, _right(NULL)
		, _parent(NULL)
	{}
};


template<typename T>
class HuffmanTree
{
	typedef HuffmanNode<T> Node;
public:
	HuffmanTree()
		:_root(NULL)
	{}

	HuffmanTree(T  *a, size_t size,const T& invalid=T())
	{
		//最小堆的比较方式
		struct NodeLess
		{
			bool operator()(Node* l, Node* r)
			{
				assert(l);
				assert(r);
				return l->_data < r->_data;
			}
		};

		//将这组数据建成一个最小堆,堆中元素的类型是Node*,这是为了保存后面结点的父节点
		Heap<Node*, NodeLess>  minHeap;
		for (size_t i = 0; i <size; i++)
		{
			if (a[i]._count!=invalid._count)           //如果字符出现的次数不为0,就加入堆中
			{
				Node* _node = new Node(a[i]);
				minHeap.Push(_node);
			}
		}

		//用huffman算法,从堆里面取出最小的两个结点并删除,将这两个结点构成一棵树在插入堆中
		Node* frist = NULL;
		Node* second = NULL;
		Node* parent = NULL;
		while (minHeap.Size()>1)
		{
			frist = minHeap.Top();
			minHeap.Pop();
			second = minHeap.Top();
			minHeap.Pop();

			parent = new Node(frist->_data + second->_data);
			parent->_left = frist;
			parent->_right = second;

			frist->_parent = parent;
			second->_parent = parent;

			minHeap.Push(parent);
		}

		//堆里面的最后一个就是Huffman树的根节点
		_root = minHeap.Top();
	}

	Node* GetRoot()
	{
		return _root;
	}


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

private:
	Node* _root;
};

//fileCompress

#pragma once
#include<string>
#include<cstdio>
#include<cassert>
#include<cstdlib>
#include<algorithm>
using namespace std;
#include"HuffmanTree.h"

typedef long long LongType;

struct CharInfo
{
	unsigned char _data;
	LongType _count;                //保存字符出现的次数
	string _Code;                   //保存Huffman编码
	CharInfo(LongType count=0)
		:_count(count)
	{}

	CharInfo operator+(CharInfo& ch)
	{
		return CharInfo(_count+ch._count);
	}

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


class HuffFileCompress
{
public:
	HuffFileCompress()
	{
		for (int i = 0; i < 256; i++)   //将Infos中每个data初始化相应的字符
		{
			_Infos[i]._data = i;
		}
	}

	HuffFileCompress(const char * filename)
	{
		assert(filename != NULL);
		for (int i = 0; i < 256; i++)   //将Infos中每个data初始化相应的字符
		{
			_Infos[i]._data = i;
		}

		FILE *fInput = fopen(filename, "rb");   //打开文件
		assert(fInput);
		int ch = 0;

		while ((ch = fgetc(fInput)) != EOF)    //读文件,统计字符出现次数
		{
			_Infos[ch]._count++;
		}

		//构建huffman树
		CharInfo invalid;
		HuffmanTree<CharInfo> ht(_Infos, 256, invalid);

		//得到huffman编码
		string str;
		GetHufCode(ht.GetRoot(), str);
		fclose(fInput);
	}


	//文件压缩
	const string CompressFile(const string filename)
	{
		assert(!filename.empty());
		//得到压缩文件的文件名
		string CompressFileName = filename;
		CompressFileName += ".huf";

		FILE *fInput = fopen(filename.c_str(),"rb");     //打开原文件
		assert(fInput);

		FILE *fOut = fopen(CompressFileName.c_str(),"wb");   //打开压缩文件
		if (fOut == NULL)
		{
			fclose(fOut);
			exit(EXIT_FAILURE);
		}

		//编写配置文件,保存字符以及字符出现的次数,用于解压时重建huffmanTree
		string configFileName = filename;          //配置文件名
		configFileName += ".config";
		FILE *configOut = fopen(configFileName.c_str(),"wb");   //打开配置文件
		assert(configOut);
		string line;
		for (int i = 0; i < 256; i++)
		{
			if (_Infos[i]._count!=0)         //将字符以及出现的次数存在一行
			{
				int c=_Infos[i]._data;
				fputc(c,configOut);
				line += ",";
				char buffer[25] = { 0 };      //将次数转换成字符串存储
				line+=_itoa((int)_Infos[i]._count, buffer, 10);
				line += 'n';
				fputs(line.c_str(),configOut);
				line.clear();
			}
		}
		fclose(configOut);                  //关闭配置文件

		int c=0;                //用来保存huffman编码所构成的字符
		int pos =7;             //判断处理的位数,如果到8则进行写入
		int ch = fgetc(fInput);
		while (ch!=EOF)
		{
			string &code=_Infos[ch]._Code;
			for (size_t i = 0; i < code.size(); i++)     //处理ch这个字符的编码
			{
				c |= ((code[i]-'0') << pos);             //从高位开始相或
				pos--;
				if (pos<0)
				{
					fputc(c,fOut);
					pos = 7;
					c = 0;
				}
			}
			ch = fgetc(fInput);
		}

		if (pos<7)   //处理最后一个字符编码不是8位的情况
		{
			fputc(c, fOut);
		} 
		fclose(fOut);
		fclose(fInput);

		return CompressFileName;
	}


	//解压缩
	const string UnCompressFile(string filename)
	{
		assert(!filename.empty());
		//得到解压缩之后的文件的名字
		string name;
	    name= filename;
		int i = 0;
		string posfix;
		for (i =(int)filename.size()-1; i>=0; --i)       //找到后缀出现的位置
		{
			posfix.push_back(filename[i]);
			if (filename[i] == '.')
				break;
		}
		reverse(posfix.begin(),posfix.end());       //让posfix保存要解压文件的后缀
		if (posfix != ".huf")                 //如果要解压的文件不是huffman压缩的,则不能解压
		{
			return NULL;
		}


		//去掉后缀
		name.resize(i);

		string UnCompressFileName = name;      //得到压缩文件名 
		UnCompressFileName += ".uhuf";

		string configName = name;
		configName+=".config";   //得到配置文件名

		//打开压缩文件
		FILE *fInput = fopen(filename.c_str(),"rb");
		FILE *fInput2 =fInput;
		assert(fInput);

		//打开解压缩文件
		FILE *fOut = fopen(UnCompressFileName.c_str(),"wb");
		if (fOut == NULL)
		{
			fclose(fInput);
			exit(EXIT_FAILURE);
		}

		int ch = 0;

		//读取配置文件
		FILE *configInput = fopen(configName.c_str(),"rb");       //打开配置文件名
		string line;
		int c = 0;
		while ((c = fgetc(configInput))!=EOF)          //读取一行
		{
			GetLine(configInput, line);                  
			_Infos[c]._count = atoi((&line[1]));       //获得字符出现的次数
			line.clear();
		}
		fclose(configInput);    //关闭配置文件

		//构建huffman树
		CharInfo invalid;
		HuffmanTree<CharInfo> ht(_Infos, 256, invalid);
		LongType count = ht.GetRoot()->_data._count;      //获取字符的总个数

		int pos=7;
		c = 1;
		HuffmanNode<CharInfo> *root= ht.GetRoot();           //得到huffman树的根节点
		HuffmanNode<CharInfo> *cur = root;      
		while (count > 0)                         //以字符的总个数作为结束标志
		{
			ch = fgetc(fInput);
			//处理ch的二进制
			while (pos >= 0 && count > 0)
			{
				//寻找叶子结点(编码所对应的字符)
				if (ch&(c << pos))
				{
					cur = cur->_right;
				}
				else
				{
					cur = cur->_left;
				}
				if (cur->_left == NULL&&cur->_right == NULL)    //找到huffman所对应的字符
				{
					//写文件
					//if (cur->_data._data == 'n')
					//	fputc(13, fOut);
					fputc(cur->_data._data, fOut);
					cur = root;
					count--;
				}
				pos--;
			}
			pos = 7;
		}
		fclose(fInput);
		fclose(fOut);
	    return UnCompressFileName;
	}

protected:
	//得到huffman编码
	void GetHufCode(HuffmanNode<CharInfo>* root, string str)
	{
		if (root == NULL)
			return;
		if (root->_left == NULL&&root->_right == NULL)
		{
			_Infos[root->_data._data]._Code = str;  //将huffman编码保存在infos里面
			return;
		}
		GetHufCode(root->_left, str + '0');    //向左子树走压0	
		GetHufCode(root->_right, str + '1');   //向右子树走压1		
	}

	bool GetLine(FILE*& Input,string &line)        //读取一行字符
	{
		assert(Input);
		int ch = 0;
		ch = fgetc(Input);
		if (ch == EOF)
			return false;
		while (ch != EOF&&ch != 'n')
		{
			line += ch;
			ch = fgetc(Input);
		}
		return true;
	}
private:
	CharInfo _Infos[256];
};
加载余下内容▼

相关文章:

;