Algorithme move to front (mtf)

Télécharger le projet
Commenter

Description

voici une implémentation de la mft, cet article est la suite de mon code source sur <link rel="la BWT" href="http://www.cppfrance.com/codes/BWT-BURROWS-WHEELER-TRANSFORM_36246.aspx" />

la mtf consite a transformer une chaine de caractere, avec des caracteres a répétitions
exemple:
la phrase suivante 'BCCCBB' a transformer.
a l'intialisation on a un tableau d'index[0..255] = [0]...[A][B][C][D]...[255]
- 1er carractere 'B', on ecrit la position de B en sortie et on fait une rotation des valeurs des index.
ainsi tableau d'index[0..255] = [b][0]...[A][C][D]...[255]
- 2nd carractere 'C', on ecrit la position de C, et rotation des index.
tableau d'index[0..255] = [C][B][0]...[A][D]...[255]
- 3em carractere 'C', ecrit la position de 'C' = 0.
- 4em carractere 'C', ecrit la position de 'C' = 0.
- 5em carractere 'B', ecrit la position de 'B' = 1, rotations des index
tableau d'index [0..255] = [B][C][0]...[A][D]...[255]
- 6em carractere 'B', ecrit la position de 'C' = 0.

donc la mtf s'utlise apres la BWT, cela a pour avantage de laisser beaucoup de 0 pour la compression.

voila si vous avez des questions, des remarques, je suis preneur

Source / Exemple : 


le fichier definition.h
--------------------------------------------
#define BYTE unsigned char

le fichier mtf.h
--------------------------------------------
void mtf(BYTE *source, BYTE *destination, int sizesrc) {
   int i=0, index, pos;
   BYTE tab[256];
  
   for (index=0; index<256; index++) tab[index]=index; // initialisation du tableau d'index 

   for (i=0; i<sizesrc; i++){       // parcourt du buffer source
       if (source[i]==tab[0]) {     // la valeur courante est elle egale a l'index 0
          destination[i]=0;         // oui ecrire 0
       } else {                     // sinon 
          for(pos = 0; tab[pos] != source[i]; ++pos);                  // recherche du nouvelle l'index
          for(index=pos; index>0; index--) tab[index] = tab[index-1];  // index trouve rotation des index.
          tab[0] = source[i];
          destination[i] = pos;                                        // ecriture de l'index trouvé.
       }
   }
}

le fichier imtf.h
--------------------------------------------
void imtf(BYTE *source, BYTE *destination, int sizesrc) {
   int i=0, index, pos;
   BYTE tmp, tab[256];

   for (index=0; index<256; index++) tab[index]=index; // initialisation du tableau d'index 

   for (i=0; i<sizesrc; i++){     // parcourt du buffer a inverser.
       if (source[i]==0) {        // si s'agit de la meme valeur originale
          destination[i]=tab[0];  // ecrire cette valeur
       } else {                   // sinon
          pos = tab[source[i]];   // recherche de la nouvelle valeur
          for(index=source[i]; index>0; index--) tab[index] = tab[index-1];  // rotation des index
          tab[0] = pos;        
          destination[i] = pos;   // ecrire cette valeur
       }
   }
}

le fichier main.c
--------------------------------------------
/* --------------------------- move to front ----------------------------- */
#include <stdio.h>
#include <stdlib.h>
#include "definition.h"
#include "mtf.h"
#include "imtf.h"

int main(int argc, char *argv[]){
   BYTE *phrase="AAACACCAABBBBBB";
   BYTE *dest;
   BYTE *ori;
   
   // préparation des buffers necessaire dest et ori
   dest = (BYTE *) malloc(strlen(phrase)*sizeof(BYTE)+1); dest[strlen(phrase)]=0x0;
   ori  = (BYTE *) malloc(strlen(phrase)*sizeof(BYTE)+1); ori[strlen(phrase)] =0x0;

   // calcul de la mtf et son inverse   
   mtf(phrase, dest, strlen(phrase));
   imtf(dest,  ori,  strlen(phrase));
   
   // affichage pour comparer
   printf("phrase '%s'\n", phrase);
   printf("imtf   '%s'\n", ori);
  
   system("PAUSE");	
   return 0;
}
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)