Move-To-Front

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

L'algorithme MTF (pour Move to Front, déplacer vers l'avant) est un système de transformation de flot utilisé notamment dans le domaine de la compression de données en informatique. Il consiste à remplacer chaque caractère par un indice, donné par un tableau évoluant de manière dynamique. Cette technique est notamment utilisable en conjonction avec la transformée de Burrows-Wheeler.

Fonctionnement[modifier | modifier le code]

Le tableau est tout d'abord initialisé en rangeant les caractères utilisés pour le codage comme ceci :

Indice 0 1 2 3 4 5 6 25
Caractère A B C D E F G Z

Lorsqu'un caractère est lu, son indice est émis, puis ce caractère est placé en première position et tous les autres caractères décalés (d'où le nom de Move to Front). Par exemple si le premier caractère à coder est un E, le tableau deviendrait :

Indice 0 1 2 3 4 5 6 25
Caractère E A B C D F G Z

Ainsi, lorsque des caractères semblables se suivent (cas de la transformée de Burrows-Wheeler), le flux émis contiendra beaucoup de 0, ce qui dans une compression statistique (type codage de Huffman) augmentera considérablement le Taux de compression de données. Dans ce cas, l'émission d'un 0 laisse le tableau identique, alors que dans les autres cas, le réarrangement ne concerne que les premiers éléments du tableau.

Par exemple, la séquence EEEEEA serait transformée en la suite 400001 ; le tableau évoluerait comme suit :

Indice 0 1 2 3 4 5 6 25
État initial A B C D E F G Z
Tableau modifié par le premier E E A B C D F G Z
Tableau conservé 4 fois par les 4 E suivants
Tableau modifié par le A A E B C D F G Z

Le décodage est tout aussi simple : à partir du même tableau initial, il suffit d'émettre le caractère correspondant à l'indice et de ranger le tableau en passant ce caractère en premier. Le tableau évolue exactement comme pendant la phase de codage.

Mise en œuvre[modifier | modifier le code]

Python[modifier | modifier le code]

Voici une mise en œuvre possible de l'algorithme Move to Front en Python.

def MtF(texte):
	# Initialiser la liste des caractères présents (i.e. le dictionnaire)
	liste = list();
	# Lire chaque caractère
	for i in range(len(texte)):
		# Si le caractère n'est pas déjà dans le dictionnaire, l'ajouter
		if texte[i] not in liste:
			liste.append(str(texte[i]));
	# Trier le dictionnaire
	liste.sort();
	# Transformation #
	mot_code = list();
	rang = 0;
	# Lire chaque caractère
	for i in range(0,len(texte)):
		rang = liste.index(str(texte[i])); # Récupérer le rang du caractère dans le dictionnaire
		mot_code += [str(rang)]; # Mettre à jour le mot codé
		# Mettre à jour le dictionnaire
		liste.pop(rang);
		liste.insert(0, texte[i]);
 
	liste.sort(); # Trier le dictionnaire
 
	return [mot_code,liste]; # Retourne le mot code ainsi que le dico

Après avoir transformé le texte, voici désormais une mise en oeuvre possible de l'algorithme Move to Front inversé qui permet de retrouver le texte d'origine.

def iMtF(compressee):
	# Initialiser les variables
	mot_code = compressee[0];
	liste = list(compressee[1]);
 
	texte = "";
	rang = 0;
	# Lire chaque caractère du mot codé
	for i in mot_code:
		# Récupérer le rang du caractère dans le dictionnaire
		rang = int(i)
		texte = texte + str(liste[rang])
 
		# Mettre à jour le dictionnaire
		e = liste[int(i)];
		liste.pop(int(i));
		liste.insert(0, e);
 
	return texte; # Retourner le texte d'origine