LZ77 y LZ78

LZ77 y LZ78 son los dos algoritmos de compresión de datos sin pérdidas publicados en artículos de Abraham Lempel y Jacob Ziv en 1977 y 1978. También se conocen como LZ1 y LZ2 respectivamente. 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 omnipresentes, 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 desde una ventana deslizante sobre los 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 todo el diccionario de antemano. Sin embargo, en la práctica, el diccionario se crea durante la codificación y decodificación mediante la creación de una nueva frase cada vez que se emite un token.

Los algoritmos fueron nombrados IEEE Milestone en 2004. En 2021, Jacob Ziv recibió la Medalla de Honor IEEE por su participación en su desarrollo.

Eficiencia teórica

En el segundo de los dos artículos que presentaron 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 los 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 probarse más directamente, como por ejemplo en las notas de Peter Shor.

LZ77

Los algoritmos LZ77 logran la compresión reemplazando las apariciones repetidas de datos con referencias a una sola copia de esos datos que existía antes en el flujo de datos sin comprimir. Una coincidencia está codificada por un par de números llamados par longitud-distancia, que es equivalente a la afirmación "cada uno de los siguientes caracteres de longitud es igual al caracteres exactamente distancia caracteres detrás de él en la transmisión sin comprimir". (La distancia a veces se denomina desplazamiento en su lugar).

Para detectar coincidencias, el codificador debe realizar un seguimiento de una parte 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 denomina 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 se refiere el codificador. Cuanto más grande es la ventana deslizante, más atrás puede buscar el codificador para crear referencias.

No solo es aceptable, sino frecuentemente útil, permitir que los pares de longitud y distancia especifiquen una longitud que realmente exceda la distancia. Como comando de copia, esto es desconcertante: "Regresar cuatro caracteres y copiar diez caracteres desde esa posición a la posición actual". ¿Cómo se pueden copiar diez caracteres cuando solo cuatro de ellos están realmente en el búfer? Al abordar un byte a la vez, no hay problema para atender esta solicitud, porque a medida que se copia un byte, puede volver a alimentarse como entrada al comando de copia. Cuando la posición de origen de la 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 origen de la copia. Por lo tanto, la operación es equivalente a la afirmación "copia los datos que te dieron y pégalos repetidamente hasta que encajen". Como este tipo de par repite una sola copia de datos varias veces, se puede utilizar para incorporar una forma flexible y fácil 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 el primero coinciden en el desplazamiento D y hacia adelante hasta el final de la ventana de búsqueda debe haber coincidido con la entrada, y estos son los caracteres (vistos anteriormente) que comprenden una sola unidad 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 avanza, en la medida en que el patrón de ejecución se repita en la entrada, los punteros de búsqueda e entrada estarán sincronizados y coincidirán con los caracteres hasta que se interrumpa el patrón de ejecución. Entonces L caracteres han sido emparejados en total, L > D, y el código es [D, L, c].

Al decodificar [D, L, c], de nuevo, D = L_R. Cuando los primeros caracteres L_R se leen en la salida, esto corresponde a una única unidad de ejecución añadida al búfer de salida. En este punto, podría pensarse 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, lea L_R caracteres (o tal vez menos en el último resultado) y repita hasta leer 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 sincronizarse con el puntero de escritura en una distancia fija igual a la longitud de ejecución L_R hasta Los caracteres L se han copiado en la salida en total.

Teniendo en cuenta lo anterior, especialmente si se espera que predomine la compresión de ejecuciones de datos, la búsqueda de 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 la búsqueda. para terminar, 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.

Pseudocódigo

El pseudocódigo es una reproducción de la ventana deslizante del algoritmo de compresión LZ77.

mientras La entrada no está vacía dopartido:= ocurrencia repetida más larga de entrada que comienza en la ventana

 si partido existe entoncesd:= distancia al inicio del partido
l:= longitud del partido
c:= char siguiente partido en entrada
 másD:= 0
l:= 0
c:= primer char de entrada
 terminar si Producto d, l, c)

descarte l + 1 chars desde la ventana
s:= pop l + 1 chars desde la entrada
apéndice s a la parte posterior de la ventana
repetición

Implementaciones

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 una longitud- par de distancia y distinguir sus pares longitud-distancia de literales (datos sin procesar codificados como sí mismos, en lugar de como parte de un par longitud-distancia). Algunos ejemplos:

• El algoritmo ilustrado en el artículo original de Lempel y Ziv produce todos sus datos tres valores a la vez: la longitud y distancia del partido más largo encontrado en el búfer, y el literal que siguió ese partido. Si dos caracteres sucesivos en el flujo de entrada podrían ser codificados sólo como literales, la longitud del par longitud–distancia sería 0.
• LZSS mejora en LZ77 utilizando una bandera de 1 bit para indicar si el siguiente trozo de datos es un par literal o de distancia longitud, y usando literales si un par longitud–distancia sería más largo.
• En el formato PalmDoc, un par longitud–distancia siempre está codificado por una secuencia de dos bytes. De los 16 bits que componen estos dos bytes, 11 bits van a encodificar la distancia, 3 van a encodificar la longitud, y los dos restantes se utilizan para asegurarse de que el decodificador puede identificar el primer byte como el comienzo de tal secuencia de dos bytes.
• En la implementación utilizada para muchos juegos por Electronic Arts, el tamaño en bytes de un par longitud–distancia se puede especificar dentro del primer byte de la par longitud–distancia misma; dependiendo de si el primer byte comienza con un 0, 10, 110 o 111 (cuando se lee en la orientación del bit grande-endian), la longitud de todo el par longitud–distancia puede ser de 1 a 4 bytes.
• A partir de 2008, el método de compresión LZ77 más popular es DEFLATE; combina LZSS con codificación Huffman. Literales, longitudes y un símbolo para indicar el final del bloque actual de datos se colocan todos juntos en un alfabeto. Las distancias se pueden colocar con seguridad en un alfabeto separado; porque una distancia sólo ocurre después de una longitud, no puede ser confundido para otro tipo de símbolo o viceversa.

LZ78

Los algoritmos LZ78 comprimen datos secuenciales mediante la creación de un diccionario de secuencias de tokens a partir de la entrada y, luego, reemplazan la segunda aparición de la secuencia y las subsiguientes 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 index es el índice de una entrada de 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. Tenga en cuenta cómo el algoritmo es codicioso, por lo que no se agrega nada a la tabla hasta que se encuentra un token de creación ú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: {último índice coincidente, 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 se deja representando 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] = {último índice coincidente, 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 AABBA que ensamblarían el diccionario;

0 {0,_}
1 {0,A}
2 {1,B}
3 {0,B}

y la secuencia de salida de los datos comprimidos sería 0A1B0B. Tenga en cuenta que la última A aún no está representada ya que el algoritmo no puede saber qué viene después. En la práctica, se agrega un marcador EOF a la entrada: AABBA$, por ejemplo. Tenga en cuenta también que en este caso la salida 0A1B0B1$ es más larga 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.

La descompresión consiste en reconstruir el diccionario a partir de la secuencia comprimida. De la secuencia 0A1B0B1$ la primera entrada siempre es el terminador 0 {...} , y el primero de la secuencia sería 1 {0,A} . El A se agrega a la salida. El segundo par de la entrada es 1B y da como resultado la entrada número 2 en el diccionario, {1,B}. La ficha "B" es la salida, precedida por la secuencia representada por la entrada de diccionario 1. La entrada 1 es una 'A' (seguido de "entrada 0" - nada) por lo que AB se agrega a La salida. Siguiente 0B se agrega al diccionario como la siguiente entrada, 3 {0,B} , y B (precedido por nada) se agrega a la salida. Finalmente, se crea una entrada de diccionario para 1$ y A$ da como resultado A AB B A$ o AABBA eliminando los espacios y el marcador EOF.

LZW

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 asume que el carácter de 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 el último índice coincidente (que puede ser el índice de 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 tres 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 vuelve a utilizar para la nueva entrada. Esto es más simple de implementar que LRU o LFU y logra un rendimiento equivalente.