La compresión de datos explicada

Cada página web que cargas, cada archivo ZIP y cada imagen PNG ha sido comprimido: reducido sin perder ni un solo bit, y descomprimido de nuevo al llegar. Los métodos que lo hacen posible son sorprendentemente sencillos. Buscan lo que se repite y dicen «lo mismo que antes» en lugar de volver a decirlo. Hasta dónde llega esa idea, y dónde se detiene, es una de las historias más elegantes de la informática.

Una línea de texto en la que los fragmentos repetidos se sustituyen por flechas que apuntan a su primera aparición, junto a unas barras que muestran el tamaño original y el comprimido
Una línea de texto en la que los fragmentos repetidos se sustituyen por flechas que apuntan a su primera aparición, junto a unas barras que muestran el tamaño original y el comprimido

Sin pérdida y con pérdida

La compresión es de dos tipos. La compresión sin pérdida devuelve exactamente el original, algo imprescindible para textos, programas, hojas de cálculo y todo aquello en lo que un solo bit erróneo importa. La compresión con pérdida, que se usa para fotos, música y vídeo, descarta detalles que apenas se perciben y alcanza tamaños mucho menores, pero el original se pierde para siempre. Esta página y el demostrador tratan de la compresión sin pérdida, que funciona encontrando y eliminando la redundancia: las partes de los datos que se podrían haber predicho.

La codificación por longitud de series

El método más sencillo sustituye una serie de símbolos idénticos por un recuento y el símbolo: doce píxeles blancos se convierten en 12W (W de white, blanco). Lo usaban los faxes, los primeros formatos de mapa de bits y el formato de imagen PCX, porque las páginas escaneadas y los dibujos sencillos están llenos de series largas. En un texto corriente es inútil, incluso perjudicial: las series son raras, y escribir un recuento para cada letra duplica el tamaño. Aun así, la codificación por longitud de series sigue viva dentro de otros métodos, para las series de ceros que deja una primera transformación.

LZ77: remitir hacia atrás

En 1977, Abraham Lempel y Jacob Ziv, dos investigadores del Technion de Israel, publicaron un método que cambió el campo. El codificador mantiene una ventana con el texto que acaba de procesar. Si los caracteres siguientes ya aparecieron en la ventana, escribe un par: a qué distancia hacia atrás empieza la copia anterior y cuánto mide. Si no, escribe el propio carácter. El decodificador no necesita ningún diccionario, solo el texto que ya ha reconstruido. Una referencia puede incluso solaparse con el texto que produce, de modo que una serie de 100 letras idénticas queda en una letra y una referencia.

Abraham Lempel, que con Jacob Ziv en el Technion en 1977 publicó el método de ventana y referencias hoy conocido como LZ77.
Abraham Lempel, que con Jacob Ziv en el Technion en 1977 publicó el método de ventana y referencias hoy conocido como LZ77.

LZW: aprender un diccionario

El segundo método de Lempel y Ziv, LZ78, construye un diccionario en lugar de mirar hacia atrás en una ventana. La mejora de Terry Welch de 1984, LZW, parte de los 256 valores de byte y, en cada paso, envía el número de la cadena más larga que ya conoce y añade esa cadena más el carácter siguiente como nueva entrada. El decodificador reconstruye el mismo diccionario solo a partir de los números. LZW era rápido y sencillo, y llegó al comando Unix compress, al formato de imagen GIF y a los archivos TIFF, hasta que sus patentes provocaron una larga disputa en los años noventa.

Deflate, ZIP y más allá

El método deflate de Phil Katz, presentado con PKZIP 2 en 1993, combina LZ77 con la codificación de Huffman: tras encontrar las repeticiones, asigna los códigos de bits más cortos a los literales, longitudes y distancias más comunes. Deflate se usa en ZIP, gzip, las imágenes PNG y la compresión de páginas web, y es el método que el demostrador mide con el compresor integrado del navegador. Métodos más recientes como Zstandard, Brotli y xz usan ventanas más grandes, una búsqueda de coincidencias más inteligente y una codificación entrópica más precisa, y reducen los archivos típicos entre un 10 y un 30 % más.

Por qué no todo se puede reducir

Ningún método puede hacer más pequeños todos los archivos. Hay 2ⁿ archivos de n bits, pero solo 2ⁿ − 1 archivos más cortos, así que si un método los redujera todos, dos acabarían siendo iguales y no se podrían restaurar ambos: es el principio del palomar. Por eso todo compresor agranda algunas entradas, normalmente datos de aspecto aleatorio como archivos cifrados, archivos ya comprimidos y ruido. También es una prueba de aleatoriedad: los datos que ningún compresor consigue reducir parecen aleatorios.

El límite de la entropía

Claude Shannon demostró en 1948 que la entropía de una fuente es el menor número medio posible de bits por símbolo para cualquier código sin pérdida. Contada letra por letra, la entropía del texto en inglés es de unos 4 bits por letra, la mitad de los 8 bits en los que se almacena. Los métodos que usan el contexto, como LZ77, bajan de esa cifra letra por letra en un texto repetitivo, porque una referencia representa todo un fragmento de una vez. Los mejores compresores modernos, que predicen cada letra a partir de todo lo anterior, dejan el inglés por debajo de 2 bits por letra.

Claude Shannon, que en 1948, en Bell Labs, precisó cuánta información contiene un mensaje y la midió en bits.
Claude Shannon, que en 1948, en Bell Labs, precisó cuánta información contiene un mensaje y la midió en bits.

Explóralo

Abre el demostrador de compresión para aplicar LZ77, LZW y la codificación por longitud de series a un párrafo, una canción con estribillo, una fila de píxeles, una tabla de datos, letras aleatorias o ADN, o a tu propio texto. Haz clic en cualquier referencia de LZ77 para ver qué copia, observa cómo crece el diccionario de LZW y compara todos los métodos con ZIP y con el límite de la entropía.

Preguntas frecuentes

¿Qué significa una relación de compresión de 3 : 1?

Que el original es tres veces más grande que la versión comprimida, así que el archivo comprimido ocupa un tercio del espacio y ahorra dos tercios. Con ZIP, un texto suele alcanzar de 2 : 1 a 4 : 1; los datos con mucha repetición, como los archivos de registro, a menudo mucho más.

¿Por qué no sirve de nada volver a comprimir un archivo ZIP?

La primera pasada ya eliminó las repeticiones, y su resultado parece casi aleatorio. Una segunda pasada no encuentra nada a lo que remitir y solo añade su propia sobrecarga, así que el archivo se queda del mismo tamaño o crece un poco.

¿Por qué es mejor una ventana de LZ77 más grande?

Una ventana más grande permite al codificador encontrar repeticiones que están más atrás, como un estribillo que vuelve después de varias estrofas. El precio es que cada distancia necesita más bits y que la búsqueda tarda más, y por eso deflate se queda en 32 KB mientras que los métodos más recientes admiten megabytes.

¿Es lo mismo comprimir que cifrar?

No. La compresión hace los datos más pequeños y cualquiera puede deshacerla; el cifrado hace los datos ilegibles sin una clave. A menudo se combinan, y entonces hay que comprimir primero: los datos cifrados parecen aleatorios y ya no se pueden comprimir.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir el demostrador de compresión