相容+fdr.txt

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

本程序代码主要包括以下几个模块：
1.将原测试集转化成多扫描链结构的形式；
2.相容压缩；
3.将按多扫描链结构的形式排列的测试集还原；
4.优化排序；
5.异或运算，生成差分向量；
6.按照FDR码的编码规则进行编码压缩。

#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++)