BWT BURROWS-WHEELER TRANSFORM

le fichier definition.h
--------------------------------------------
#define BYTE  unsigned char       
#define WORD  unsigned short int 
#define DWORD unsigned long int


le fichier bwt.h
--------------------------------------------
int BWT(BYTE *source, BYTE *destination, int sizesrc){
   int  i=0, index;
   int  *ordre;
       
   static int compare (const void *a, const void *b){
      int i, j, n, t;
      i = * (int *) a;
      j = * (int *) b;
      n = sizesrc;
      while(n--) {
         t = source[i]-source[j]; // diff entre car(i) et car(j)
         if (t) return t;
         i = (i+1) % sizesrc;     // prochain car i
         j = (j+1) % sizesrc;     // ...          j
      }
      return 0;
   }

   ordre = (int *) malloc(sizeof(int)*sizesrc);
   if (!ordre) return -1;
   
   do {
      ordre[i]=i++;
   } while (i<sizesrc);
       
   qsort((void*) ordre, sizesrc, sizeof(int), compare);
       
   for (i=0; i<sizesrc; i++) {
      if (ordre[i]==0) {
         index = i;
         destination[i] = source[sizesrc-1]; 
      } else {
         destination[i] = source[ordre[i]-1];
      }
   }
       
   free(ordre);
   return index;
}


le fichier ibwt.h
--------------------------------------------
void IBWT(int sizesrc, int posori, BYTE *source, BYTE *destination){
   typedef struct {
      BYTE f;
      int  nd, nf;
   } IBWT_ELT;

   IBWT_ELT *p;

   int  i, tmp_pos, ind, index[255];  
   int  compteur_d[256], compteur_f[255];
   BYTE tmp;

   static int compare (const void *a, const void *b){
      int i, j;
      i = * (BYTE *) a;
      j = * (BYTE *) b;
      return i-j; 
   }
   
   // --- initialisation ---  
   p = (IBWT_ELT *) malloc(sizesrc * sizeof(IBWT_ELT));

   // copy la transformé pour trier les éléments a remplacer par Memcopy
   memcpy(destination, source, sizesrc);

   // trie les données sources
   qsort((void*) destination, sizesrc, sizeof(BYTE), compare);
 
   // affectation des p[].d et P[].f
   for (i=0; i<=255; i++) { compteur_d[i]=0; compteur_f[i]=0;}
   
   for (i=0; i<sizesrc; i++) {
      tmp     = destination[i];
      p[i].f  = source[i];
      if (compteur_d[tmp]==0) index[tmp]=i;
      p[i].nd = compteur_d[tmp]++;
      p[i].nf = compteur_f[source[i]]++;
   }

   // calcule de l'inverse  
   i       = (sizesrc-1);
   tmp_pos = posori;
   while (i>=0) {
      tmp              = p[tmp_pos].f;
      ind              = p[tmp_pos].nf;
	  tmp_pos          = index[tmp]+ind;
      destination[i--] = tmp;
   };
}


le fichier main.c
--------------------------------------------
#include <stdio.h>
#include <stdlib.h>
#include "definition.h"
#include "bwt.h"
#include "ibwt.h"

 
int main(int argc, char *argv[]){
  BYTE *p = "BWT : la transformée de Burrows-Wheeler";
  BYTE *t, *i;
  int  s, pos;
  
  t = (BYTE *) malloc( sizeof(BYTE) * strlen(p)+1); t[strlen(p)]=0x0;
  i = (BYTE *) malloc( sizeof(BYTE) * strlen(p)+1); i[strlen(p)]=0x0;

  pos = BWT((BYTE *)p, t, strlen(p));
  IBWT(strlen(p),pos, t, i);

  printf("originale: '%s'  taille de %d\n", p, strlen(p));
  printf("BWT :      '%s'\n", t);
  printf("IWT:       '%s'\n", i);
   
  system("PAUSE");	
  return 0;
}