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 generalmente 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 transformación
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:
bananaaa
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:
1
La b se mueve al principio de la lista, produciendo (bacdefghijklmnopqrstuvwxyz). La siguiente letra es a, que ahora aparece en el índice 1. Entonces agregamos un 1 al flujo de salida. Tenemos:
1,1
y volvemos a mover la letra a al principio de la lista. Continuando de esta manera, encontramos que la secuencia está codificada por:
1,1,13,1,1,1,0,0
Iteración | Secuencia | Lista |
---|---|---|
b ananaaa | 1 | (ABCDEFGHIJKLMNOPQRSTU VWXYZ) |
b a nanaaa | 1,1 | (bacdefghijklmnopqrstuvwxyz) |
ba n anaaa | 1,1,13 | (ABCDEFGHIJKLMNOPQRSTU VWXYZ) |
prohibir un naaa | 1,1,13,1 | (nabcdefghijklmopqrstuvwxyz) |
bana n aaa | 1,1,13,1,1 | (anbcdefghijklmopqrstuvwxyz) |
banan a aa | 1,1,13,1,1,1 | (nabcdefghijklmopqrstuvwxyz) |
banana a a | 1,1,13,1,1,1,0 | (anbcdefghijklmopqrstuvwxyz) |
bananaa un | 1,1,13,1,1,1,0,0 | (anbcdefghijklmopqrstuvwxyz) |
Final | 1,1,13,1,1,1,0,0 | (anbcdefghijklmopqrstuvwxyz) |
Es fácil ver que la transformación es reversible. Simplemente mantenga la misma lista y decodifique reemplazando cada índice en la secuencia codificada con la letra en ese índice en la lista. Tenga en cuenta la diferencia entre esto y el método de codificación: el índice de la lista se usa directamente en lugar de buscar cada valor para su índice.
es decir, empiezas de nuevo con (abcdefghijklmnopqrstuvwxyz). Usted toma el "1" del bloque codificado y lo busca en la lista, lo que da como resultado "b". Luego mueva la "b" al frente, lo que da como resultado (bacdef ...). Luego tome el siguiente "1", búsquelo en la lista, esto da como resultado "a", mueva la "a" al frente ... etc.
Implementación
Los detalles de la implementación son importantes para el rendimiento, especialmente para la decodificación. Para la codificación, no se obtiene ninguna ventaja clara al usar una lista enlazada , por lo que usar una matriz para almacenar la lista es aceptable, con un rendimiento en el peor de los casos O ( n k ), donde n es la longitud de los datos a codificar y k es el número de valores (generalmente una constante para una implementación dada).
El rendimiento típico es mejor porque es más probable que los símbolos de uso frecuente estén al frente y produzcan aciertos más tempranos. Esta es también la idea detrás de una lista autoorganizada de Move-to-front .
Sin embargo, para la decodificación, podemos utilizar estructuras de datos especializadas para mejorar considerablemente el rendimiento. [ ejemplo necesario ]
Pitón
Esta es una posible implementación del algoritmo de movimiento al frente en Python .
# Mtfwiki.py de tipificación de importación de lista , tupla , Unión # En lugar de transmitir siempre un diccionario "original", es más sencillo simplemente ponerse de acuerdo sobre un conjunto inicial. # Aquí usamos los 256 valores posibles de un byte: common_dictionary = list ( rango ( 256 ))def encode ( plain_text : str ) -> List [ int ]: # Cambiar a bytes para 256. plain_text = plain_text . codificar ( 'utf-8' ) # Cambiar el diccionario común es una mala idea. Hacer una copia. diccionario = common_dictionary . copiar () # Transformación compressed_text = list () # Rango de matriz regular = 0 # Leer en cada carácter para c en plain_text : rank = dictionary . index ( c ) # Encuentra el rango del carácter en el diccionario [O (k)] compressed_text . agregar ( rango ) # Actualizar el texto codificado # Actualice el diccionario [O (k)] diccionario . diccionario pop ( rango ) . insertar ( 0 , c ) return compressed_text # Devuelve el texto codificado
Lo inverso recuperará el texto original:
def decode ( compressed_data : List [ int ]) -> str : compressed_text = compressed_data dictionary = common_dictionary . copy () plain_text = [] # Lea en cada rango en el texto codificado para el rango en compressed_text : # Lea el carácter de ese rango en el diccionario plain_text . añadir ( diccionario [ rango ]) # Actualice el diccionario e = dictionary . diccionario pop ( rango ) . insertar ( 0 , e ) devuelve bytes ( texto_plano ) . decode ( 'utf-8' ) # Devuelve la cadena original
Salida de ejemplo:
>>> importar mtfwiki >>> mtfwiki . encode ( 'Wikipedia' ) [87, 105, 107, 1, 112, 104, 104, 3, 102] >>> mtfwiki . decodificar ([ 119 , 106 , 108 , 1 , 113 , 105 , 105 , 3 , 103 ]) 'wikipedia'
En este ejemplo podemos ver el código MTF aprovechando los tres repetitivos i
en la palabra de entrada. El diccionario común aquí, sin embargo, es menos que ideal, ya que se inicializa con caracteres imprimibles ASCII de uso más común después de códigos de control poco usados, en contra de la intención del diseño del código MTF de mantener lo que se usa comúnmente en el frente. Si se rota el diccionario para colocar los caracteres más usados en lugares anteriores, se puede obtener una mejor codificación:
>>> import mtfwiki >>> block32 = lambda x : [ x + i for i in range ( 32 )] >>> # Ordene los bloques ASCII: primero minúsculas, luego mayúsculas, puntuación / número, y finalmente el código de control y las cosas que no son ASCII >>> mtfwiki . common_dictionary = block32 ( 0x60 ) + block32 ( 0x40 ) + block32 ( 0x20 ) + block32 ( 0x00 ) + lista ( rango ( 128 , 256 )) >>> mtfwiki . codificar ( 'Wikipedia' ) [55, 10, 12, 1, 17, 9, 9, 3, 7]
Uso en algoritmos prácticos de compresión de datos
La transformada MTF aprovecha la correlación local de frecuencias para reducir la entropía de un mensaje. [ aclaración necesaria ] De hecho, las letras usadas recientemente permanecen al principio de la lista; si el uso de letras exhibe correlaciones locales, esto dará como resultado una gran cantidad de números pequeños como "0" y "1" en la salida.
Sin embargo, no todos los datos exhiben este tipo de correlación local y, para algunos mensajes, la transformación MTF puede aumentar la entropía.
Un uso importante de la transformada MTF es la compresión basada en la transformada de Burrows-Wheeler . La transformada de Burrows-Wheeler es muy buena para producir una secuencia que exhibe una correlación de frecuencia local a partir del texto y otras clases especiales de datos. La compresión se beneficia enormemente del seguimiento de la transformada de Burrows-Wheeler con una transformada MTF antes del paso final de codificación de entropía.
Ejemplo
Como ejemplo, imagina que deseamos comprimir el soliloquio de Hamlet ( Ser o no ser ... ). Podemos calcular el tamaño de este mensaje en 7033 bits. Ingenuamente, podríamos intentar aplicar la transformación MTF directamente. El resultado es un mensaje con 7807 bits (más alto que el original). La razón es que el texto en inglés no presenta, en general, un alto nivel de correlación de frecuencias locales. Sin embargo, si primero aplicamos la transformada de Burrows-Wheeler y luego la transformada MTF, obtenemos un mensaje con 6187 bits. Tenga en cuenta que la transformación de Burrows-Wheeler no disminuye la entropía del mensaje; solo reordena los bytes de una manera que hace que la transformación MTF sea más efectiva.
Un problema con la transformación MTF básica es que realiza los mismos cambios para cualquier carácter, independientemente de la frecuencia, lo que puede resultar en una compresión disminuida ya que los caracteres que ocurren raramente pueden empujar a los caracteres frecuentes a valores más altos. Por este motivo se han desarrollado diversas alteraciones y alternativas. Un cambio común es hacer que los caracteres por encima de cierto punto solo se puedan mover a un cierto umbral. Otra es hacer algún algoritmo que ejecute un recuento de la frecuencia local de cada personaje y use estos valores para elegir el orden de los caracteres en cualquier momento. Muchas de estas transformaciones aún reservan cero para los caracteres repetidos, ya que a menudo son los más comunes en los datos después de la Transformada de Burrows Wheeler.
Mover al frente de la lista vinculada
- El término Move To Front (MTF) también se utiliza en un contexto ligeramente diferente, como un tipo de lista enlazada dinámica . En una lista MTF, cada elemento se mueve al frente cuando se accede a él. [4] Esto asegura que, con el tiempo, los elementos a los que se accede con mayor frecuencia sean más fáciles de acceder.
Referencias
- ^ Ryabko, B. Ya Compresión de datos por medio de una "pila de libros", Problemas de transmisión de información, 1980, v. 16: (4), págs. 265-269
- ^ JL Bentley; DD Sleator; RE Tarjan; VK Wei (1986). "Un esquema de compresión de datos adaptativo localmente" . Comunicaciones de la ACM . 29 (4): 320–330. CiteSeerX 10.1.1.69.807 . doi : 10.1145 / 5684.5688 .
- ^ Ryabko, B. Ya .; Horspool, R. Nigel; Cormack, Gordon V. (1987). "Comentarios para:" Un esquema de compresión de datos adaptable localmente "por JL Bentley, DD Sleator, RE Tarjan y VK Wei". Comm. ACM . 30 (9): 792–794. doi : 10.1145 / 30401.315747 .
- ^ Rivest, R. (1976). "Sobre heurística de búsqueda secuencial autoorganizada". Comunicaciones de la ACM . 19 (2): 63–67. doi : 10.1145 / 359997.360000 .