Datos comprimidos por Ziv y Lempel señalando hacia el texto ya enviado

La compresión clásica se centraba en la codificación de Huffman, pero Huffman necesita un modelo de probabilidades de símbolos construido antes de poder codificar. Hasta 1977, la mayor parte del trabajo asumía que ese modelo tenía que venir de algún lugar.

En «A Universal Algorithm for Sequential Data Compression», Jacob Ziv y Abraham Lempel, del Technion, demostraron que se podía prescindir del modelo. El codificador mantiene una ventana del texto visto recientemente y la compara con el búfer de anticipación entrante; una coincidencia se escribe como un desplazamiento y una longitud, de modo que la repetición casi no cuesta nada.

El resultado es un esquema universal: comprime cualquier fuente sin estadísticas previas, porque el diccionario son los propios datos. El artículo de 1977 es el clásico que convirtió la compresión por diccionario en la base de gzip, PNG y la familia ZIP.

Señalar hacia el texto ya visto en lugar de precalcular

Usar el texto ya enviado como diccionario no requiere una tabla de probabilidades precalculada.

Un único token de desplazamiento más longitud maneja cualquier frase repetida, larga o corta.

El esquema funciona con fuentes desconocidas, por lo que es universal en lugar de estar ajustado a un tipo de archivo.

No construyas un modelo de los datos de antemano; deja que los datos aporten su propia estructura sobre la marcha. Una representación autorreferencial se adapta a cualquier entrada, sea cual sea.

El enfoque LZ se convirtió en la base de la compresión sin pérdida moderna: LZ77 y su descendiente LZ78/LZW impulsan gzip, zip, PNG y el flujo DEFLATE usado en toda la web. Los artículos de Ziv y Lempel obtuvieron el Premio a la Innovación Tecnológica del Jubileo de Oro de 1997 de la IEEE Information Theory Society.