chuffman.cpp

是用c++实现的几个数字信号处理中的典型算法

#include ".\chuffman.h"

CHuffman::CHuffman(void){}
CHuffman::~CHuffman(void){}
void CHuffman::Select(HuffmanTree HT,int num,int &s1,int &s2)
{
	unsigned int weight=~0;
	unsigned int weight1=~0;
	int i;
	for(i=1;i<=num;i++){
		if(HT[i].parent)
			continue;
		if(HT[i].weight<=weight){
			weight1=weight,weight=HT[i].weight;
			s2=s1,s1=i;
		}
		else if(HT[i].weight<weight1)
			weight1=HT[i].weight,s2=i;
	}
}
void CHuffman::HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,unsigned int*weight,int n){
	if(n<=1)
		return;
	int i,m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	HuffmanTree p;
	for(p=HT+1,i=1;i<=n;++i,++p,++weight)
		p->weight=*weight,p->parent=0,p->lchild = 0,p->rchild= 0;
	for(;i<=m;++i,++p)
		p->weight=0,p->parent=0,p->lchild = 0,p->rchild= 0;
	for(i=n+1;i<m+1;++i){
		int s1,s2;
		Select(HT,i-1,s1,s2);
		HT[s1].parent=i;HT[s2].parent=i;
		HT[i].lchild=s1;
		HT[i].rchild=s2;
		HT[i].weight=HT[s1].weight+HT[s2].weight;
	}
	HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
	unsigned char* cd=(unsigned char*)malloc(n*sizeof(unsigned char));
	cd[n-1]='\0';
	for(i=1;i<=n;++i){
		int start=n-1;
		unsigned int c,f;
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent){
			if(HT[f].lchild==c)
				cd[--start]='0';
			else
				cd[--start]='1';
		}
		HC[i]=(unsigned char*)malloc((n-start)*sizeof(unsigned char));
		memcpy(HC[i],&cd[start],n-start);
	}
	free(cd);
}
void CHuffman::setBit(BYTE_8&b,int j,unsigned char c){
	static unsigned char bvec[9]={255,254,253,251,247,239,223,191,127};
	unsigned char*p=(unsigned char*)&b;
	if(c==1)
		*p|=~bvec[j];
	else
		*p&=bvec[j];
}
void CHuffman::FindIndex(const char &ch,int &i,const unsigned char*charSet,int setNum){
	int a=0,b=setNum;
	i=(a+b)/2;
	unsigned char tmp=(ch+256)%256;
	while(charSet[i]!=tmp){
		if(charSet[i]<tmp)a=i;
		else b=i;
		i=(a+b)/2;
	}
}
void CHuffman::setByte0(BYTE_8&b){memset(&b,0,1);}
void CHuffman::Coding(const unsigned char*origbuff,unsigned char*&destbuff,int origNum,int destNum,
			const HuffmanCode &HC, const unsigned char*charSet,int setNum){
	int i,l;
	destNum++;
	destbuff=new unsigned char[destNum];
	memset(destbuff,0,destNum*sizeof(char));
	int num=0;
	BYTE_8 b;
	setByte0(b);
	int index=0;
	size_t j=1,k=1;
	for(l=0;l<origNum;l++){
		FindIndex(origbuff[l],i,charSet,setNum);
		i=i+1,j=0;
		while(HC[i][j]){
			while(HC[i][j]&&k<=8){
				setBit(b,k,HC[i][j]-'0');
				k++,j++;
			}
			if(k>8){
				destbuff[num++]=b.data;
				setByte0(b),k=1;
			}
		}
	}
	if(k<=8)destbuff[num++]=b.data;
}
int CHuffman::Child(const HuffmanTree &HT,int p,int&j,const BYTE_8 &b){
	unsigned i=b[j];
	j++;
	if(i)return HT[p].rchild;
	else return HT[p].lchild;
}
void CHuffman::UnCoding(const unsigned char*origbuff,const HuffmanTree &HT,unsigned char*&destbuff,int root,int len, const unsigned char*charSet){
	destbuff=new unsigned char[HT[root].weight+1];
	memset(destbuff,0,HT[root].weight+1);
	int i,num=0,j=1;
	int p=root;
	BYTE_8 b;
	setByte0(b);
	for(i=0;i<=len;i++){
		b=*((BYTE_8*)&origbuff[i]);
		j=1;
		while(j<=8){
			while(j<=8&&HT[p].lchild&&HT[p].rchild)p=Child(HT,p,j,b);
			if(HT[p].lchild==0){
				destbuff[num++]=charSet[p-1];
				p=root;
			}
		}
	}
}
void CHuffman::compress(const char*sourcefile,const char*destfile){
	unsigned int w[256]={0};
	unsigned int pv[256]={0};
	unsigned char charSet[256]={0};
	ifstream inFile(sourcefile,ios::in|ios::binary);
	inFile.seekg(0,ios::end);
	long len=inFile.tellg();
	unsigned char *buff=new unsigned char[len];
	inFile.seekg(0,0);
	inFile.read((char*)buff,len);
	inFile.close();
	for(int i=0;i<len;i++)
		w[buff[i]]++;
	int n=0;
	for(i=0;i<256;i++){
		if(w[i]){
			charSet[n++]=i,pv[n-1]=w[i];
		}
	}
	memset(w,0,256*sizeof(int));
	memcpy(w,pv,n*sizeof(unsigned int));

	HuffmanTree HT;
	HuffmanCode HC;
	HuffmanCoding(HT,HC,w,n);

	int destNum=0;
	for(i=0;i<n;i++)
		destNum+=w[i]*strlen((char*)HC[i+1]);
	destNum/=8;

	unsigned char* buff2;
	char tag[12]="ZhouYuncai";i=0;while(i<11)tag[i++]-=20;
	Coding(buff,buff2,len,destNum,HC,charSet,n);
	ofstream outFile(destfile,ios::out|ios::binary);
	outFile.write(tag,11);
	outFile.write((char*)charSet,256*sizeof(unsigned char));
	outFile.write((char*)&n,sizeof(int));
	outFile.write((char*)&destNum,sizeof(int));
	outFile.write((char*)HT,2*n*sizeof(HTNode));
	outFile.write((char*)buff2,destNum);
	outFile.close();
}
void CHuffman::uncompress(const char*sourcefile,const char*destfile){
	unsigned char charSet[256]={0};
	ifstream inFile(sourcefile,ios::in|ios::binary);
	int n,destNum;
	char tag[12]={0};
	inFile.read(tag,11);int i=0;while(i<11)tag[i++]+=20;
	if(strcmp(tag,"ZhouYuncai")){
		cout<<"文件格式不对！"<<endl;
		return;
	}
	inFile.read((char*)charSet,256*sizeof(unsigned char));
	inFile.read((char*)&n,sizeof(int));
	inFile.read((char*)&destNum,sizeof(int));
	HuffmanTree HT=(HuffmanTree)malloc(2*n*sizeof(HTNode));
	memset(HT,0,2*n*sizeof(HTNode));
	inFile.read((char*)HT,2*n*sizeof(HTNode));
	unsigned char*buff=new unsigned char[destNum];
	inFile.read((char*)buff,destNum);
	inFile.close();
	ofstream of1(destfile,ios::out|ios::binary);
	unsigned char*buff2;
	UnCoding(buff,HT,buff2,2*n-1,destNum,charSet);
	of1.write((char*)buff2,HT[2*n-1].weight);
	of1.close();
}