compression4.cpp

对流数据的压缩

	   t=tscl[0];
	   for ( j=0;j<wfmp;j++ )
	   {
		   fmatpat[t*wfmp+j]=tfmat[j];
	   }
	   for ( j=1;j<t1;j++ )
	   {
		   t=tscl[j];
		   fmatpat[t*wfmp]='2';
	   }
   }

 
//if the first cell of the patterns in the formatted array is char 2,delete this pattern
   i=1;
   for ( j=1;j<m;j++ )
   {
	   if( fmatpat[j*wfmp]!='2' ) 
	   {
		   for ( k=0;k<wfmp;k++ )
			   fmatpat[i*wfmp+k]=fmatpat[j*wfmp+k];
		   i++;
	   }
   }
   tm=i;

   fprintf(fp,"%s ","the number of the vectors after the compatible vectors have been deleted:");
   fprintf(fp,"%d\n",tm);
   fprintf(fp,"%s\n","");

   delete[]tscl;
   delete[]rcomp;
   delete[]tfmat;

//output the array fmatpat in which the compatible patterns have been deleted
   fprintf(fp,"%s\n","the processed fmatpat:");
   for ( i=0;i<tm;i++ )
   {
	   for ( j=0;j<wfmp;j++ )
		   fprintf(fp,"%c",fmatpat[i*wfmp+j]);
	   fprintf(fp,"%s\n","");
   }
   fprintf(fp,"%s\n","");


//find the compatible relationship of the column
//this is the second time to look for the compatible cliques
//here we establish the dictionary and output the results
//as above
   
   int *graphgg=new int[wfmp*wfmp];//the compatible matrix of the columns
   int *ggg=new int[wfmp*wfmp];
   int *tggg=new int[wfmp*wfmp];
   int *sclg=new int[wfmp];
   int *tsclg=new int[wfmp];
   int *ncompg=new int[wfmp];//the degree of every vertex
   int *tcompg=new int[wfmp];
   char *dictionary=new char[wfmp*tm];
   char *tdic=new char[wfmp*tm];
   int pggg1,pggg2;
   int nd=0;

   if(graphgg==NULL) cout<<"allocate error0"<<endl;
   if(ggg==NULL) cout<<"allocate error1"<<endl;
   if(tggg==NULL) cout<<"allocate error2"<<endl;
   if(sclg==NULL) cout<<"allocate error3"<<endl;
   if(tsclg==NULL) cout<<"allocate error4"<<endl;
   if(ncompg==NULL) cout<<"allocate error5"<<endl;
   if(tcompg==NULL) cout<<"allocate error6"<<endl;
   if(dictionary==NULL) cout<<"allocate error7"<<endl;
   if(tdic==NULL) cout<<"allocate error8"<<endl;
//set up the graph G(graphgg)
   temp=0;
   for ( i=0;i<wfmp;i++ )
   {
	   for ( j=0;j<wfmp;j++ )
	   {
		   fcomp=0;
		   k=0;
		   while ( k<tm )
		   {
			   if (((fmatpat[k*wfmp+i]=='0')||(fmatpat[k*wfmp+i]=='1'))&&((fmatpat[k*wfmp+j]=='0')||(fmatpat[k*wfmp+j]=='1')))
			   {
				   if (fmatpat[k*wfmp+i]==fmatpat[k*wfmp+j])  k++;
				   else
				   {
					   graphgg[i*wfmp+j]=0;
					   fcomp=1;
					   break;
				   }
			   }
			   else k++;
		   }
		   if ((fcomp==0)&&(i!=j))
		   {
			   graphgg[i*wfmp+j]=1;
			   temp++;
		   }
		   if (i==j) graphgg[i*wfmp+j]=0;
	   }
   }
   
//greedy algorithm
   fcomp=0;
   while(temp!=0)
   {
	   for ( i=0;i<(wfmp*wfmp);i++ )
	       ggg[i]=graphgg[i];
           pggg2=wfmp;
	   for ( i=0;i<wfmp;i++ )
	       sclg[i]=i;
	   fcomp++;
	   tp1=0;
	   do
	   {
            for ( i=0;i<pggg2;i++ )
				ncompg[i]=0;
			for ( i=0;i<pggg2;i++ )
				for ( j=0;j<pggg2;j++ )
				{
					if( ggg[i*pggg2+j]==1)
						ncompg[i]++;
				}
		    t2=ncompg[0];
            tmax=0;
            for( t1=1;t1<pggg2;t1++ )
			{
	            if( t2<ncompg[t1] )
				{
		            t2=ncompg[t1];
		            tmax=t1;
				}
			}
			t=sclg[tmax];
			fprintf(fp,"%d ",t);
			tcompg[tp1]=t;
			tp1++;
			for ( i=0;i<wfmp;i++ )
			{
				if ( graphgg[i*wfmp+t]==1 )
				{
					graphgg[i*wfmp+t]=0;
					temp--;
				}
				if ( graphgg[t*wfmp+i]==1 )
				{
					graphgg[t*wfmp+i]=0;
					temp--;
				}
			}
			pggg1=pggg2;
			pggg2=0;
			for ( i=0;i<pggg1;i++ )
			{
				if( ggg[tmax*pggg1+i]==1 )
				{
					tsclg[pggg2]=i;
					pggg2++;
				}
			}
			for ( i=0;i<pggg2;i++ )
			{
				t1=tsclg[i];
				sclg[i]=sclg[t1];
				for ( j=0;j<pggg2;j++ )
				{
					t2=tsclg[j];
					tggg[i*pggg2+j]=ggg[t1*pggg1+t2];
				}
					
			}
			for ( i=0;i<(pggg2*pggg2);i++ )
					ggg[i]=tggg[i];
			
	   }while(pggg2!=0);
	   
	   fprintf(fp,"%s\n","");

//set up the dictionary
//the vector which is not compatible to others is not contained in the dictionary
	   t=0;
	   for ( i=0;i<tp1;i++ )
	   {
		   t1=tcompg[i];
		   for ( j=0;j<tm;j++ )
		   {
			   tdic[t]=fmatpat[j*wfmp+t1];
			   t++;
		   }
	   }
	   for ( j=0;j<tm;j++ )
	   {
		   k=0;
		   while ( k<tp1 )
		   {
			   if( tdic[k*tm+j]=='-') k++;
			   else
			   {
				   tdic[j]=tdic[k*tm+j];
				   break;
			   }
		   }
	   }
	   for ( i=0;i<tm;i++ )
	   {
		   if ( tdic[i]!='-')
		   {
			   dictionary[nd]=tdic[i];
		       nd++;
		   }
		   else
		   {
			   dictionary[nd]='0';
			   nd++;
		   }
	   }
   }
   fprintf(fp,"%s\n","");
   delete[]graphgg;
   delete[]ggg;
   delete[]tggg;
   delete[]ncompg;
   delete[]tcompg;
   delete[]sclg;
   delete[]tsclg;
   delete[]tdic;

//output the dictionary for checking
   fprintf(fp,"%s\n","the dictionary:");
   for ( i=0;i<fcomp;i++ )
   {
	   for ( j=0;j<tm;j++ )
		   fprintf(fp,"%c",dictionary[i*tm+j]);
	   fprintf(fp,"%s\n","");
   }
   fprintf(fp,"%s\n","");


   fprintf(fp,"%s ","the total number of the dictionary entries is:");
   fprintf(fp,"%d\n",fcomp);//the real size of the dictionary
   fprintf(fp,"%s\n","");
   cout<<"the total number of the dictionary entries is"<<fcomp<<endl;
   
//output the result
//you can select the size of the dictionary with same m many times
//because the same m is corresponding to the same dictionary 
   int fc1,total;
   char cc;
   do
   {
	   cout<<"do you want to input the size of the dictionary?(y/n):";
	   cin>>cc;
	   if ( cc!='y' )  break;
	   else
	   {
		   cout<<"please input the size of the dictionary:";
		   cin>>t;
		   if ( t>fcomp )  t=fcomp;
		   if ((log10(t)/log10(2))==int((log10(t)/log10(2))))
		       nd=int((log10(t)/log10(2)));//the length of the dictionary index
		   else  nd=int((log10(t)/log10(2)))+1;		   
		   total=0;
		   for ( i=0;i<wfmp;i++ )
		   {
			   if ( (i%l)==0 ) 
				   fprintf(fr,"%s\n","");
			   fc1=0;
			   j=0;
			   while ( j<t )
			   {
				   fcare=0;
				   k=0;
				   while ( k<tm )
				   {
					   if ((fmatpat[k*wfmp+i]!='-')&&(dictionary[j*tm+k]!='-'))
					   {
						   if (fmatpat[k*wfmp+i]==dictionary[j*tm+k])  k++;
						   else
						   {
							   fcare=1;
							   break;
						   }
					   }
					   else  k++;
				   }
				   if ( fcare==1 ) j++;
				   else
				   {
					   fprintf(fr,"%c",'1');
					   total++;
					   t2=j;
					   for ( k=(nd-1);k>=0;k-- )
					   {
						   t1=int(t2/pow(2,k));
						   fprintf(fr,"%d",t1);
						   total++;
						   t2=t2-t1*int(pow(2,k));
					   }
					   fc1=1;
					   break;
				   }

			   }
			   if (fc1==0)
			   {
				   fprintf(fr,"%c",'0');
				   total++;
				   for ( j=0;j<tm;j++ )
				   {
					   if ( fmatpat[j*wfmp+i]!='-' )
					   {
						   fprintf(fr,"%c",fmatpat[j*wfmp+i]);
					       total++;
					   }
					   else
					   {
						   fprintf(fr,"%c",'0');
						   total++;
					   }
				   }
			   }

		   }
		   fprintf(fr,"%s\n","");
		   fprintf(fp,"%s","when the size of the dictionary you select is ");
		   fprintf(fp,"%d\n",t);
		   fprintf(fp,"%s","the size of the compressed test data is ");
		   fprintf(fp,"%d\n",total);
		   fprintf(fp,"%s","the total size of the compressed test data and the dictionary is ");
		   fprintf(fp,"%d\n",total+tm*t);
		   fprintf(fp,"%s\n","");

	   }

   }while (cc=='y');
    
    fclose(fp);
	fclose(fr);
	return 0;

}