huffmantree.h

在win32下的文本huffman压缩以及文本的解压。

#ifndef HUFFMANTREE_H
#define HUFFMANTREE_H
#define FILE_BLOCK 40960
//文件块缓存大小
#include<stack>
#include<string>
#include<stdio.h>  //用C中的文件流来打开文件
#include<time.h>
clock_t time_start,time_finish;  //用于计算压缩和解压的时间

template<class Type>class ExtBinTree;
template<class Type>class Compress;

class Pack  //字符权值类
{
public:
	char ch;  //字符值
	unsigned long int key;  //字符的频数
	void setDate(char c=0)
	{
		ch=c;
	}
};

template<class Type>
class ExtBinTree  //带权值二叉树
{
	template<class Type>
	friend class Compress;
public:
	ExtBinTree(ExtBinTree<Type> *bt1,ExtBinTree<Type> *bt2);  //用两颗带权值二叉树作为左右子树构建二叉树
	ExtBinTree()
	{
		date.setDate();
		date.key=0;
		lChild=rChild=NULL;
	}
	int getKey(){return date.key;}  //获得二叉树根的权值
private:
	ExtBinTree<Type> *lChild,*rChild;  //左子女,右子女
	Type date;  
};
template<class Type>
ExtBinTree<Type>::ExtBinTree(ExtBinTree<Type> *bt1, ExtBinTree<Type> *bt2)
{
	date.setDate();
	date.key=bt1->getKey()+bt2->getKey();  //将两颗子树的权值相加赋给根结点
	lChild=bt1;  
	rChild=bt2;
}
template<class Type>  
class Compress  //霍夫曼编码压缩执行类
{
public:
	static void ToDo(char *str1,char *str2=NULL);  //压缩函数,str1为被压缩文件,str2为输出文件
	static bool UnDo(char *str1,char *str2=NULL);  //解压函数,str1为被解压文件,str2为输出文件
	static bool Do(char *func,char *file1=NULL,char *file2=NULL);  //通过获得参数决定其操作
	Compress(){};
	~Compress(){};
private:
	static bool getFileFreq(char *);  //读取文件中的字符频数
	static bool getInputFreq(char *);  //读取键盘输入的字符频数
	static ExtBinTree<Type>* BuildHufTree(Type *fr,int n);  //构建Huffman树
	static bool getCode(ExtBinTree<Type>*);  //通过Huffman树获得Huffman编码
	static bool CompresstoFile(char *str1,char *str2);  //压缩到文件
	static inline void SetBit_One(char &c,int n);  //改变字符第n位为1
	static bool GetBit(char &c,int n);  //获得字符第n位的数值,1则返回true,0则返回false
	static void showRate(int k);  //进度条显示函数

	static unsigned long int freq[256];  //文件中各字符的频率
	static unsigned long int file_size,file_size_after;  //文件大小以及压缩后文件大小
	static string HuffCode[256];  //储存霍夫曼编码
	static bool isShowed;  //用于标示进度条是否在前面显示
	
};
template<class Type>
unsigned long int Compress<Type>::freq[256]={0};  //Compress类中各静态变量初始化
template<class Type>
unsigned long int Compress<Type>::file_size=0;
template<class Type>
unsigned long int Compress<Type>::file_size_after=0;
template<class Type>
string Compress<Type>::HuffCode[256]={""};
template<class Type>
bool Compress<Type>::isShowed=false;


template<class Type>
bool Compress<Type>::Do(char *func,char *file1,char *file2)  
//func为操作代码,"-c"则执行压缩,"-u"则执行解压,"-t"则输入一串字符求Huffman编码  
{
	if(strcmp(func,"-c")==0) 
	{
		time_start=clock();  //获得进度条开始时间
		isShowed=false;
		if(file1==NULL)
		{
			cout<<"Missing Filename!"<<endl;
			return false;
		}
		cout<<"    .......................................................";  
		if(!getFileFreq(file1))return false;  //获得文件字符频数
		
		Compress<Type>::ToDo(file1,file2);  //执行压缩
		return true;
	}
	else if(strcmp(func,"-u")==0) 
	{
		time_start=clock();  //获得进度条开始时间
		isShowed=false;
		if(file1==NULL)
		{
			cout<<"Missing Filename!"<<endl;
			return false;
		}
		cout<<"    .......................................................";
		Compress<Type>::UnDo(file1,file2);  //执行解压
		return true;
	}
	else if(strcmp(func,"-t")==0)  //屏幕操作
	{
		cout<<"Type in a string(less than 30 Chars)"<<endl;
		cout<<"  :";
		char temp[31]="";
		Compress<Type>::getInputFreq(temp);  //获得输入字符的频数
		Pack Node[256];
		for(int i=0;i<256;i++)
		{
			Node[i].ch=i;
			Node[i].key=freq[i]; 
		}
		ExtBinTree<Type> *HufTree=NULL;  
		HufTree=BuildHufTree(Node,256);  //构建256个字符的Huffman树
		for(int i=0;i<256;i++)
			HuffCode[i]="";
		getCode(HufTree);  //获得Huffman编码
		cout<<"The Origin Size is:  "<<file_size*8<<" Bit"<<endl;
		cout<<"HuffmanCode for Each:\n";
		for(int i=0;i<256;i++)
			if(freq[i]>0)cout<<"  "<<(char)i<<":"<<HuffCode[i]<<endl;  //如若频数非零,则输出其Huffman编码
		cout<<"HuffmanCode for all:\n";
		cout<<"  ";
		int length_of_HuffCode=0;
		for(unsigned int i=0;i<strlen(temp);i++)
		{
			length_of_HuffCode+=(int)HuffCode[(unsigned char)temp[i]].length();
			cout<<HuffCode[(unsigned char)temp[i]];
		}
		cout<<"\nThe HuffmanCode Size is:  "<<length_of_HuffCode<<" Bit";
		cout<<"\nNow Input a HuffmanCode-String:\n  :";
		char temp1[100];
		cin>>temp1;
		cout<<"Origin Char for it:\n  ";
		ExtBinTree<Type> *p=HufTree;
		for(unsigned int i=0;i<strlen(temp1);i++)  //读取屏幕的1和0,如果是0则在Huffman树中左走,如果是1则右走.
		{
			char c=temp1[i];
			if(c=='1')
				p=p->rChild;
			else p=p->lChild;
			if(!p->lChild&&!p->rChild)  //到达叶的时候输出叶所表示的字符
			{
				char ch=p->date.ch;
				cout<<ch;
				p=HufTree;
			}
		}
		cout<<endl;
		return true;
	}
	return false;
}
template<class Type>
bool Compress<Type>::getCode(ExtBinTree<Type> *HufTree)  //获得Huffman编码
{
	string tempCode="";
	ExtBinTree<Type>*p=HufTree;
	stack<ExtBinTree<Type>*> st; //使用栈来遍历Huffman树
	while(p||st.size())  
	{
		while(p)
		{
			st.push(p);  //将当前节点入栈
			p=p->lChild;
			if(p)
				tempCode+="0";  //p=p->lChild后若非空,则在当前编码后面加0
		}
		if(st.size())
		{
			p=st.top();
			st.pop();
			if(p->lChild==NULL)  //如果到达子叶则进行编码
			{
				HuffCode[(unsigned char)p->date.ch]=tempCode;  //记录字符i的Huffman编码
				int i;
				for(i=(int)tempCode.length()-1;i>=0;i--)  //理解这步关键在用理解栈的遍历过程
					if(tempCode[i]=='0')break;
				tempCode=tempCode.substr(0,i);
			}
			p=p->rChild;
			if(p)
			{
				tempCode+="1";  //p=p->rChild后若非空,则在当前编码后面加1
			}
		}
	}
	return true;
}	

template<class Type>
bool Compress<Type>::UnDo(char *str1, char *str2 = NULL)  //解压操作
{
	char info[26];
	FILE *fi=fopen(str1,"rb");
	fread(&info,25,1,fi);  
	//文件头信息表示:
	//0--24:标示,25--28:压缩后文件大小,29--32:最后一个字节有效位数,33--48:原文件名,接下来是256个频数,各占用4个字节
	info[25]=0;
	if(strcmp(info,"CODED BY HUFFMAN,LINUXAYN")!=0)  //读取文件的标示,如若不同则终止解压
	{
		cout<<"File Corrupted or Not a .HFM File!"<<endl;
		return false;
	}
	
	fread(&file_size_after,4,1,fi);  //读入压缩后的文件大小,便于文件夹压缩(本版本尚未实现)
	int ptr=0;
	fread(&ptr,4,1,fi);  //读入最后一个字节的有效位数

	char filename_temp[16];
	fread(filename_temp,16,1,fi);  //读入原文件名

	string string1=str1;
	if(str2==NULL)  //通过str1和filename_temp生成str2(即输出文件名)
	{
		int jj=0;
		for(jj=string1.length()-1;jj>=0;jj--)
			if(string1[jj]=='\\')break;
		string1=string1.substr(0,jj+1);
		string1+=filename_temp;
		str2=(char *)string1.c_str();		
	}
	FILE *fo=fopen(str2,"wb");

	for(int i=0;i<256;i++)  //获得各字符的频数
		fread(&freq[i],4,1,fi);

	Pack Node[256];
	ExtBinTree<Type> *HufTree=NULL;
	ExtBinTree<Type> *p=NULL;
	for(int i=0;i<256;i++)
	{
		Node[i].ch=i;
		Node[i].key=freq[i];
	}
	HufTree=BuildHufTree(Node,256);  //构建Huffman树
	p=HufTree;
	char c=0;
	long int temp=0;
	char str_c[FILE_BLOCK]={0};  //整块读入文件,可以提高运行效率
	char str_o[FILE_BLOCK]={0};  //整块输出文件,可以提高运行效率
	int loc_o=0;  //当前对str_o的读写位置
	int k;
	int write_filesize=0;  
	while((k=fread(str_c,1,FILE_BLOCK,fi))>0)  //fread返回成功读取的项数
	{
		write_filesize+=k;  //已读入文件的大小
		if(feof(fi))k--;  //当以到达文件尾时,不读入最后一位  
		for(int i=0;i<k;i++)
		{
			for(int j=0;j<8;j++)  //解码
			{
				if(GetBit(str_c[i],j)) 
					p=p->rChild;
				else p=p->lChild;
				if(!p->lChild&&!p->rChild)
				{
					str_o[loc_o]=p->date.ch;
					loc_o++;
					if(loc_o==FILE_BLOCK)  //如果str_o已满,则将其指针loc_o设为0,然后整块输出到文件
					{