LZ77 y LZ78 son los dos algoritmos de compresión de datos sin pérdida 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 .
En teoría, ambos son codificadores de diccionario . 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 a partir de una ventana deslizante sobre caracteres vistos previamente, 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 todo el diccionario. Sin embargo, en la práctica, el diccionario se crea durante la codificación y la decodificación creando una nueva frase cada vez que se genera un token. [4]
Los algoritmos fueron nombrados un 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 los analiza 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 (en oposición a conjuntos probabilísticos). Esta medida proporciona un límite a la tasa de compresión de datos que se puede lograr. Luego se demuestra que existen codificadores finitos sin pérdida para cada secuencia que alcanzan 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 se puede demostrar de manera más directa, como por ejemplo en las notas de Peter Shor . [7]
Formalmente, (Teorema 13.5.2 [8] ).
LZ78 es universal y entrópico : si es una fuente binaria que es estacionaria y ergódica, entonces con probabilidad 1. Aquí está la tasa de entropía de la fuente.
Teoremas similares se aplican a otras versiones del algoritmo LZ.
Los algoritmos LZ77 logran la compresión reemplazando las repeticiones de datos con referencias a una única copia de esos datos que existía anteriormente en el flujo de datos sin comprimir. Una coincidencia se codifica mediante 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 se encuentran exactamente a distancia caracteres detrás de él en el flujo sin comprimir". (La distancia a veces se denomina desplazamiento ).
Para detectar coincidencias, el codificador debe realizar un seguimiento de cierta cantidad de los datos más recientes, como los últimos 2 KB , 4 KB o 32 KB. La estructura en la que se almacenan estos datos se denomina ventana deslizante , por lo que a veces se denomina compresión de ventana deslizante a LZ77 . 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 mayor sea la ventana deslizante, más tiempo puede retroceder el codificador para crear referencias.
No sólo es aceptable, sino que a menudo resulta útil permitir que los pares longitud-distancia especifiquen una longitud que realmente exceda la distancia. Como comando de copia, esto es desconcertante: "Retroceda cuatro caracteres y copie diez caracteres desde esa posición a la posición actual". ¿Cómo se pueden copiar diez caracteres cuando sólo cuatro de ellos están realmente en el búfer? Si se aborda un byte a la vez, no hay ningún problema en atender esta solicitud, porque a medida que se copia un byte, se puede volver a introducir como entrada en el comando de copia. Cuando la posición de origen de la copia llega a la posición de destino inicial, se le introducen en consecuencia los datos que se pegaron desde el principio de la posición de origen de la copia. La operación es, por tanto, equivalente a la instrucción "copie los datos que le dieron y péguelos 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 desde la primera coincidencia en el desplazamiento D y hacia adelante hasta el final de la ventana de búsqueda deben tener una entrada coincidente, y estos son los caracteres (vistos previamente) que comprenden una sola unidad de ejecución de longitud L R , que debe ser igual a D . Luego, a medida que el puntero de búsqueda avanza más allá de la ventana de búsqueda y hacia adelante, en la medida en que el patrón de ejecución se repita en la entrada, los punteros de búsqueda y entrada estarán sincronizados y coincidirán con los caracteres hasta que se interrumpa el patrón de ejecución. Entonces, se han coincidente L caracteres en total, L > D , y el código es [ D , L , c ].
Al decodificar [ D , L , c ], nuevamente, D = L R . Cuando los primeros L R caracteres se leen en la salida, esto corresponde a una sola 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 hasta el inicio de esa única unidad de ejecución almacenada en búfer, leer L R caracteres (o tal vez menos en el último retorno) y repetir hasta que se lean un total de L caracteres. Pero reflejando el proceso de codificación, dado que el patrón es repetitivo, el puntero de lectura solo necesita seguir en sincronía 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.
Considerando lo anterior, especialmente si se espera que predomine la compresión de las ejecuciones de datos, la búsqueda en la ventana debe comenzar al final de la ventana y proceder 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 de secuencia coincidente actual, 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 match := ocurrencia repetida más larga de la entrada que comienza en la ventana Si existe coincidencia entonces d := distancia al inicio del partido l := longitud del partido c := carácter que sigue a la coincidencia en la entrada demás d := 0 yo := 0 c := primer carácter de la entrada terminar si salida (d, l, c) Descartar l + 1 caracteres del frente de la ventana s := pop l + 1 caracteres del frente de la entrada añadir s al dorso de la ventanarepetir
Aunque todos los algoritmos LZ77 funcionan por definición con 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 la cantidad 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 mediante la construcción de un diccionario de secuencias de tokens a partir de la entrada y luego reemplazando la segunda y subsiguientes ocurrencias 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 previamente 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 voraz y, por lo tanto, no se agrega nada a la tabla hasta que se encuentra un token que la hace única. El algoritmo es 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, entonces el último índice coincidente se establece en el índice de la entrada coincidente, no se genera nada y se deja el último índice coincidente que representa la entrada hasta el momento. La entrada se procesa hasta que no se encuentra una 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 tokensAABBAque ensamblaría el diccionario;
0 {0,_}1 {0,A}2 {1,B}3 {0,B}y la secuencia de salida de los datos comprimidos sería0A1B0BTenga en cuenta que la última A aún no está representada, ya que el algoritmo no puede saber qué viene a continuación. En la práctica, se agrega un marcador EOF a la entrada:AABBA$por ejemplo. Nótese 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 el diccionario crece, 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. A partir de la secuencia0A1B0B1$La primera entrada es siempre el terminador.0 {...}, y el primero de la secuencia sería1 {0,A}. ElAse añade 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 "entrada 0" - nada) por lo queDese añade a la salida. Siguiente0Bse agrega al diccionario como la siguiente entrada,3 {0,B}, y B (sin nada precedido) se agrega a la salida. Finalmente, una entrada de diccionario para1$se crea yUn dólares la salida que da como resultadoUna AB BA$oAABBAeliminando los espacios y el marcador EOF.
LZW es un algoritmo basado en LZ78 que utiliza un diccionario preinicializado con todos los caracteres posibles (símbolos) 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 (ya que el diccionario se inicializa con todos los caracteres posibles), por lo que solo se genera el último índice coincidente (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 en 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 que se encuentra un nodo hoja (un nodo sin dependientes). Este se elimina y el espacio se reutiliza para la nueva entrada. Esto es más simple 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