Move-To-Front


Move-To-Front

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

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.


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Move-To-Front de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Move-To-Front — (englisch „Nach vorne verschieben“) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows Wheeler Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Move-to-Front — (englisch „Nach vorne verschieben“) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows Wheeler Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Move To Front — (englisch „Nach vorne verschieben“) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows Wheeler Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu können. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

  • Move to front — (englisch „Nach vorne verschieben“, auch: Rotierende Kodierung) ist ein Kodierungsverfahren, das sich gut eignet, um Daten, die aus der Burrows Wheeler Transformation stammen, weiterzuverarbeiten, um sie anschließend effektiver komprimieren zu… …   Deutsch Wikipedia

  • Move-to-front — 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é… …   Wikipédia en Français

  • Move to Front — 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é… …   Wikipédia en Français

  • Move-To-Front — Движение к началу (англ. move to front, MTF)  преобразование для кодирования данных (обычно потока байтов), разработанное для улучшения производительности энтропийного кодирования. При хорошей реализации, оно достаточно быстро для… …   Википедия

  • Move-to-front transform — The move to front transform (or MTF) is an encoding of data (typically a stream of bytes) designed to improve the performance of entropy encoding techniques of compression. When efficiently implemented, it is fast enough that its benefits usually …   Wikipedia

  • Move-to-front heuristic — …   Википедия

  • Front loop — is the name given to a trick performed by a windsurfer (also known as a forward loop) whereby the rider performs a jump from a wave face and forces the sail, board and rider to perform a forward somersault in one motion. In its basic form, the… …   Wikipedia