> mtf | move | front <
// Move-to-Front - Reordenamiento dinámico de listas para mejor compresión
Auto-adaptativo
Se adapta automáticamente a los patrones locales de los datos.
Aprovecha la localidad
Los símbolos recientes reciben índices más pequeños para mejorar la compresión.
Parte de bzip2
Se utiliza después de la BWT en la tubería de compresión de bzip2.
>> información técnica
Cómo funciona MTF:
MTF mantiene una lista de todos los símbolos posibles. Al codificar un símbolo, se emite su posición actual en la lista y luego se mueve a la parte frontal. Esto hace que los símbolos usados recientemente tengan índices pequeños, lo que se comprime mejor con la codificación de entropía posterior.
Ejemplo de codificación:
Texto: "banana" Lista inicial: [a,b,c,d,...] "b": índice 1, mover b→frente [b,a,c,d,...] "a": índice 1, mover a→frente [a,b,c,d,...] "n": índice 13, mover n→frente [n,a,b,c,...] "a": índice 1, mover a→frente [a,n,b,c,...] "n": índice 1, mover n→frente [n,a,b,c,...] "a": índice 1, mover a→frente [a,n,b,c,...] Salida: [1,1,13,1,1,1]
Por qué usar MTF:
- >Mejora la redundancia local
- >Funciona junto con BWT
- >Implementación sencilla
- >Transformación reversible
- >Se adapta a los patrones
>> preguntas frecuentes
¿Qué es la codificación Move-to-Front?
MTF es un algoritmo de transformación de datos que codifica cada símbolo como su índice en una lista actualizada dinámicamente. Después de codificar cada símbolo, se mueve al frente de la lista, de modo que los símbolos frecuentes obtienen índices más pequeños.
¿Por qué usar MTF junto con BWT?
BWT agrupa contextos similares y crea repeticiones locales. MTF transforma esas repeticiones en números pequeños (muchos 0 y 1), que se comprimen muy bien con codificación por longitud de corrida o codificación de Huffman.
¿Cómo funciona la lista?
La lista empieza con los 256 valores de byte posibles en orden. A medida que se codifican símbolos, los usados se mueven al frente. Los símbolos usados recientemente permanecen cerca del frente con índices pequeños, mientras que los no usados se desplazan hacia índices más grandes.
¿MTF frente a otras transformaciones?
MTF está diseñado específicamente para usarse después de BWT. No es muy eficaz por sí solo, pero es excelente para convertir la salida de BWT en una forma que se comprime bien. Es más sencillo que la codificación aritmética, pero menos óptimo.