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