ALGORITHME MTF

L'algorithme MTF est une technique de transformation utilisé dans le domaine de la compression de données. Il consiste à remplacer chaque caractère par un indice, donné par un tableau évoluant de manière dynamique. Le tableau est tout d'abord initialisé en rangeant les caractères utilisés pour la transformation:

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 second caractère à coder est un L, le tableau deviendrait :

Ainsi, lorsque des caractères identiques se suivent (par exemple en sortie de la transformée de Burrows-Wheeler BWT), le code de sortie MTF contiendra beaucoup de 0. Cette technique peut être utilisée avec une compression statistique (par exemple 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, avec la transformé MTF de "ALGOPT" on obtient la suite 0 11 7 14 15. Le tableau évoluerait comme suit :

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.