golomb_compress.txt

一种基于多扫描链相容 压缩的 Golomb 码的压缩方法。这种方法首先把原始测试集的测试向量转变成多扫 描链的形式

本程序代码主要包括以下几个模块： 
1.将原测试集转化成多扫描链结构的形式； 
2.相容压缩； 
3.将按多扫描链结构的形式排列的测试集还原； 
4.优化排序； 
5.异或运算，生成差分向量； 
6.按照Golomb 码的编码规则进行编码压缩。 
 
#include <iostream> 
#include <stdlib.h> 
#include <stdio.h> 
#include <math.h> 
#include <vector> 
#include <iomanip> 
 
using namespace std; 
 
//----------------transfer the pattern to multiscan chains-------------------------- 
void transferpattern(char *pt,vector<char>& trpt,int m,int width,int nrow) 
{ 
  int q=0,i,j,k,p,d; 
  int wf;  
  if(width%m==0) 
 { 
    d=width/m; 
    wf=d*nrow; 
    for(i=0;i<nrow;i++) 
  { 
   for(j=0;j<m;j++) 
    for(k=0;k<d;k++) 
    { 
     trpt[j*wf+i*d+k]=pt[q]; 
     q++; 
    } 
  } 
 } 
  else                    //need to fill with the don't care 
 { 
    d=width/m+1;                                
    wf=d*nrow; 
    p=width/d; 
        for (i=0;i<nrow;i++) 
  { 
   for(j=0;j<p;j++) 
    for(k=0;k<d;k++) 
    { 
     trpt[j*wf+i*d+k]=pt[q]; 
     q++; 
    }                       
    for(k=0;k<width-d*p;k++)        
    { 
     trpt[j*wf+i*d+k]=pt[q]; 
        q++; 
    } 
for(k=width-d*p;k<d;k++)        //fill the (p+1)th row remaining bits with 
//the don't care 
    trpt[j*wf+i*d+k]='-'; 
         for ( j=p+1;j<m;j++ )    //while width%m>d,fill m-(p+1)  rows with don't care 
       for ( k=0;k<d;k++ ) 
     trpt[j*wf+(k+i*d)]='-'; 
   
  } 
 } 
 
} 
//-------------------------compatible compession--------------------------------- 
 
// firstly, set the compatible graph 
 
int setgraph(vector<vector<int> >& graph,vector<char>& trpt,int wf,int m) 
{ 
  int i,j,k; 
  int iscompatible;       //if the test sets are compatible iscompatible=1 
  int t=0;                //the number of the compatible relation 
  for(i=0;i<m;i++) 
 { 
    for(j=0;j<m;j++) 
  { 
   iscompatible=1; 
   k=0; 
   while (k<wf) 
   {                             
    if((trpt[i*wf+k]!='-')&&(trpt[j*wf+k]!='-')) 
    { 
     if(trpt[i*wf+k]!=trpt[j*wf+k]) 
     { 
      iscompatible=0; 
      break; 
     } 
     else 
      k++; 
    } 
    else 
     k++; 
   }//while 
   if((iscompatible==1)&&(i!=j)) 
   { 
    graph[i][j]=1; 
    t++; 
   } 
  } 
 } 
  return t; 
} 
 
//secondly, find the compatible cliques     
 
int compatibleclique(FILE *fo,vector<vector<int> >& graph,vector<int>& comp,int m,int 
tol) 
{  
  vector<vector<int> > gg;               //G' 
    vector<vector<int> > subg;             //subgraph               
  vector<int> degree(m);                  //the degree of every vertex  
  int dmax;                                             
  vector<int> ver(m);                  //save the initial position                    
  vector<int> vver(m); 
  int i,j,k,r1,r2,r3,s,t; 
int count=0;               //count the compatible cliques in which the number of the 
// vertexes is ">1" ,not including independent vertexes              
  for(i=0;i<m;i++)                       //assign the space for gg 
    { 
     vector<int> temp; 
     for(j=0;j<m;j++) 
         { 
    temp.insert(temp.end(),0);                                
     } 
     gg.insert(gg.end(),temp); 
 } 
  for(i=0;i<m;i++) 
 { 
    vector<int> temp; 
    for(j=0;j<m;j++) 
  { 
   temp.insert(temp.end(),0); 
  } 
    subg.insert(subg.end(),temp); 
 } 
 
    while (tol!=0)                       //wether there are compatible vectors in G   
 { 
    for(i=0;i<m;i++)                 // copy the graph to the G' 
   for(j=0;j<m;j++) 
    gg[i][j]=graph[i][j];   
    count++;                            
    for(i=0;i<m;i++) 
   ver[i]=i; 
  r1=m;  
    do 
    {         
   for(i=0;i<r1;i++)                
    degree[i]=0; 
   for(i=0;i<r1;i++)               
    for(j=0;j<r1;j++) 
    { 
     if(gg[i][j]==1) 
      degree[i]++; 
    } 
   dmax=0;   
   k=degree[0]; 
   for(i=1;i<r1;i++)              //figure the vertex with the max degree 
   { 
    if (k<degree[i]) 
    { 
     k=degree[i]; 
     dmax=i; 
    } 
   } 
   t=ver[dmax];                             
   comp[t]=count;         //the vertexes in the same clique have the same value
    
   for (i=0;i<m;i++)             
   { 
    if (graph[i][t]==1) 
    { 
     graph[i][t]=0;  
     tol--; 
    } 
    if (graph[t][i]==1)  
    { 
     graph[t][i]=0; 
     tol--; 
    } 
   } 
   s=r1; 
   r1=0;              
   for(i=0;i<s;i++) 
   { 
    if(gg[dmax][i]==1) 
    { 
     vver[r1]=i; 
     r1++; 
    } 
   } 
   for(i=0;i<r1;i++) 
   { 
    r2=vver[i]; 
    ver[i]=ver[r2];               
    for(j=0;j<r1;j++) 
    { 
     r3=vver[j]; 
     subg[i][j]=gg[r2][r3]; 
    } 
   } 
   for(i=0;i<r1;i++)                   //copy the subgraph to G' 
    for(j=0;j<r1;j++) 
     gg[i][j]=subg[i][j]; 
   
    }while (r1!=0); 
  }//while 
 
    return count;                                
  gg.clear(); 
  subg.clear(); 
  ver.clear(); 
  vver.clear(); 
  degree.clear (); 
} 
 
//thirdly,combine the compatible vectors to reduce the vector 
 
int combination(vector<int>& comp,vector<char>& trpt,int wf,int m,int cliq) 
{ 
  int i,j,k,s,a,b,r; 
  vector<vector<char> > comp1; 
  vector<int> comp2(m); 
  vector<vector<char> > comp3; 
  int *arr=new int[m]; 
 
  for(i=0;i<m;i++) 
     { 
     vector<char> temp; 
     for(j=0;j<wf;j++) 
         { 
    temp.insert(temp.end(),'0'); 
     } 
     comp1.insert(comp1.end(),temp); 
   } 
   for(i=1;i<=m;i++) 
     { 
     vector<char> temp; 
     for(j=0;j<wf;j++) 
         { 
    temp.insert(temp.end(),'0'); 
     } 
     comp3.insert(comp3.end(),temp); 
   } 
   for(i=0;i<m;i++) 
     arr[i]=0; 
 
  for(i=1;i<=cliq;i++) 
 { 
    s=0;          //the number of the vectors in every compatible clique  
  a=0; 
    for(j=0;j<m;j++)                             
  { 
   if(comp[j]==i) 
   { 
    arr[j]=1; 
    b=0; 
    for(k=0;k<wf;k++) 
    { 
     comp1[a][b]=trpt[j*wf+k]; 
     b++; 
    } 
    comp2[s]=j; 
    s++; 
    a++; 
   }   
  } 
    for(j=0;j<wf;j++)                          //combine the test vectors 
  { 
   k=0;                                 //the comparation during  the  rows(列) 
   while (k<s) 
   { 
    if ((comp1[k][j]=='-')&&(k==s-1)) 
     comp3[i][j]='-'; 
    if (comp1[k][j]=='-') 
     k++; 
       else 
    { 
     comp3[i][j]=comp1[k][j]; 
     break; 
    } 
    
   } 
  } 
  }//for  
 
  r=cliq; 
  for(i=0;i<m;i++) 
 { 
    if(arr[i]==0) 
  { 
   r++; 
   for(k=0;k<wf;k++) 
    comp3[r][k]=trpt[i*wf+k]; 
   arr[i]=1;                                
  } 
 } 
     
  k=0; 
  for(i=1;i<=r;i++) 
 { 
    for(j=0;j<wf;j++) 
            trpt[k*wf+j]=comp3[i][j]; 
        k++; 
    } 
  return k; 
 
  delete[] arr; 
  comp1.clear(); 
  comp3.clear(); 
} 
 
int compatipression(FILE *fo,vector<char>& trpt,int wf,int m) 
{ 
   vector<vector<int> > graph;       //  compatible matrix G 
   vector<int> comp(m); 
   int sum;  
   int cliq; 
   int t; 
   for(int i=0;i<m;i++) 
     { 
     vector<int> temp; 
     for(int j=0;j<m;j++) 
         { 
    temp.insert(temp.end(),0); 
     } 
     graph.insert(graph.end(),temp); 
   } 
     t=setgraph(graph,trpt,wf,m); 
   cliq=compatibleclique(fo,graph,comp,m,t);     
   sum=combination(comp,trpt,wf,m,cliq); 
 
  return sum; 
 
  comp.clear(); 
  graph.clear(); 
} 
//-------------------output the first compression vectors---------------------------                             
 
void compatioutput (FILE *fr,vector<char>& trpt,int m,int wf) 
{ 
  int i,j; 
  for(i=0;i<m;i++) 
 { 
    for(j=0;j<wf;j++) 
   fprintf(fr,"%c",trpt[i*wf+j]); 
    fprintf(fr,"%s\n",""); 
 } 
}   
//-----------reset the test vectors after the first compression------------------ 
void reset(vector<char>& trpt,int wf,int sum) 
{   
  vector<int> temp(wf*sum); 
  int i,j; 
  for(i=0;i<wf;i++) 
    for(j=0;j<sum;j++) 
   temp[i*sum+j]=trpt[j*wf+i]; 
  for(i=0;i<wf*sum;i++)