Bwt burrows-wheeler transform

Télécharger le projet
Commenter

Description

le code implémente la transformée Burrows-Wheeler (BWT) et de son inverse (IBWT).

BWT transforme un buffer source dans un buffer de destination (tout en memoire), idem pour IBWT. Le temps de conversion pour un buffer de 4096 octets reste correcte, une partie de la fonction BWT est repris du magazine login N°114.

Source / Exemple : 


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;
}

Conclusion :


restitution à l'ecran
------------------------------------------------------------------
originale: 'BWT : la transformÚe de Burrows-Wheeler' taille de 39
BWT : 'Tee:as r WB-lr dÚhelsW erafretoruwn Bom'
IWT: 'BWT : la transformÚe de Burrows-Wheeler'
Appuyez sur une touche pour continuer...
------------------------------------------------------------------

voila si vous avez des remarques, je suis preneur!
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (noaie)