compression12.cpp

对流数据的压缩

   if(tgg==NULL)      cout<<"allocate error2"<<endl;

   fprintf(f,"%s\n","the positions of the shanchu lines:");

   flag=0;//count the number of the groups(cliques)   
   while(total!=0)
   {
	   for ( i=0;i<(n*n);i++ )
	       gg[i]=graphg[i];
           pgg2=n;
	   for ( i=0;i<n;i++ )
	       scl[i]=i;
	   flag++;
	   do
	   {
            for ( i=0;i<pgg2;i++ )
				ncomp[i]=0;
			for ( i=0;i<pgg2;i++ )
				for ( j=0;j<pgg2;j++ )
				{
					if( gg[i*pgg2+j]==1)
						ncomp[i]++;
				}
		    t2=ncomp[0];
            tmax=0;
            for( t1=1;t1<pgg2;t1++ )
			{
	            if( t2<ncomp[t1] )
				{
		            t2=ncomp[t1];
		            tmax=t1;
				}
			}
			t=scl[tmax];            //the position of the vector in graphg
			fprintf(f,"%d ",t);     //output the position of the shanchu line
			rcomp[t]=flag;          //the compatible vectors have the same value in the corresponding positions in the array rcomp.this can be used later.
			for ( i=0;i<n;i++ )
			{
				if(graphg[i*n+t]==1)
				{
					graphg[i*n+t]=0;
					total--;
				}
				if(graphg[t*n+i]==1)
				{
					graphg[t*n+i]=0;
					total--;
				}
			}
			pgg1=pgg2;
			pgg2=0;
			for ( i=0;i<pgg1;i++ )
			{
				if( gg[tmax*pgg1+i]==1 )
				{
					tscl[pgg2]=i;
					pgg2++;
				}
			}
			for ( i=0;i<pgg2;i++ )
			{
				t1=tscl[i];
				scl[i]=scl[t1];      //t1 increases progressively
				for ( j=0;j<pgg2;j++ )
				{
					t2=tscl[j];
					tgg[i*pgg2+j]=gg[t1*pgg1+t2];
				}
					
			}
			for ( i=0;i<(pgg2*pgg2);i++ )
					gg[i]=tgg[i];			

	   }while(pgg2!=0);
	   
	   fprintf(f,"%s\n","");
   }
   fprintf(f,"%s\n","");

   delete[]gg;
   delete[]tgg;
   delete[]ncomp;
   delete[]scl;
   delete[]tscl;

   return flag;
}




//********************function comppatdelete*******************


//this fuction will delete the compatible vectors in the test patterns according to the rcomp

//first the compatible vectors belong to same clique will be resave to the heap(array) tfmat in order to process easily
//then we will specify the bits that can be specified in a clique
//and rewrite the specified vector to the first appeared position in the original array 
//and char 2 is rewited to the first cells of the other patterns
//at last,scan the array.if the first cell of the vector in array is char 2,delete this vector

//the meaning of the function's parameters as follows:
//      patterns--the test patterns will be processed
//      rcomp--compatible mark array(as above)
//      width,number--the width and the number of the patterns
//      n--the number of the cliques
//this function will return the number of the patterns in which the compatible ones have been deleted.

//在图中去掉在一个相容类中出现过的一个接点
int comppatdelete(char *patterns,int *rcomp,int width,int number,int n)
{

	int i,j,k,t,t1;
	char *temp1=new char[width*number];   
	int *temp2=new int[number];

	for ( i=1;i<=n;i++ )
    {
	    t=0;
	    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","");
		fprintf(f,"%s\n","");
    }
    fprintf(f,"%s\n","");
   
}




/*//*******************function shiftedfdr***********************


//shifted FDR

int shiftedfdr(FILE *f,int l)
{
	l--;  //shift

	int i,j,k=0;
	int total=0;
	if ((log10(l+3)/log10(2)-1)==int((log10(l+3)/log10(2)-1)))
		j=int((log10(l+3)/log10(2)-1));
    else
		j=int((log10(l+3)/log10(2)-1))+1;
	for(i=1;i<j;i++)
	{
		fprintf(f,"%c",'1');
		total++;
		k=k+pow(2,i);
	}
	fprintf(f,"%c",'0');
	total++;
	l=l-k;
	for(i=(j-1);i>=0;i--)
	{
		k=int(l/pow(2,i));
		fprintf(f,"%d",k);
		total++;
		l=l-k*int(pow(2,i));
	}
	fprintf(f,"%s\n","");
	return total;

	
}

//*******************function alterrunlen***********************


//alternating run-length

int alterrunlen(FILE *f,char *patterns,int n)
{
	int pp,nsame,total=0;
	char pt;
	pp=0;
	nsame=1;
	pt=patterns[pp];
	pp++;
	while(pp<n)
	{
		if((patterns[pp]=='-')||(pt==patterns[pp]))
		{
			pp++;
			nsame++;
		}
		else
		{
			total=total+shiftedfdr(f,nsame);
			nsame=1;
			pt=patterns[pp];
			pp++;
		}
	}
	return total;

}

*/