huffman.c

我用C＋＋编写的Huffman压缩解压算法

#include <stdio.h>
#include <string.h>
//#define __DEBUG

unsigned long bytecount[256];
int back;
struct Huffmannode{
     int oa,parent,lchild,rchild;
     unsigned long weight;
};

typedef Huffmannode* Huffmantree;

struct info{
     int data;
     char *hc;
};

typedef info* infodex;

struct SupHuffmannode{
     int lchild;
     int rchild;
};

typedef SupHuffmannode* SupHuffmantree;
//-----------------------------------------------------------------
int Compress( FILE *fpSrc, FILE *fpDest );
int Extract( FILE *fpSrc, FILE *fpDest );
void Huffman(Huffmantree &HT,int n);
void Huffmansize(Huffmantree &HT,int n,infodex &HC);
void Superize(Huffmantree HT,SupHuffmantree &SHT,int n);
void Cpress(SupHuffmantree SHT,infodex HC,int n,FILE *fpSrc,FILE *fpDest);
//-------------------------------------------------------------------
main( int argc, char *argv[] )
{
    // Analyze parameters
    if( argc!=4 || ( strcmp( argv[3], "-p" ) && strcmp( argv[3],"-x" ) ) ){
	printf( "Usage: Hello sourcefile destfile -p or -x\n" );
	printf( "       -p use to compress the soure file.\n" );
	printf( "       -x use to extract the source file.\n" );
	return 0;
    }
    FILE *fpSrc, *fpDest;
    // Open source file
    fpSrc = fopen( argv[1], "rb" );
    if( !fpSrc ){
	printf( "Open %s failure!\n", argv[1] );
	return 0;
    }
    // Open destination file
    fpDest = fopen( argv[2], "wb" );
    if( !fpDest ){
	printf( "Create %s failure!\n", argv[2] );
	fclose( fpSrc );
	return 0;
    }
    // Operation type
    if( !strcmp( argv[3],"-p" ) ){
	// compress
	Compress( fpSrc, fpDest );
    }else{
	// extract
	Extract( fpSrc, fpDest );
    }
    // Close all files
    fclose( fpSrc ); fclose( fpDest );
    return 0;
}
//--------------------------------------------------------------------
int Compress( FILE *fpSrc, FILE *fpDest )
{
    printf( "Compressing...\n" );
    //statistic
    int ch;
    int n=0;
    for(int i=0;i<256;i++)
       bytecount[i]=0;
    while( (ch=fgetc(fpSrc))!=EOF )
	bytecount[ch]++;
    for(i=0;i<256;i++)
	 if(bytecount[i]!=0) n++;
    rewind(fpSrc);
    //Huffmantree
    Huffmantree HT;
    Huffman(HT,n);
    //HC
    infodex HC;
    Huffmansize(HT,n,HC);
#ifdef __DEBUG
    for( i=0; i<n; i++ ){
	printf( "%c: %s\n", HC[i].data, HC[i].hc );
    }
#endif
    //SuperHuffmantree
    SupHuffmantree SHT;
    Superize(HT,SHT,n);
    //compress
    Cpress(SHT,HC,n,fpSrc,fpDest);
    rewind(fpSrc);
    fputc(back,fpDest);
    for(i=0;i<n;i++)
    {     delete []HC[i].hc;}
    delete []HC;
    return 0;
}
//--------------------------------------------------------------------
int Extract( FILE *fpSrc, FILE *fpDest )
{
    printf( "Extracting...\n" );
    //Get SupHuffmantree
    back=fgetc(fpSrc);
    int n;
    n=fgetc(fpSrc);
    SupHuffmantree SHT;
    SHT=new SupHuffmannode[2*n-1];
    for(int i=0;i<2*n-1;i++)
	 if(fread(&SHT[i],sizeof(struct SupHuffmannode),1,fpSrc)!=1)
	     printf("file read error\n");
    //Extract
    int ch,w,q,m,sh;
    ch=fgetc(fpSrc);
    w=fgetc(fpSrc);
    m=2*n-2;     //SupHuffmantree root
    while(w!=EOF )
    {
	  for( int bitcount=0; bitcount<8; bitcount++,ch<<=1 ){
	      if( ch & 0x80 )
		  m = SHT[m].rchild;
	      else
		  m = SHT[m].lchild;
	      if( SHT[m].lchild==-1 ){
		  fputc( SHT[m].rchild, fpDest );
		  m = 2*n-2;
	      }
	  }
	  ch=w;
	  w=fgetc(fpSrc);
    }
    for( int bitcount=0; bitcount<back; bitcount++,ch<<=1 ){
	      if( ch & 0x80 )
		  m = SHT[m].rchild;
	      else
		  m = SHT[m].lchild;
	      if( SHT[m].lchild==-1 ){
		  fputc( SHT[m].rchild, fpDest );
		  m = 2*n-2;
	      }
	  }
    return 0;
}
//-----------------------------------------------------------------
void Huffman(Huffmantree &HT,int n)
{
    HT=new Huffmannode[2*n-1];
    int i,j;
    for(i=0,j=0;i<256;i++)
    {
	   if(bytecount[i]!=0)
	   {     HT[j].oa=i;
		 HT[j].weight=bytecount[i];
		 HT[j].parent=-1;
		 HT[j].lchild=-1;
		 HT[j].rchild=-1;
		 j++;
	   }
    }
    int s1,s2;
    for(i=n;i<2*n-1;i++){
	s1=-1; s2=-1;
	for(int j=0;j<i;j++)
	    if(HT[j].parent==-1){
		if( s1==-1 )
		    s1=j;
		else if( HT[j].weight<HT[s1].weight ){
		    s2 = s1;
		    s1 = j;
		}else if( s2==-1 || HT[j].weight<HT[s2].weight )
		    s2 = j;
	    }
	HT[s1].parent=i;
	HT[s2].parent=i;
	HT[i].parent=-1;
	HT[i].lchild=s1;
	HT[i].rchild=s2;
	HT[i].weight=HT[s1].weight+HT[s2].weight;
     }
}
//----------------------------------------------------------------
void Huffmansize(Huffmantree &HT,int n,infodex &HC)
{
     int i,c,f;
     HC=new info[n];
     for(i=0;i<n;i++)
     {
	    HC[i].data=HT[i].oa;
	    HC[i].hc=new char[n];
	    int p=n-1;
	    HC[i].hc[p]='\0';
	    for(c=i,f=HT[c].parent;f!=-1;c=f,f=HT[c].parent)
	    {
		if(HT[f].lchild==c) HC[i].hc[--p]='0';
		else                HC[i].hc[--p]='1';
	    }
	    strcpy(HC[i].hc,HC[i].hc+p);
     }
}
//-----------------------------------------------------------------
void Superize(Huffmantree HT,SupHuffmantree &SHT,int n)
{
     SHT=new SupHuffmannode[2*n-1];
     for(int i=0;i<n;i++)
     {
	    SHT[i].lchild=-1;
	    SHT[i].rchild=HT[i].oa;
     }
     for(i=n;i<2*n-1;i++)
     {
	    SHT[i].lchild=HT[i].lchild;
	    SHT[i].rchild=HT[i].rchild;
     }
}
//-----------------------------------------------------------------------
void Cpress(SupHuffmantree SHT,infodex HC,int n,FILE *fpSrc,FILE *fpDest)
{   //put SHT to Destination
    fputc(0,fpDest);
    fputc(n,fpDest);
    for(int i=0;i<2*n-1;i++)
	    fwrite(&SHT[i],sizeof(struct SupHuffmannode),1,fpDest);
    //put Sourcefile to Destination
    int sh,q,bit,bitcount,a,*p;
    q=0;bitcount=0;p=&q;
    while(!feof(fpSrc))
    {
	    sh=fgetc(fpSrc);
	    bit=0;
	    for(i=0;i<n;i++)
	    {     if(HC[i].data==sh)
		  {      while(HC[i].hc[bit]!='\0')
			 {      *p<<=1;
				if(HC[i].hc[bit]=='1')
				    *p|=1;
				bitcount++;
				bit++;
				if(bitcount>=8)
				{   fputc(q,fpDest);
				    q=0;p=&q;
				    bitcount=0;
				}
			 }
			 break;
		  }
	    }
    }
    *p<<=(8-bitcount);
    fputc(q,fpDest);
    /*the second way
    while(bitcount<8)
    {
	    float w1=1.0;
	    int x=0;
	    for(i=0;i<256;i++)
		if(bytecount[i]!=0)
		{     x++;
		      if(bytecount[i]<w1)
		      {	   w1=bytecount[i];
			   a=x-1;
		      }
		}
	    bit=0;
	    while(HC[a].hc[bit+1]!='\0')
	    {    *p<<=1;
		 if(HC[a].hc[bit]=='1')
		     *p|=1;
		 bitcount++;
		 bit++;
		 if(bitcount>=8)
		 {    fputc(q,fpDest);
		      break;
		 }
	    }
    }*/
    back=bitcount;
}