coding.cpp

利用霍夫曼树进行文件压缩和解压

#pragma once

# include "coding.h"

using namespace std;


//将ch的第i位设为value: value只能取1和0，0<=i<=7
unsigned char SetBit(unsigned char ch, int i,int value){
	unsigned char c1,c0;
	c1=(0x01<<(i));  //将0x00的第i位设为1,左移i-1位
	c0=c1^0xFF;  //位的异或运算：将0xFF的第i位设为0
                                //或改为c0=~c1;
    if (value==0) ch=ch & c0;
	else ch=ch | c1;
	return ch;
};

int getBit(unsigned char c, int n){   //获取c的第n位的值 ，0<=n<=7
	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:exit(0);
    }
}


Coding::Coding( const char * input )
{
	setstrkey(input);
}


//设置字符串的huffman编码
void Coding::setstrkey( const char * input ){
	int i, len=strlen(input) ;
	for( i=0 ; i<Csize ;i++ ){ 
		freq[i] = 0; 
		letter[i] = char(i);
		Code[i] = "\0";
	}//初始化数据
	for( i=0 ; i<len ;i++ )freq[int(unsigned char(input[i]))]++;//设置字母频数
	
	HuffmanTree<char >(letter, freq, 256, htree);              //建立huffman树
	setcode(1);                                                 //设置并获取编码
}

//设置文件的huffman编码
int Coding::setfilekey( const char *filename ){
    int i;
    int file_size=0; //文件大小
    char c;
	for(i=0;i<Csize;i++) {
		freq[i]=0; 
		letter[i] = char(i);
		Code[i] = "\0";
	}//初始化字符频数
    ifstream fi(filename, ios::binary);
    if(!fi){
		cerr<<"Can not open this file "<< filename<< endl;
		exit(0);
	}
	
	while(fi.get(c)){
		i=int((unsigned char)c);
		freq[i]++;                                             //设置字母频数
		file_size++;
	}
    fi.close();
   	HuffmanTree<char >(letter, freq, 256, htree);              //建立huffman树
	setcode(0);                                                 //设置并获取编码
   return file_size;                                           //返回文件长度
}

//获取字符c的编码，将字符c的Huffman编码拼接到str的后面并由它返回
void Coding::getCode(char c, char*str){
	int n = int(unsigned char(c));
	if(!Code[n].length()){
		cout<<"该字符还没进行编码！"<<endl;
		exit(0);
	}
	strcat(str,Code[n].c_str());
}


//将str中的编码转换成字节存盘，不足8位的剩余部分由strCode返回
void Coding::saveCode2File(ofstream &fo,char *str){
	char save[9];
	save[8]='\0';
	unsigned char ch=0x00;
	int i,val;
	while(strlen(str)>=8){
		strncpy(save,str,8);
		strcpy(str,&str[8]);
		for( i=0 ; i<8 ; i++){
			val = int(save[i])-48;
			ch = SetBit( ch, i, val);
		}
		fo.put(ch);
	}
}

//将strCode中的不足8位的剩余部分存盘
void Coding::saveLastCode2File( ofstream &fo, char *str ){
	int n = strlen (str);
	char save[8];
	save[8] = '\0';
	int val,i;
	strncpy(save,str,n);
	unsigned char ch=0x00;
	if( n>=8 ){ cerr<<"error!"<<endl; return; }
	for( i=0 ; i<8 ; i++){
	    if ( i< n) val = int(save[i])-48;
		else val = 0;                                       //不足8位的部分置0
		ch = SetBit( ch, i, val);
	}
	fo.put(ch);
}


void Coding::setcode(int flag ){
	htree.setcode();
	int m;
	string n;
	PostOrder<char > piter(htree);
	piter.First();
	while(piter.Isin()){
		if(piter.Isleaf())
		{
		   m = int(unsigned char(piter.getD()));
		   n = piter.getC();
		   Code[m] = n;
		  if(flag) cout<<char(m)<<"    的编码为："<<n<<endl;
		}
		++piter;
	}

}
/*
int Coding::decode(char *co, char * deco){
	PostOrder<char > piter(htree);
	int i,j=0;
	for( i = 0 ; i<strlen(co) ; i++ ){
	if(piter.Isleaf()){
			deco[j++] = piter.getD();
			piter.SettoRoot();
			strcpy( co, &co[i] );
			i=0;
		}
	if(co[i] == '0') piter.TurnLeft();
	else if(co[i] == '1') piter.TurnRight();
	else {cerr<<"输入有误，只能输入0或1，请重新输入！"<<endl; exit(0); }
	}	
	if(piter.Isleaf()) {deco[j++] = piter.getD();strcpy( co, &co[i] );}
	deco[j]='\0';
	return j;
}
*/

//解码并输出原码，多余字符由co返回
void Coding::decode(char *co,  ostream &out){
	PostOrder<char > piter(htree);
	int i,j=0;
	unsigned char c;
	for( i = 0 ; i<strlen(co) ; i++ ){               //循环
		if(piter.Isleaf()){                          //如果是叶子，获取编码
			c = piter.getD();
			out.put(c);
			piter.SettoRoot();
			strcpy( co, &co[i] );
			i=0;
		}
	if(co[i] == '0') piter.TurnLeft();               //走到左子女
	else if(co[i] == '1') piter.TurnRight();         //走到左子女
	else {cerr<<"输入有误，只能输入0或1，请重新输入！"<<endl; exit(0); }
	}	
	if(piter.Isleaf()) {                             //如果是叶子，获取编码
		c = piter.getD();
		out.put(c);
		strcpy( co, &co[i] );
	}
}


//屏幕输出编码
void Coding::printcode(const char *a){
	int i,len = strlen(a),n,k=0;
	for( i=0; i<len; i++ ){
		n = int(unsigned char(a[i]));
		k += Code[n].length();
		if(!Code[n].length()){
			cout<<"\n有效长度："<<k<<"\t没有对该字母编码："<<a[i]<<endl;
			return;
		}
		cout<<Code[n];
	}
	cout<<"\n长度："<<k<<endl;

}

//压缩存盘
int Coding::compress(const char *ifi,const char *ofi){
	ifstream fi(ifi, ios::binary);
	if(!fi){
		cerr<<"Can not open the file :"<< ifi<<endl;
		return 0;
	}
	ofstream fo(ofi, ios::binary);
	if(!fo){
		cerr<<"Can not open the file :"<< ofi<<endl;
		return 0;
	}
	char flag[4]= "HJM";
	
	fo.write((char*)(flag),sizeof(flag));           //填入"HJM"，作为判断.HJM文件的标志
	fo.write((char*)(ifi),20*sizeof(char));         //填入原文件名（包括文件类型）
	fo.seekp(24);                                   //定位最后字节的有效位数的存放位置
	fo.put(0x00);                                   //保留最后字节的有效位数
	int *iptr=new int(0);
	fo.write((char *)iptr,sizeof(int));             //保留压缩文件长度的存放位置
	int i;    
	for(i=0;i<256;i++) {                            //存放频数
			 *iptr=freq[i];
			 fo.write((char *)iptr,sizeof(int));
	 }
    //一个字符的编码长度最多是256，再加上原来尚未存盘的编码(不足一个字节)，
	//长度不超过264＋结束标志
	char * strCode=new char[265];      
	strCode[0]='\0';
	char c;
	while(fi.get(c)) {
	     getCode(c,strCode); 
	     saveCode2File(fo,strCode );  
          
	 }
	(*iptr) = fo.tellp();                  //获取压缩文件长度
	i=strlen(strCode);                     //取出最后字节的有效位数
	if(i){
	     saveLastCode2File(fo,strCode);    //将strCode中的不足8位的剩余部分存盘
		 (*iptr) = fo.tellp();             //获取压缩文件长度
         fo.seekp(24);                     
	     c=char(i);
	     fo.put(c);
		 
	}
	fo.seekp(25);
	fo.write((char *)iptr,sizeof(int));   //填入压缩文件实际长度
//	cout<<*iptr<<endl;
	fi.clear();
	int L=fi.tellg();
	int L1=*iptr;
    fi.close();     
    fo.close();
    cout<<"已成功压缩文件"<<ifi<<"到文件"<<ofi<<endl
		<<"压缩文件大小（字节）"<<L1<<"     原文件大小（字节）"<<L
		<<"\n压缩率"<<100.0*L1/L<<'%'<<endl;
	return *iptr;                         //返回压缩文件实际长度
}

//解压文件
bool Coding::decompress(const char *ifi ){
	ifstream fi(ifi, ios::binary);
	if(!fi){
		cerr<<"Can not open the file "<< ifi<<endl;
		return false;
	}
	char flag[4] ;

	//判断是否是HJM文件
	fi.read((char*)(flag),sizeof(flag));
	if(strcmp(flag,"HJM")){
		cerr<<"这不是HJM文件，本程序不能解压～"<<endl;
		return false;
	}
	char ofi[20];
	fi.read((char*)(ofi),20*sizeof(char));            //读入原文件名（包括路径）
	cout<<"使用默认解压文件名（包括路径）"<<ofi<<"?(Y or N)"<<endl;
	char c;
	cin.ignore(1);
	cin.get(c);
	if(c=='N' || c== 'n'){
    	cout<<"请输入压缩文件名（包括路径）:";
	    cin>>ofi;
	}
	ofstream fo(ofi, ios::binary);
	if(!fo){
		cerr<<"Can not open the file "<< ofi<<endl;
		return false;
	}

	fi.seekg(24);
	int ap = int(fi.get());                          //获取最后字节的有效位数
	int *iptr=new int;
 	int flen;
	fi.read((char *)iptr,sizeof(int));               //获取文件长度
	flen=*iptr;
    int i,j=0;
	for(i=0;i<Csize;i++) {      
			 fi.read((char *)iptr,sizeof(int));
			 freq[i]= *iptr;
	         letter[i] = char(i);
		     Code[i] = "\0";
	}                                                //读入频数，初始化各种数据
	HuffmanTree<char >(letter, freq, 256, htree);    //建立huffman树
	setcode(0);                                       //设置huffman码
	char fcode[9], co[257] ;
	co[0] = '\0'; fcode[8]='\0';
	char ch;
	int f=8;
	while(fi.get(ch)){
		if(int(fi.tellg())>=flen){                  //到文件结束时，处理最后字节的有效位数
			f = ap; fcode[f] = '\0';
		}
		for( i=0; i<f; i++){
			fcode[i] = getBit( ch, i) + 48;
		}
		strcat(co, fcode );                        //将单字符的编码复制到co中
		j++;
		if(j == 31){
			decode( co, fo);                       //每当字符串co满256位时进行解码并输出到文件
			j=0;
		}
	}
	if(strlen(co))	decode( co, fo);               //将剩余的字符串co进行解码并输出到文件

	int folen = fo.tellp();	
	fi.close();
	fo.close();
    cout<<"已成功解压文件"<<ifi<<"到文件"<<ofi
		<<"\n压缩文件大小（字节）"<<flen<<"     解压得到的文件大小（字节）"<<folen
		<<"\n文件压缩率为"<<100.0*flen/folen<<'%'<<endl;
	return true;
}