La transformación de movimiento al frente (MTF) es una codificación de datos (normalmente un flujo de bytes ) diseñada para mejorar el rendimiento de las técnicas de compresión de codificación de entropía . Cuando se implementa de manera eficiente, es lo suficientemente rápido como para que sus beneficios usualmente justifiquen su inclusión como un paso adicional en el algoritmo de compresión de datos .
Este algoritmo fue publicado por primera vez por B. Ryabko bajo el nombre de "pila de libros" en 1980. [1] Posteriormente, fue redescubierto por JK Bentley et. Alabama. en 1986, [2] como consta en la nota explicativa. [3]
La idea principal es que cada símbolo en los datos sea reemplazado por su índice en la pila de "símbolos usados recientemente". Por ejemplo, las secuencias largas de símbolos idénticos se reemplazan por tantos ceros, mientras que cuando aparece un símbolo que no se ha utilizado durante mucho tiempo, se reemplaza por un número grande. Así, al final, los datos se transforman en una secuencia de números enteros; si los datos muestran muchas correlaciones locales, entonces estos números enteros tienden a ser pequeños.
Démosle una descripción precisa. Suponga por simplicidad que los símbolos en los datos son bytes . Cada valor de byte está codificado por su índice en una lista de bytes, que cambia a lo largo del algoritmo. La lista está inicialmente ordenada por valor de byte (0, 1, 2, 3, ..., 255). Por lo tanto, el primer byte siempre está codificado por su propio valor. Sin embargo, después de codificar un byte, ese valor se mueve al principio de la lista antes de continuar con el siguiente byte.
Un ejemplo arrojará algo de luz sobre cómo funciona la transformación. Imagine que en lugar de bytes, estamos codificando valores en a – z. Deseamos transformar la siguiente secuencia:
Por convención, la lista es inicialmente (abcdefghijklmnopqrstuvwxyz). La primera letra de la secuencia es b, que aparece en el índice 1 (la lista está indexada de 0 a 25). Ponemos un 1 al flujo de salida: