La compresión de Lempel-Ziv

La compresión de Lempel-Ziv (en inglés, Lempel-Ziv compression) es una familia de métodos para reducir el tamaño de un texto, o de cualquier fichero, sustituyendo cada fragmento que ya ha aparecido antes por una referencia a su aparición anterior. En lugar de escribir otra vez «tristes tigres», el compresor (compressor) anota algo como «copia catorce caracteres empezando treinta y un caracteres atrás». Si la referencia ocupa menos que el fragmento, el fichero encoge. Abraham Lempel y Jacob Ziv, dos ingenieros del Technion de Haifa, publicaron la idea en 1977, y casi medio siglo después sigue dentro de los ficheros ZIP, de las imágenes PNG, de los programas que se descargan y de buena parte de las páginas web, que viajan por la red comprimidas con una variante suya.

La figura de esta página comprime un texto delante del lector. Cada tramo sombreado en naranja no se guarda letra a letra sino como una referencia hacia atrás, y al pasar el puntero por encima se ilumina en negro el tramo del que se copia. Lo que queda sin sombrear son letras sueltas, que se guardan tal cual. Las dos barras de abajo comparan el tamaño original con el comprimido, calculado con una cuenta sencilla: un bit para distinguir letra de referencia, ocho bits por letra suelta, y para cada referencia los bits necesarios para decir cuánto hay que retroceder y ocho más para decir cuánto hay que copiar. El texto se puede cambiar, y el menú trae cinco ejemplos elegidos para que salgan cosas distintas.

El trabalenguas de los tigres se reduce a menos de la mitad, porque el ochenta por ciento de sus letras repite algo que ya había salido. El primer párrafo del Quijote encoge bastante menos: la mitad de sus caracteres se pueden copiar de atrás, pero en trozos cortos, como «de la», « los » o «que », y cada referencia cuesta casi lo mismo que las tres o cuatro letras que ahorra. La cadena «abababab» enseña el caso extremo y un detalle ingenioso del método: después de las dos primeras letras, una sola referencia dice «copia doscientos treinta y ocho caracteres empezando dos atrás». La copia se solapa consigo misma, porque se hace carácter a carácter y cada letra copiada ya está disponible para la siguiente, así que una referencia puede repetir un patrón tantas veces como haga falta. Las letras al azar, en cambio, no tienen nada que repetir, y el resultado ocupa más que el original.

Ese último caso no es un defecto del algoritmo sino un teorema. Ningún método sin pérdida (lossless) puede encoger todos los ficheros, por una cuenta de casillas: hay más ficheros de mil bits que ficheros de menos de mil bits, así que si un compresor acortara todos, dos ficheros distintos acabarían en el mismo resultado y no se podría saber cuál era el original. Comprimir es apostar a que los datos tienen una estructura, y la de Lempel-Ziv es la repetición: palabras, frases, etiquetas de una página web, filas parecidas en una tabla. La codificación de Huffman apuesta por otra, que unos símbolos sean más frecuentes que otros, y por eso gana con el ADN al azar del menú: cada una de sus cuatro letras cabe en dos bits, la cuarta parte de lo que ocupa, mientras que Lempel-Ziv, que en él solo encuentra repeticiones cortas, no baja del sesenta por ciento.

El tamaño de la ventana, el tramo de texto anterior donde se buscan coincidencias, es el principal ajuste del método. Con una ventana de dieciséis caracteres casi nada se repite tan cerca; con una de 32.768, el máximo del formato DEFLATE que usan ZIP y PNG, se encuentran coincidencias lejanas, pero cada referencia necesita quince bits para decir la distancia. En un texto corto como los de la figura, las ventanas grandes cuestan más de lo que encuentran; en un fichero de megabytes, donde un nombre o una etiqueta se repiten a miles de caracteres de distancia, compensan de sobra. Los compresores reales afinan además la cuenta: no gastan ocho bits fijos en cada letra ni la misma cantidad en cada distancia, sino que pasan las letras y las referencias por una codificación de Huffman, de modo que lo frecuente ocupa poco. Con esa segunda etapa, el párrafo del Quijote se queda en algo menos del sesenta por ciento de su tamaño.

La aportación de Lempel y Ziv no fue solo un procedimiento práctico sino una demostración. Sus dos artículos, el de 1977, que usa la ventana deslizante (sliding window) de la figura, y el de 1978, que va construyendo un diccionario (dictionary) de frases ya vistas, probaron que el método es universal: aplicado a un texto suficientemente largo, comprime tanto como el mejor método diseñado a propósito para esa fuente, sin saber nada de antemano sobre ella. Huffman necesita conocer las frecuencias de los símbolos antes de empezar; Lempel-Ziv las descubre sobre la marcha. En 1984, Terry Welch, de la empresa Sperry, publicó una versión del método de 1978 sencilla y rápida, conocida como LZW, que se convirtió en la orden compress de Unix y en el formato de imagen GIF.

LZW tuvo una historia judicial. Welch había patentado el método, y en 1994 Unisys, la empresa que heredó la patente, empezó a exigir licencias a los programas que creaban imágenes GIF. La respuesta fue un formato nuevo y libre de patentes, PNG, que se basó en DEFLATE, la combinación de la ventana de 1977 con la codificación de Huffman que Phil Katz había creado para el compresor PKZIP y que L. Peter Deutsch documentó en 1996 como norma de internet. La patente expiró en 2003, pero para entonces DEFLATE estaba en todas partes: en los ficheros ZIP y en los .gz, en las imágenes PNG, en los documentos PDF y en la compresión con que los servidores web envían sus páginas.

Los compresores más recientes, como Brotli, que Google publicó en 2015, o Zstandard, que Facebook liberó en 2016, comprimen más, o más deprisa, con ventanas de megabytes y diccionarios preparados de antemano, pero por dentro hacen lo mismo que la figura. Buscan en lo ya escrito el tramo más largo que coincide con lo que viene, y en lugar de repetirlo, apuntan hacia él. La idea tiene algo de lectura: un texto comprimido es un texto que recuerda lo que ya ha dicho.