Bwt burrows-wheeler transform

Soyez le premier à donner votre avis sur cette source.

Vue 6 994 fois - Téléchargée 371 fois

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!

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

cs_Matt67
Messages postés
554
Date d'inscription
samedi 6 septembre 2003
Statut
Membre
Dernière intervention
6 mars 2010
-
Bonjour,

euh, à quoi ca sert ???

Matt...
noaie
Messages postés
5
Date d'inscription
samedi 25 février 2006
Statut
Membre
Dernière intervention
18 septembre 2011
-
Bonjour Matth67,

voici un exemple plus long (extrait de victor hugo, les misérables) qui montre l'utilité de la BWT, a savoir la compression de données sans perte. Cette transformée ne diminue pas la taille des données, mais elle améloire la compression aprés.

originale:

'Javert pencha la tete et regarda. Tout etait noir. On ne distinguait rien. On entendait un bruit d'ecume ; mais on ne voyait pas la riviere. Par instants, dans cette profondeur vertigineuse, une lueur apparaissait et serpentaitvaguement, l'eau ayant cette puissance, dans la nuit la plus complete, de prendre la lumiere on ne sait ou et de la changer en couleuvre. La lueur s'evanouissait, et tout redevenait indistinct. L'immensite semblait ouverte la. Ce qu'on avait au-dessous de soi, ce n'etait pas de l'eau, c'etait du gouffre. Le mur du quai, abrupt, confus, mele a la vapeur, tout de suite derobe, faisait l'effet d'un escarpement de l'infini.' taille de 651

BWT :

'e........e,rtnun,,stas,ntt,,stt,steetrrnnuet,t,utr,eteeestsaaeeaa;,eennntaestttttaeeeeutttareeteea,tt,tarelldlcnsLludiuitseetetsreuateenreai . lh Lllllllld vumfrvtsnstsltyudtsshvddytv Ppgcppee J om a s n n ne rn -nen n mltntdddrtnLcrdttCntddnctbsrrr'''r'rmspu ivptrmmmp giidsvvv df ' 'tlccuudpnl'd feunofneni naccaonrmvt'tg'tf oaaauuddauaaaauaaaaaaaaausr bepu p eu meeuio oueOuOoo eeaeieoie u iioaii aaaeiaeeeea rrsnc' fc gncstTt vp r ram a u uueauuuiaadevfe p epaeeeebbnuaunai tusi sseu n siiienii inieneuiiuiiiiiiiirueieeiipinceeensierttien rss neeaoddqaaqggllooprnsocl ' remeeelofeooooe ae eau i uoa'

ici on voie clairement l'utilité de l'agorithme, il regroupe les lettres identiques, ce qui améloire la compression. son éfficacité augmente avec la taille des données à codé en entrée

cf ce lien http://fr.wikipedia.org/wiki/BWT , cet algorithme est utilisé dans la compression bzip2.

Merci de ta question.

NoAiE.
psycho81
Messages postés
88
Date d'inscription
mardi 4 mai 2004
Statut
Membre
Dernière intervention
17 février 2008
-
A quand le MTF (Move To Front) ?
pour des informations complémentaire à ce sujet (et une approche légèrement différente) regarde mes sources (en VB par contre ... désolé)

je tiens à signaler pour les visiteurs venant ici, qu'à l'ehure actuelle, les meilleure compression texte sont réalisé avec comme base de BWT. Le meilleur étant selon moi comrpessia (ou compcl.exe). Contactez moi pour disposer du module dos compcl.exe. Il est surpuissant !

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.