Transformación de movimiento al frente

La transformación de desplazamiento al frente (MTF, por sus siglas en inglés) es una codificación de datos (normalmente una secuencia de bytes ) diseñada para mejorar el rendimiento de las técnicas de compresión basadas en la codificación entrópica . Cuando se implementa de forma eficiente, es lo suficientemente rápida como para que sus ventajas justifiquen su inclusión como un paso adicional en el algoritmo de compresión de datos .

Este algoritmo fue publicado por primera vez por Boris Ryabko con el nombre de "pila de libros" en 1980. ^{[ 1 ]} Posteriormente, fue redescubierto por JK Bentley et al. en 1986, ^{[ 2 ]} como se atestigua en la nota explicativa. ^{[ 3 ]}

La idea principal es que cada símbolo de los datos se reemplaza por su índice en la pila de "símbolos usados ​​recientemente". Por ejemplo, las secuencias largas de símbolos idénticos se reemplazan por la misma cantidad de ceros, mientras que cuando aparece un símbolo que no se ha usado en mucho tiempo, se reemplaza por un número grande. De esta manera, al final, los datos se transforman en una secuencia de enteros; si los datos presentan muchas correlaciones locales, estos enteros tienden a ser pequeños.

Procedamos a dar una descripción precisa. Supongamos, para simplificar, que los símbolos en los datos son bytes . Cada valor de byte se codifica mediante 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 se codifica con 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 aclarará cómo funciona la transformación. Imaginemos que, en lugar de bytes, codificamos valores en letras de la a a la z. Queremos 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 del 0 al 25). Añadimos un 1 al flujo de salida:

1

La letra 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 movemos la letra a de nuevo al principio de la lista. Siguiendo este procedimiento, encontramos que la secuencia está codificada por:

1,1,13,1,1,1,0,0

Es fácil ver que la transformación es reversible. Simplemente se mantiene la misma lista y se decodifica reemplazando cada índice en la secuencia codificada con la letra correspondiente a ese índice en la lista. Nótese la diferencia con el método de codificación: se utiliza directamente el índice de la lista en lugar de buscar el índice de cada valor.

Es decir, comienzas de nuevo con (abcdefghijklmnopqrstuvwxyz). Tomas el "1" del bloque codificado y lo buscas en la lista, lo que resulta en "b". Luego mueves el "b" al principio, lo que resulta en (bacdef...). Luego tomas el siguiente "1", lo buscas en la lista, esto resulta en "a", mueves el "a" al principio... etc.

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 un arreglo para almacenar la lista es aceptable, con un rendimiento en el peor de los casos de 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 los símbolos de uso frecuente tienen más probabilidades de estar al frente y producirán resultados más rápidos. Esta es también la idea detrás de una lista autoorganizada de "mover al frente" .

Sin embargo, para la decodificación, podemos utilizar estructuras de datos especializadas para mejorar considerablemente el rendimiento.

from collections.abc import Generator , Iterableclase MoveToFront : """  >>> mtf = MoveToFront()  >>> list(mtf.encode("Wikipedia"))  [87, 105, 107, 1, 112, 104, 104, 3, 102]  >>> mtf.decode([87, 105, 107, 1, 112, 104, 104, 3, 102])  'Wikipedia'  >>> list(mtf.encode("wikipedia"))  [119, 106, 108, 1, 113, 105, 105, 3, 103]  >>> mtf.decode([119, 106, 108, 1, 113, 105, 105, 3, 103])  'wikipedia'  """ def __init__ ( self , common_dictionary : Iterable [ int ] = range ( 256 )): """  En lugar de transmitir siempre un diccionario "original",  es más sencillo acordar un conjunto inicial.  Aquí usamos los 256 valores posibles de un byte.  """ # consumimos el iterable para que pueda usarse varias veces self . common_dictionary = list ( common_dictionary )def encode ( self , plain_text : str ) -> Generator [ int ] : # Modificar el diccionario común es una mala idea. Haz una copia . dictionary = list ( self.common_dictionary )# Leer cada carácter para c en plain_text.encode ( " latin - 1" ): # Convertir a bytes para 256. # Encontrar el rango del carácter en el diccionario [O(k)] rango = diccionario.index ( c ) # el carácter codificado produce rango# Actualizar el diccionario [Θ ( k ) para insertar] diccionario.pop ( rank ) diccionario.insertar ( 0 , c )def decode ( self , compressed_data : Iterable [ int ]) -> str : """ Función  inversa que recupera el texto original  """ dictionary = list ( self.common_dictionary ) plain_text = [ ]# Lee cada rango en el texto codificado para cada rango en compressed_data : # Elimina el carácter de ese rango del diccionario e = dictionary.pop ( rank ) plain_text.append ( e )# Inserta el carácter al principio del diccionario . diccionario.insertar ( 0 , e )return bytes ( plain_text ) . decode ( "latin-1" ) # Devuelve la cadena original

desde itertools importar cadenadef block32 ( x ): return range ( x , x + 32 )clase MoveToFrontMoreCommon ( MoveToFront ): """  >>> mtf = MoveToFrontMoreCommon()  >>> list(mtf.encode("Wikipedia"))  [55, 10, 12, 1, 17, 9, 9, 3, 7]  """ def __init__ ( self ): super () . __init__ ( chain ( # Ordenar los bloques ASCII: block32 ( ord ( "a" ) - 1 ), # primero minúsculas, block32 ( ord ( "A" ) - 1 ), # luego mayúsculas, block32 ( ord ( "!" ) - 1 ), # puntuación/número, block32 ( 0 ), # códigos de control, range ( 128 , 256 ), # y finalmente lo que no es ASCII ) )if __name__ == " __main__" : import doctest doctest.testmod ( )

La transformada MTF aprovecha la correlación local de frecuencias para reducir la entropía de un mensaje. De hecho, las letras usadas recientemente permanecen al principio de la lista; si el uso de letras presenta 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 presentan este tipo de correlación local, y para algunos mensajes, la transformación MTF puede incluso aumentar la entropía.

Una aplicación importante de la transformada MTF se encuentra en la compresión basada en la transformada de Burrows-Wheeler . Esta transformada es muy eficaz para generar una secuencia que muestra correlación de frecuencia local en texto y otras clases especiales de datos. La compresión se beneficia enormemente al aplicar una transformada MTF después de la transformada de Burrows-Wheeler, antes del paso final de codificación de entropía.

• El término Mover al frente (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 garantiza que, con el tiempo, los elementos a los que se accede con mayor frecuencia sean más fáciles de acceder.

• "Pasar al frente" de Arturo San Emeterio Campos