compression11.cpp

对流数据的压缩

	    t1=0;
	    for ( j=0;j<number;j++ )
		{
		    if ( rcomp[j]==i )
			{
			    for ( k=0;k<width;k++ )
				{
				    temp1[t]=patterns[j*width+k];
				    t++;
				}
			    temp2[t1]=j;
			    t1++;   //the size of the clique
		   }
	   }

	   for ( j=0;j<width;j++ )
	   {
		   k=0;
		   while ( k<t1 )
		   {
			   if( temp1[k*width+j]=='-') k++;
			   else
			   {
				   temp1[j]=temp1[k*width+j];
				   break;
			   }
		   }
	   }

	   t=temp2[0];
	   for ( j=0;j<width;j++ )
	   {
		   patterns[t*width+j]=temp1[j];
	   }
	   for ( j=1;j<t1;j++ )
	   {
		   t=temp2[j];
		   patterns[t*width]='2';
	   }
   }
 
   i=1;
   for ( j=1;j<number;j++ )
   {
	   if( patterns[j*width]!='2' ) 
	   {
		   for ( k=0;k<width;k++ )
			   patterns[i*width+k]=patterns[j*width+k];
		   i++;
	   }
   }

   delete[]temp1;
   delete[]temp2;

   return i;
}




//*******************function rowcompalg***********************


//this function transfer allocate three functions above to complete the first compression.
//the meaning of the function's parameters as follows:
//      f--the point of the file to output the information
//      patterns--the test patterns will be compressed
//      width,number--the width and the number of the patterns
//this function will return the number of patterns after compatible processing


int rowcompalg(FILE *f,char *patterns,int width,int number)
{
    int *graphg=new int[number*number];    //the graph G for the compatible matrix 
    int *rcomp=new int[number];            //show the compatible relationship 
    int tm;                                //the number of the vectors in the array in which the compatible vectors have been deleted
    int temp=0;

	if(graphg==NULL)   cout<<"allocate error0"<<endl;

	temp=compgraphset(patterns,graphg,width,number);
    temp=maxcliquegreedy(f,graphg,rcomp,number,temp);//greedy algorithm.
    tm=comppatdelete(patterns,rcomp,width,number,temp);
/*	fprintf(f,"%s\n","the fmatpat after compatible processing: ");
	matrixoutput(f,patterns,width,tm);*/

	delete[]graphg;
    delete[]rcomp; 
	return tm;
}





//*******************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","");
   
}





//*******************function distgraphset***********************


//this function set up the distance graph of the patterns
//the distance between two patterns equals the number of the uncompatible bits
//and we think the distance between a pattern to itself is maxdistance+1(infinite).here it is width+1.
//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be checked
//      graphg--the distance graph
//      width,number--the width and the number of the patterns


void distgraphset(char *patterns,int *graphg,int width,int number)
{
	    
	int i,j,k,cn;
	for(i=0;i<number;i++)
		for(j=0;j<number;j++)
		{
			k=0;
		    cn=0;//the distance
		    while(k<width)
			{
				if((patterns[i*width+k]!='-')&&(patterns[i*width+k]!='-'))			
				{
					if(patterns[i*width+k]==patterns[j*width+k])
						k++;
				    else
					{
						cn++;
					    k++;
					}
				}
			    else k++;
		   
			}
		    graphg[i*number+j]=cn;
		    if(i==j)
				graphg[i*number+j]=width+1;
		}
}





//********************function patternsort***********************


//this function will sort the patterns in order to make the sum of the distances of the patterns adjoined as small as possible
//this is a greedy algorithm
//we begin from the first pattern,and find the pattern which has the shortest distance to the first pattern.
//then begin from this new pattern to find the next pattern and just one by one as this
//the meaning of the function's parameters as follows:
//      patterns--the test patterns need be be sorted
//      temp--the heap room to save the sorted patterns
//      graphg--the distance graph
//      width,number--the width and the number of the patterns


void patternsort(char *patterns,char *temp,int *graphg,int width,int number)
{
	int i,j,k,t=0;
	int p=0;
    do
	{
		for(i=0;i<width;i++)
		{
			temp[t]=patterns[p*width+i];
		    t++;
		}
	    for(i=0;i<number;i++)
			graphg[i*number+p]=width+1;
	    j=graphg[p*number];
	    for(i=0;i<number;i++)
		{
			if(j>graphg[p*number+i])
			{
				j=graphg[p*number+i];
			    k=i;
			}
		}
	    p=k;

	}while(j<width+1);
}





//*******************function firstpattern**********************


//this function will confirm the first pattern as compared standard
//of course,it will be changed as the compare goes on.
//the first pattern is consisted of the first specified bit of every column of test set
//if there is not specified bit,we will pad '0'.
//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be checked
//      temp--the heap room to save the first pattern
//      width,number--the width and the number of the patterns(matrix)


void firstpattern(char *patterns,char *temp,int width,int number)
{
	int i,j;   
	for(i=0;i<width;i++)
    {
		j=0;
	    temp[i]='0';
        while(j<number)
		{
			if((patterns[j*width+i]=='0')||(patterns[j*width+i]=='1'))
			{
				temp[i]=patterns[j*width+i];
		        j++;
		        break;
			}
	        else j++;
		}
	}
}





//*******************function maxdistfind************************


//this function is used to find the maximum of the distances between the sorted patterns
//it scans the whole test set
//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be checked
//      first--the first(standard) pattern
//      width,number--the width and the number of the patterns(matrix)


int maxdistfind(char *patterns,char *first,int width,int number)
{
	int i,j,k,max=0;
	char *temp=new char[width];
	
	for (i=0;i<width;i++)
		temp[i]=first[i];

    for(i=1;i<number;i++)
    {
		j=0;
		k=0;
	    while(j<width)
		{
			if((patterns[i*width+j]=='0')||(patterns[i*width+j]=='1'))
			{
				if(patterns[i*width+j]==temp[j]) j++;
	            else
				{
					temp[j]=patterns[i*width+j];
					k++;
	                j++;
				}
			}
	        else j++;
	
		}
		if(max<k)    max=k;
	}
	delete[]temp;
	return max;
}




//*******************function log2upl**********************


//this small function is used to gain the upper limit of log2(x)


int log2upl(int x)
{
	int y;
	if ((log10(x)/log10(2))==int((log10(x)/log10(2))))
		y=int((log10(x)/log10(2)));
    else
		y=int((log10(x)/log10(2)))+1;
	return y;

}





//*******************function positioncao************************


//this function completes the compare and output of the position
//in every row of output file
//first we output the number(fixed-length1(dmax)) of the different position
//then we output the different position values(fixed-length2(lmax))
//the meaning of the function's parameters as follows:
//      f--the file for output
//      patterns--the test patterns will be checked
//      temp--the first(standard) pattern
//      width,number--the width and the number of the patterns(matrix)
//      dmax--the length of the number of the different position
//      lmax--the length of the different position values
//this function will return the total number(bits) for output 
 

int positioncao(FILE *f,char *patterns,char *temp,int width,int number,int dmax,int lmax)
{

	int i,j,k,cn,p,q,p1,total=0;
	int *temp1=new int[width];
	for(i=1;i<number;i++)
    {
		j=0;
		k=0;
		cn=0;
	    while(j<width)
		{
			if((patterns[i*width+j]=='0')||(patterns[i*width+j]=='1'))
			{
				if(patterns[i*width+j]==temp[j]) j++;
	            else
				{
					temp[j]=patterns[i*width+j];
	                temp1[k]=j;
					k++;
					cn++;
	                j++;
				}
			}
	        else j++;
	
		}
   	    for(j=(dmax-1);j>=0;j--)
		{
			p=int(cn/pow(2,j));
			fprintf(f,"%d",p);
			total++;
			cn=cn-p*int(pow(2,j));
		}//output the number
		for(q=0;q<k;q++)
		{
			p1=temp1[q];
			for(j=(lmax-1);j>=0;j--)
			{
				p=int(p1/pow(2,j));
			    fprintf(f,"%d",p);
			    total++;
			    p1=p1-p*int(pow(2,j));
			}
		}//output the position
		fprintf(f,"%s\n","");
	}
	return total;
}





//******************function positionmarkalg********************


//this function transfer allocate six functions above to complete the second compression.
//the meaning of the function's parameters as follows:
//      f1--the point of the file to output the information
//      f2--the point of the file to output the result
//      patterns--the test patterns will be compressed
//      width,number--the width and the number of the patterns
//this function will return the total number(bits) of compressed test set except the first pattern



int positionmarkalg(FILE *f1,FILE *f2,char *patterns,int width,int number)
{

	int smax=0;                  //the length of the maximal number of the different positions  
	int lmax=0;                  //the length of the position value
    char *temp2=new char[width]; //a pattern consisted of the first specified value of every column;otherwise pad 0.
    int *temp1=new int[number*number];
	char *temp=new char[width*number];
	int i;

	if(temp2==NULL) cout<<"allocate error3"<<endl;
	if(temp1==NULL) cout<<"allocate error4"<<endl;
	if(temp==NULL) cout<<"allocate error5"<<endl;

	distgraphset(patterns,temp1,width,number);
	patternsort(patterns,temp,temp1,width,number);

	firstpattern(temp,temp2,width,number);
	matrixoutput(f2,temp2,width,1);

	smax=maxdistfind(temp,temp2,width,number);
	fprintf(f1,"%s","the number of the changed bits in every pattern: ");
	fprintf(f1,"%d\n",smax);
	fprintf(f1,"%s\n","");
	
	smax=int((log10(smax)/log10(2)))+1;
	fprintf(f1,"%s","the length of the number value of the changed bits in every pattern: ");
	fprintf(f1,"%d\n",smax);
	fprintf(f1,"%s\n","");

	lmax=log2upl(width);
	fprintf(f1,"%s","the length of the position value: ");
	fprintf(f1,"%d\n",lmax);
	fprintf(f1,"%s\n","");

	i=positioncao(f2,temp,temp2,width,number,smax,lmax);

	delete[]temp;
	delete[]temp1;
	delete[]temp2;

	return i;
}