compression15.cpp

对流数据的压缩

// compression15.cpp : Defines the entry point for the console application.
//
//improved statistical coding

#include "stdafx.h"
#include "iostream.h"
#include "stdio.h"
#include "math.h"


typedef struct htnode
{
	int weight;
	int parent,lchild,rchild;
} * huffmantree;

typedef char * huffmancode;


//function declaration

void pad0(char *,int,int);
void blockfreqcount(char *,int *,int *,int *,int,int,int);

void huffmancoding(htnode *,huffmancode *,int *,int);
int resultoutput(FILE *,char *,int *,huffmancode *,int,int,int);

void matrixoutput(FILE *,char *,int,int);



//**************************main function***********************

int main(int argc, char* argv[])
{

	char sourcename[35];          //filename for input
	char informationname[35];     //filename for information output
	char resultname[35];          //filename for result output
	FILE *fpp,*fp,*fr;

	int width=0;                  //the width of test pattern
	int number=0;                 //the number of the patterns
	int s=0;                      //the size of the selected block
	int nb=0;                     //the number of the block
	int nbs=0;                    //the number of the encoded block
	int m;
	int total=0;
	int i,j;


//open the file

    cout << "Filename input:";
    cin >> sourcename;
	fpp=fopen(sourcename,"r");
	if (!fpp)
	{
		cout << sourcename << " could not be opened" << endl;
		return 1;
	} 
	
    cout << "informationfilename output:";
    cin >> informationname;
    fp=fopen(informationname,"w");
    if (!fp)
    {
	     cout<< informationname << "not created" << endl;
         return 1;
	}

	cout << "Filename for result:";
    cin >> resultname;
    fr=fopen(resultname,"w");
    if (!fr)
    {
	     cout<< resultname << "not created" << endl;
         return 1;
	}
 
	
//read the width and the number of the patterns

	fscanf(fpp,"%d", &width);
    fscanf(fpp,"%d", &number);
	fprintf(fp,"%s","the width and number of test patterns : ");
    fprintf(fp,"%d ",width);
	fprintf(fp,"%d\n",number);
	fprintf(fp,"%s\n","");

//read the size of the block

	cout<<"please input the size of the block you select s: ";
	cin>>s;
	fprintf(fp,"%s","the size of the selected block is :");
	fprintf(fp,"%d\n",s);
	fprintf(fp,"%s\n","");

//read the number of the block which will be encoded

	cout<<"please input the number of block which you want to encode nbs : ";
	cin>>nbs;
	fprintf(fp,"%s","the number of the encoded blocks nbs is :");
	fprintf(fp,"%d\n",nbs);
	fprintf(fp,"%s\n","");


//calculate l and wfmp

    if ( (width*number)%s==0 )    	nb=(width*number)/s;
    else            		        nb=(width*number)/s+1;

	fprintf(fp,"%s","the number of the blocks nb is :");
	fprintf(fp,"%d\n",nb);
	fprintf(fp,"%s\n","");


	char *patterns=new char[s*nb];  //the heap for the original patterns
                                            //many times we use the heap as two dimensions array
    char *ptemp;                            //the point of the array patterns
    ptemp=patterns;

   
//read the original patterns

    while(!feof(fpp))
    {
	    fscanf(fpp,"%c",ptemp);
        if(*ptemp!='\n') ptemp++;
    }
    fclose(fpp);
//	matrixoutput(fp,patterns,width,number);
	pad0(patterns,s,nb);
//	matrixoutput(fp,patterns,s,nb);


	int *frequency=new int[pow(2,s)];
	int *hfmnode=new int[nbs];
	int *nodefreq=new int[nbs+1];

	if(frequency==NULL)       cout<<"allocate error1"<<endl;

	blockfreqcount(patterns,frequency,hfmnode,nodefreq,s,nb,nbs);

	fprintf(fp,"%s\n","the selected block and their frequencies:");
	for(i=0;i<nbs;i++)
	{
		fprintf(fp,"%d ",hfmnode[i]);
		fprintf(fp,"%d\n",nodefreq[i]);
	}
	fprintf(fp,"%d\n",nodefreq[nbs]);
	fprintf(fp,"%s\n","");
	
	m=2*(nbs+1)-1;
	htnode * ht=new htnode[m];
	huffmancode * hc=new huffmancode[nbs+1];
	huffmancoding(ht,hc,nodefreq,(nbs+1));

	fprintf(fp,"%s\n","the huffmancoding:");
	for(i=0;i<nbs+1;i++)
	{
		j=0;
		while(hc[i][j]!='2')
		{
			fprintf(fp,"%c",hc[i][j]);
			j++;
		}
		fprintf(fp,"%s\n","");
	}

	total=resultoutput(fr,patterns,hfmnode,hc,s,nb,nbs);
	fprintf(fp,"%s","the total size of the compressed testset is: ");
	fprintf(fp,"%d\n",total);

	delete[]frequency;
	delete[]hfmnode;
	delete[]nodefreq;
	delete[]ht;
	delete[]hc;

	fclose(fp);
	fclose(fr);
	
	return 0;
}



//***********************fuction pad0****************************

void pad0(char *testset,int width,int number)
{
	int i;
	for(i=0;i<(width*number);i++)
	{
		if((testset[i]!='0')&&(testset[i]!='1'))
			testset[i]='0';
	}
}


//*********************function blockfreqcount*******************

void blockfreqcount(char *testset,int *freq,int *node,int *nfreq,int width,int number,int n)
{
	int i,j,k;

	for(i=0;i<pow(2,width);i++)
		freq[i]=0;

	for(i=0;i<number;i++)
	{
		k=0;
		for(j=0;j<width;j++)
		{
			if(testset[i*width+j]=='1')
				k=k+pow(2,(width-j-1));
		}
		freq[k]++;
	}
	for(i=0;i<n;i++)
	{
		k=0;
		for(j=1;j<pow(2,width);j++)
		{
			if(freq[k]<freq[j])
				k=j;
		}
		node[i]=k;
		nfreq[i]=freq[k];
		freq[k]=0;
	}
	nfreq[n]=number;
	for(i=0;i<n;i++)
		nfreq[n]=nfreq[n]-nfreq[i];

}


//***********************function huffmancoding*******************

void huffmancoding(htnode *ht,huffmancode *hc,int *w,int n)
{
	int m,i,j,k,t,s1,s2;

	if(n<=1)  return;
	m=2*n-1;
	for(i=0;i<n;i++)
	{
		ht[i].weight=w[i];
	    ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}
	for(;i<m;i++)
	{
		ht[i].weight=0;
		ht[i].parent=0;
		ht[i].lchild=0;
		ht[i].rchild=0;
	}

	//set up huffmantree
	for(i=n;i<m;i++)
	{
		//select(ht,i-1,s1,s2);
		j=0;
		while(j<i)
		{
			if(ht[j].parent==0) 
			{
				s1=j;
				j++;
				break;
			}
			j++;
		}
		while(j<i)
		{
			if(ht[j].parent==0)
			{
				s2=j;
				j++;
				break;
			}
			j++;
		}
		if(ht[s1].weight>ht[s2].weight)
		{
			k=s1; s1=s2; s2=k;
		}
		for(;j<i;j++)
		{
			if((ht[j].weight<ht[s2].weight)&&(ht[j].parent==0))
			{
				s2=j;
				if(ht[s1].weight>ht[s2].weight)
				{
					k=s1; s1=s2; s2=k;
				}
			}
		}

		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;
	}

	//coding
	char * cd=new char[n];
	cd[n-1]='2';
	for(i=0;i<n;i++)
	{
		j=n-1;
		for(k=i,t=ht[i].parent;t!=0;k=t,t=ht[t].parent)
		{
			if(ht[t].lchild==k)
				cd[--j]='0';
			else cd[--j]='1';
		}
		hc[i]=new char[n-j];
		for(k=0;k<n-j;k++)
		{
			hc[i][k]=cd[k+j];
		}
	}
	delete[]cd;


}


//*******************function resultoutput***********************

int resultoutput(FILE *f,char * testset,int *node,huffmancode *hc,int width,int number,int n)
{
	int i,j,k,t,flag;
	int total=0;

	for(i=0;i<number;i++)
	{
		k=0;
		for(j=0;j<width;j++)
		{
			if(testset[i*width+j]=='1')
				k=k+pow(2,(width-j-1));
		}
		t=0;
		flag=0;
		while(t<n)
		{
			if(k==node[t])
			{
				flag=1;
				break;
			}
			else   t++;
		}
		if(flag==1)
		{
			j=0;
	        while(hc[t][j]!='2')
			{
				fprintf(f,"%c",hc[t][j]);
				total++;
				j++;
			}
		}
		else
		{
			j=0;
	        while(hc[n][j]!='2')
			{
				fprintf(f,"%c",hc[n][j]);
				total++;
				j++;
			}
			for(j=0;j<width;j++)
			{
				fprintf(f,"%c",testset[i*width+j]);
				total++;
			}
		}
		fprintf(f,"%s\n","");		
	}

	return total;


}

//*******************function matrixoutput***********************


//this function will output a heap(array) in form of matrix
//the meaning of the function's parameters as follows:
//      f--the file for output
//      patterns--the test patterns will be output
//      width,number--the width and the number of the patterns(matrix)


void matrixoutput(FILE *f,char *patterns,int width,int number)
{
	
	int i,j;
    for ( i=0;i<number;i++ )
    {
	    for ( j=0;j<width;j++ )
		    fprintf(f,"%c",patterns[i*width+j]);
	    fprintf(f,"%s\n","");
    }
    fprintf(f,"%s\n","");
   
}