huffmantree.h

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

						fwrite(str_o,FILE_BLOCK,1,fo);
						loc_o=0;
					}
					p=HufTree;
					temp++;
				}
			}
		}
		showRate((int)(write_filesize*100.0/file_size_after));  //显示进度条
	}
	if(loc_o!=0)
		fwrite(str_o,loc_o,1,fo);  //将剩余未写的部分写进文件中
	fseek(fi,-1L,SEEK_END);
	fread(&c,1,1,fi);  //处理最后一个字节
	if(ptr==0)ptr=8;
	for(int i=0;i<ptr;i++)
	{
		if(GetBit(c,i))
			p=p->rChild;
		else p=p->lChild;
		if(!p->lChild&&!p->rChild)
		{
			char ch=p->date.ch;
			fwrite(&ch,1,1,fo);
			p=HufTree;
			temp++;
		}
	}
	time_finish=clock();  //进度条时间停
	cout<<" Used "<<(time_finish-time_start)/1000<<" secs"<<endl;  //输出所用时间
	cout<<"  UnCompressed file has been successfully saved to "<<str2<<endl;
	fclose(fi);
	fclose(fo);
	return true;
}

template<class Type>
void Compress<Type>::ToDo(char *str1,char *str2=NULL)  //压缩操作
{
	Pack Node[256];
	ExtBinTree<Type> *HufTree=NULL;
	for(int i=0;i<256;i++)
	{
		Node[i].ch=i;
		Node[i].key=freq[i];
	}
	HufTree=BuildHufTree(Node,256);
	getCode(HufTree);  //构建Huffman树并获得Huffman编码
	if(!str2)
	{
		str2=new char[strlen(str1)+6];
		str2[0]=0;
		strcat(str2,str1);
		strcat(str2,".hfm");
	}
	CompresstoFile(str1,str2);  //将文件1压缩成文件2
}
template<class Type>
bool Compress<Type>::CompresstoFile(char *str1,char *str2)
{
	FILE *fo=fopen(str2,"wb");
	FILE *fi=fopen(str1,"rb");
	if(!fi||!fo)
	{
		cout<<"File Failed to Open!"<<endl;
		return false;
	}
	//文件头信息表示:
	//0--24:标示,25--28:压缩后文件大小,29--32:最后一个字节有效位数,33--48:原文件名,接下来是256个频数,各占用4个字节
	char info[]="CODED BY HUFFMAN,LINUXAYN";
	fwrite(info,25+8+16,1,fo);  //多写几个位置是为了后面补写25--28,29--32,33-48的内容 
	for(int i=0;i<256;i++)
		fwrite(&freq[i],4,1,fo);
	  
	int ptr=0;  //最后一个字节的有效位数
	file_size_after=0;
	int kk=0;
	int j;
	char ch;
	unsigned long int load_filesize;
	fseek(fi,0,2);
	load_filesize=ftell(fi);
	fseek(fi,0,0);  //获得文件大小
	char load_file[FILE_BLOCK]={0};  //整块读入文件
	char c[FILE_BLOCK]={0};  //整块写入文件
	int k;
	int loc_c=0;  //当前写入位置
	int temp_load_filesize=0;  
	while((k=fread(load_file,1,FILE_BLOCK,fi))>0)
	{
		temp_load_filesize+=k;  //已读入文件大小
		for(int i=0;i<k;i++)
		{
			j=(int)(unsigned char)load_file[i];
			for(unsigned int i=0;i<HuffCode[j].length();i++)  //编码
			{
				if(HuffCode[j][i]=='1')
					SetBit_One(c[loc_c],ptr);
				ptr++;
				if(ptr==8)  //满一个字节时
				{
					loc_c++;
					ptr=0;
					if(loc_c==FILE_BLOCK)  //满一个写入块时
					{
						fwrite(c,FILE_BLOCK,1,fo);
						loc_c=0;
						file_size_after+=FILE_BLOCK;
						for(int ii=0;ii<FILE_BLOCK;ii++)
							c[ii]=0;						
					}	
				}
			}
		}
		showRate((int)(30+70*(temp_load_filesize*1.0/load_filesize)));  //显示进度条
	}

	if(loc_c!=0)  //写入剩余未写入的部分
	{
		fwrite(c,loc_c+1,1,fo);
		file_size_after+=loc_c+1;
	}
	fseek(fo,25L,SEEK_SET);
	fwrite(&file_size_after,4,1,fo);  //将压缩后文件大小和最后一个字节有效位数写进去
	fwrite(&ptr,4,1,fo);
	int jj=0;
	for(jj=(int)strlen(str1);jj>=0;jj--)
		if(str1[jj]=='\\')break;
	string string1=str1;
	string1=string1.substr(jj+1,string1.length()-jj);
	fwrite(string1.c_str(),16,1,fo);  //将原文件名写入
	time_finish=clock();
	cout<<" Used "<<(time_finish-time_start)/1000<<" secs"<<endl;  //输出压缩所用时间

	cout<<"  Compressed file has been sucessfully saved to "<<str2<<endl;
	cout<<"  The Compression Ratio is: ";
	double CompRation=(file_size_after+25+8+16+256*4)*1.0/file_size;
	cout<<file_size_after+25+8+16+256*4<<"/"<<file_size<<"="<<100*CompRation<<"%"<<endl;  //输出压缩比率
	fclose(fi);
	fclose(fo);
	return true;
}
template<class Type>
bool Compress<Type>::getInputFreq(char *str)  //获得屏幕输入字符的频数
{
	char c=0;
	file_size=0;
	for(int i=0;i<256;i++)
		freq[i]=0;
	fflush(stdin);
	cin.getline(str,30,10);
	for(unsigned int j=0;j<strlen(str);j++)
	{
		int i=(int)((unsigned char)str[j]);
		freq[i]++;
		file_size++;
	}
	return true;
}
template<class Type>
bool Compress<Type>::getFileFreq(char *str)  //取得文件中各字符的频数
{
	FILE *fi=fopen(str,"rb");
	if(!fi)
	{
		cout<<"File Failed to Open."<<endl;
		return false;
	};
	for(int i=0;i<256;i++)
		freq[i]=0;
	file_size=0;
	file_size_after=0;
	char c=0;
	unsigned long int load_filesize;
	fseek(fi,0,2);
	load_filesize=ftell(fi);
	fseek(fi,0,0);  //获得文件大小以方便进度条显示
	char load_file[FILE_BLOCK]={0};
	int k;
	while((k=fread(load_file,1,FILE_BLOCK,fi))>0)
	{
		for(int i=0;i<k;i++)
		{
			int ii=(int)((unsigned char)load_file[i]);
			freq[ii]++;
			file_size++;
		}	
		showRate((int)(file_size*1.0/load_filesize*30));
	}
	fclose(fi);
	return true;
}
template<class Type>
ExtBinTree<Type>* Compress<Type>::BuildHufTree(Type *fr, int n)  //构建Huffman树
{
	ExtBinTree<Type> *first,*second,*HufTree;
	ExtBinTree<Type> *Node=new ExtBinTree<Type>[n];
	int Code_cnt=0;
	for(int i=0;i<n;i++)  //只将频数大于0的字符进行构建
	{
		if(fr[i].key>0)
		{
			Node[Code_cnt].date.ch=fr[i].ch;
			Node[Code_cnt].date.key=fr[i].key;
			Node[Code_cnt].lChild=Node[i].rChild=NULL;

			Code_cnt++;
		}
	}
	n=Code_cnt;
	MinHeap<ExtBinTree<Type>> hp(Node,n);  //构建最小堆
	for(int i=0;i<n-1;i++)
	{
		first=hp.RemoveMin();  //当只有一种类型的字符时会出错!
		second=hp.RemoveMin();
		HufTree=new ExtBinTree<Type>(first,second);
		hp.Insert(HufTree);
	}
	return HufTree;
}
template<class Type>
inline void Compress<Type>::SetBit_One(char &c, int n)  //将字符C的第N位设为1
{
	switch(n)
	{
	case 0:
		c=c|0x01;return;
	case 1:
		c=c|0x02;return;
	case 2:
		c=c|0x04;return;
	case 3:
		c=c|0x08;return;
	case 4:
		c=c|0x10;return;
	case 5:
		c=c|0x20;return;
	case 6:
		c=c|0x40;return;
	case 7:
		c=c|0x80;return;
	default:
		cout<<"The N is illegal!"<<endl;
		return;
	}
}
template<class Type>
bool Compress<Type>::GetBit(char &c, int n)  //取得字符C的第n位
{
	switch(n)
	{
	case 0:return 0!=(c&0x01);
	case 1:return 0!=(c&0x02);
	case 2:return 0!=(c&0x04);
	case 3:return 0!=(c&0x08);
	case 4:return 0!=(c&0x10);
	case 5:return 0!=(c&0x20);
	case 6:return 0!=(c&0x40);
	case 7:return 0!=(c&0x80);
	default:
		cout<<"The N is illegal!"<<endl;
		return false;
	}
}
template<class Type>
void Compress<Type>::showRate(int k)  //进度条显示函数
{
	if(!isShowed)
		isShowed=true;
	else
		cout<<"\b\b\b";
	if(k<10)
		cout<<"0";
	if(k>100)
		cout<<"100";
	else
		cout<<k<<"%";
}
#endif