Admin
Admin
Nombre de messages : 138
Age : 38
Date d'inscription : 02/09/2006
 |  Sujet: ALGORITHME MOVE TO FRONT (MTF) Mer 13 Sep - 5:26 | |
| 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. - Code:
-
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;
}
| |
|
