LZ77 y LZ78 son dos algoritmos de compresión de datos sin pérdidas publicados en artículos de Abraham Lempel y Jacob Ziv en 1977 [1] y 1978. [2] También se conocen como LZ1 y LZ2 respectivamente. [3] Estos dos algoritmos forman la base de muchas variaciones, incluidas LZW , LZSS , LZMA y otras. Además de su influencia académica, estos algoritmos formaron la base de varios esquemas de compresión ubicuos, incluidos GIF y el algoritmo DEFLATE utilizado en PNG y ZIP .
Ambos son teóricamente codificadores de diccionarios . LZ77 mantiene una ventana deslizante durante la compresión. Más tarde se demostró que esto era equivalente al diccionario explícito construido por LZ78; sin embargo, solo son equivalentes cuando se pretende descomprimir todos los datos.
Dado que LZ77 codifica y decodifica desde una ventana deslizante sobre caracteres vistos anteriormente, la descompresión siempre debe comenzar al principio de la entrada. Conceptualmente, la descompresión LZ78 podría permitir el acceso aleatorio a la entrada si se conociera de antemano el diccionario completo. Sin embargo, en la práctica, el diccionario se crea durante la codificación y decodificación creando una nueva frase cada vez que se genera un token. [4]
Los algoritmos fueron nombrados Hito IEEE en 2004. [5] En 2021, Jacob Ziv recibió la Medalla de Honor IEEE por su participación en su desarrollo. [6]
En el segundo de los dos artículos que introdujeron estos algoritmos, se analizan como codificadores definidos por máquinas de estados finitos. Se desarrolla una medida análoga a la entropía de la información para secuencias individuales (a diferencia de conjuntos probabilísticos). Esta medida da un límite a la relación de compresión de datos que se puede lograr. Luego se muestra que existen codificadores finitos sin pérdidas para cada secuencia que logran este límite a medida que la longitud de la secuencia crece hasta el infinito. En este sentido, un algoritmo basado en este esquema produce codificaciones asintóticamente óptimas. Este resultado puede demostrarse más directamente, como por ejemplo en las notas de Peter Shor . [7]
Formalmente, (Teorema 12.10.2 [8] ).
LZ78 es universal y entrópico : si es una fuente binaria estacionaria y ergódica, entonces
Se aplican teoremas similares a otras versiones del algoritmo LZ.
Los algoritmos LZ77 logran la compresión reemplazando apariciones repetidas de datos con referencias a una única copia de esos datos que existía anteriormente en el flujo de datos sin comprimir. Una coincidencia está codificada por un par de números llamado par longitud-distancia , que es equivalente a la afirmación "cada uno de los siguientes caracteres de longitud es igual a los caracteres que están exactamente a la distancia detrás de él en la secuencia sin comprimir". (La distancia a veces se denomina desplazamiento ).
Para detectar coincidencias, el codificador debe realizar un seguimiento de una cierta cantidad de los datos más recientes, como los últimos 2 KB , 4 KB o 32 KB. La estructura en la que se guardan estos datos se llama ventana deslizante , razón por la cual LZ77 a veces se denomina compresión de ventana deslizante . El codificador debe conservar estos datos para buscar coincidencias y el decodificador debe conservar estos datos para interpretar las coincidencias a las que hace referencia el codificador. Cuanto más grande sea la ventana deslizante, más tiempo atrás podrá buscar el codificador para crear referencias.
No sólo es aceptable sino frecuentemente útil permitir que los pares longitud-distancia especifiquen una longitud que realmente exceda la distancia. Como comando de copia, esto es desconcertante: "Regrese cuatro caracteres y copie diez caracteres desde esa posición a la posición actual". ¿Cómo se pueden copiar diez caracteres cuando en realidad sólo cuatro de ellos están en el búfer? Al abordar un byte a la vez, no hay ningún problema en atender esta solicitud, porque a medida que se copia un byte, se puede enviar nuevamente como entrada al comando de copia. Cuando la posición de copia llega a la posición de destino inicial, en consecuencia se alimentan los datos que se pegaron desde el principio de la posición de copia. Por tanto, la operación equivale a la frase "copia los datos que te han proporcionado y pégalos repetidamente hasta que quepan". Como este tipo de par repite una única copia de datos varias veces, se puede utilizar para incorporar una forma flexible y sencilla de codificación de longitud de ejecución .
Otra forma de ver las cosas es la siguiente: durante la codificación, para que el puntero de búsqueda continúe encontrando pares coincidentes más allá del final de la ventana de búsqueda, todos los caracteres de la primera coincidencia en el desplazamiento D y hacia adelante hasta el final de la ventana de búsqueda deben haber coincidido. entrada, y estos son los caracteres (vistos anteriormente) que componen una única unidad de ejecución de longitud L R , que debe ser igual a D . Luego, a medida que el puntero de búsqueda pasa por la ventana de búsqueda y avanza, en la medida en que el patrón de ejecución se repite en la entrada, los punteros de búsqueda y de entrada estarán sincronizados y coincidirán con los caracteres hasta que se interrumpa el patrón de ejecución. Entonces L caracteres han coincidido en total, L > D , y el código es [ D , L , c ].
Al decodificar [ D , L , c ], nuevamente, D = L R . Cuando los primeros caracteres L R se leen en la salida, esto corresponde a una única unidad de ejecución agregada al búfer de salida. En este punto, se podría pensar que el puntero de lectura solo necesita devolver int( L / L R ) + (1 si L mod L R ≠ 0) veces al inicio de esa única unidad de ejecución almacenada en búfer, leer los caracteres L R ( o tal vez menos en la última devolución), y repita hasta que se lea un total de L caracteres. Pero al reflejar el proceso de codificación, dado que el patrón es repetitivo, el puntero de lectura solo necesita sincronizarse con el puntero de escritura una distancia fija igual a la longitud de ejecución L R hasta que se hayan copiado L caracteres en la salida en total.
Teniendo en cuenta lo anterior, especialmente si se espera que predomine la compresión de las ejecuciones de datos, la búsqueda de la ventana debe comenzar al final de la ventana y continuar hacia atrás, ya que los patrones de ejecución, si existen, se encontrarán primero y permitirán que la búsqueda termine. absolutamente si se cumple la longitud máxima actual de la secuencia coincidente, o juiciosamente, si se cumple una longitud suficiente, y finalmente por la simple posibilidad de que los datos sean más recientes y puedan correlacionarse mejor con la siguiente entrada.
El siguiente pseudocódigo es una reproducción de la ventana deslizante del algoritmo de compresión LZ77.
mientras la entrada no esté vacía, hazlo coincidencia: = aparición repetida más larga de entrada que comienza en la ventana si existe coincidencia entonces d := distancia hasta el inicio del partido l := duración del partido c := char siguiente coincidencia en la entrada demás d := 0 yo := 0 c := primer carácter de entrada terminara si salida (d,l,c) descartar l + 1 caracteres del frente de la ventana s := pop l + 1 caracteres desde el frente de la entrada agregar s a la parte posterior de la ventanarepetir
Aunque todos los algoritmos LZ77 funcionan por definición según el mismo principio básico, pueden variar ampliamente en la forma en que codifican sus datos comprimidos para variar los rangos numéricos de un par longitud-distancia, alterar el número de bits consumidos para un par longitud-distancia, y distinguir sus pares longitud-distancia de los literales (datos sin procesar codificados como sí mismos, en lugar de como parte de un par longitud-distancia). Algunos ejemplos:
Los algoritmos LZ78 comprimen datos secuenciales construyendo un diccionario de secuencias de tokens a partir de la entrada y luego reemplazando la segunda aparición y posteriores de la secuencia en el flujo de datos con una referencia a la entrada del diccionario. La observación es que el número de secuencias repetidas es una buena medida de la naturaleza no aleatoria de una secuencia. Los algoritmos representan el diccionario como un árbol n-ario donde n es el número de tokens utilizados para formar secuencias de tokens. Cada entrada del diccionario tiene la forma dictionary[...] = {index, token}, donde índice es el índice de una entrada del diccionario que representa una secuencia vista anteriormente, y token es el siguiente token de la entrada que hace que esta entrada sea única en el diccionario. Observe cómo el algoritmo es codicioso y, por lo tanto, no se agrega nada a la tabla hasta que se encuentre un token único. El algoritmo consiste en inicializar el último índice coincidente = 0 y el siguiente índice disponible = 1 y luego, para cada token del flujo de entrada, el diccionario busca una coincidencia: {last matching index, token}. Si se encuentra una coincidencia, el último índice coincidente se establece en el índice de la entrada coincidente, no se genera nada y el último índice coincidente queda representando la entrada hasta el momento. La entrada se procesa hasta que no se encuentra ninguna coincidencia. Luego se crea una nueva entrada de diccionario dictionary[next available index] = {last matching index, token}y el algoritmo genera el último índice coincidente, seguido del token, luego restablece el último índice coincidente = 0 e incrementa el siguiente índice disponible. Como ejemplo, considere la secuencia de tokens.AABBAque armaría el diccionario;
0 {0,_}10 A}2 {1,B}3 {0,B}y la secuencia de salida de los datos comprimidos sería0A1B0B. Tenga en cuenta que la última A aún no está representada porque el algoritmo no puede saber qué sigue a continuación. En la practica, se agrega un marcador EOF a la entrada:AABBA$Por ejemplo. Tenga en cuenta también que en este caso la salida0A1B0B1$es más largo que la entrada original, pero la relación de compresión mejora considerablemente a medida que crece el diccionario, y en binario los índices no necesitan estar representados por más que el número mínimo de bits. [11]
La descompresión consiste en reconstruir el diccionario a partir de la secuencia comprimida. De la secuencia0A1B0B1$la primera entrada es siempre el terminador0 {...}, y el primero de la secuencia sería10 A}. ElAse agrega a la salida. El segundo par de la entrada es1By da como resultado la entrada número 2 en el diccionario,{1,B}. Se genera el token "B", precedido por la secuencia representada por la entrada 1 del diccionario. La entrada 1 es una "A" (seguida de la "entrada 0" - nada), por lo queABse agrega a la salida. Próximo0Bse agrega al diccionario como la siguiente entrada,3 {0,B}y B (precedido por nada) se agrega a la salida. Finalmente una entrada de diccionario para1$se crea yA$es la salida que resulta enAB BA$oAABBAeliminando los espacios y el marcador EOF.
LZW es un algoritmo basado en LZ78 que utiliza un diccionario preinicializado con todos los caracteres (símbolos) posibles o la emulación de un diccionario preinicializado. La principal mejora de LZW es que cuando no se encuentra una coincidencia, se supone que el carácter del flujo de entrada actual es el primer carácter de una cadena existente en el diccionario (dado que el diccionario se inicializa con todos los caracteres posibles), por lo que solo se muestra la última coincidencia. Se genera el índice (que puede ser el índice del diccionario preinicializado correspondiente al carácter de entrada anterior (o inicial)). Consulte el artículo de LZW para obtener detalles de implementación.
BTLZ es un algoritmo basado en LZ78 que fue desarrollado para su uso en sistemas de comunicaciones en tiempo real (originalmente módems) y estandarizado por CCITT/ITU como V.42bis . Cuando el diccionario estructurado trie está lleno, se utiliza un algoritmo simple de reutilización/recuperación para garantizar que el diccionario pueda seguir adaptándose a los datos cambiantes. Un contador recorre el diccionario. Cuando se necesita una nueva entrada, el contador recorre el diccionario hasta encontrar un nodo hoja (un nodo sin dependientes). Esto se elimina y el espacio se reutiliza para la nueva entrada. Esto es más sencillo de implementar que LRU o LFU y logra un rendimiento equivalente.
Medios relacionados con el algoritmo LZ77 en Wikimedia CommonsMedios relacionados con el algoritmo LZ78 en Wikimedia Commons