Cómo funciona hoy la compresión de archivos (y cómo le gané 2,86% a zlib con teoría de grafos)

Cada archivo que se comprime hoy, un .zip, una imagen .png, una petición HTTP con gzip, corre casi siempre sobre el mismo algoritmo de hace 35 años: DEFLATE, el que implementa zlib. Quería entender de verdad cómo funciona por dentro, así que hice lo que mejor sé hacer: traducirlo de C a Rust con c2rust, probar que la traducción no cambia ni un bit, y después ver si podía mejorarlo. Se pudo. Un 2,86% menos que zlib en su nivel más alto de compresión, verificado byte a byte contra la implementación original en C. En el camino, midiendo y no leyendo, quedó claro dónde está el límite real de la compresión sin pérdida y por qué ese límite no se puede tramposear.

La familia de algoritmos que comprime casi todo hoy

Antes de tocar código, un mapa rápido de qué usa qué:

• LZ77 + Huffman (DEFLATE, el motor de zip/gzip/PNG): busca repeticiones recientes (“esto ya apareció hace 200 bytes, cópialo”) y después codifica lo que queda con códigos de largo variable, más cortos para lo más frecuente. Rápido, viejo, universal.
• LZMA (el de 7-Zip y .xz): la misma idea de repeticiones, pero con un codificador aritmético de rango en vez de Huffman, y una ventana de historial mucho más grande. Comprime más, es más lento.
• BWT (el de bzip2): reordena cada bloque (de 100 KB a 900 KB, configurable) para que bytes con el mismo contexto queden juntos, así una repetición dispersa se convierte en una corrida larga fácil de comprimir.
• PPM (el de 7-Zip también, como opción): predice el próximo byte mirando los N anteriores, con una tabla de probabilidades que se ajusta sobre la marcha.
• Context mixing (cmix, paq8px, los mejores en los rankings serios): en vez de un solo modelo, corre decenas en paralelo y los combina con pesos que aprende bit a bit. Es lo que hoy lidera Hutter Prize y Large Text Compression Benchmark, y es carísimo (a veces menos de 10 KB/s).

Todos, sin excepción, chocan con el mismo límite: ningún compresor sin pérdida puede achicar todos los archivos posibles de un tamaño dado, sin importar cuán ingenioso sea. Se puede demostrar contando, no adivinando: si existen 1.024 archivos posibles de 10 bits y el compresor es reversible (tiene que poder recuperar el original), tiene que darle a cada uno una salida distinta. No hay manera de que 1.024 entradas quepan en menos de 1.024 salidas distintas, así que en promedio la salida no puede ser más corta que la entrada. Este es el argumento de conteo (pigeonhole), y es la versión intuitiva de lo que Shannon formalizó para una fuente con cierta distribución de probabilidad: existe un límite a cuánto se puede acortar en promedio, aunque un archivo particular, si tiene mucha estructura, sí puede comprimirse muy por debajo de su tamaño. Lo único que un algoritmo mejor puede hacer es acercarse más a ese promedio, encontrando estructura que uno más simple no ve.

El experimento: traducir zlib y probar que no rompí nada

Tomé el código fuente oficial de zlib 1.3.1 (el mismo que usa medio internet) y lo pasé por c2rust, un traductor mecánico de C a Rust. La traducción sale fea: punteros crudos, aritmética manual, cero seguridad de tipos de Rust. Pero compila y corre.

Antes de tocar una sola línea, necesitaba probar que la traducción no cambió el comportamiento. Armé un arnés que compila la zlib original en C al lado, y compara: comprime con la versión traducida, descomprime con la C real, ¿da el archivo original exacto? Comprime con la C real, descomprime con la traducida, ¿también? Y lo más estricto: ¿los bytes comprimidos son idénticos, no solo “ambos funcionan”?

Corrí esto contra más de 15.000 entradas generadas (aleatorias, repetidas, con patrones cortos, con datos ya comprimidos) y contra los corpus estándar de compresión: los 11 archivos del corpus Canterbury y 18 del corpus Calgary (los 14 que mantiene hoy su sitio oficial, más paper3–paper6, cuatro archivos que la colección usó en evaluaciones anteriores) en varios niveles de compresión de zlib (de los 10 que existen, 0 a 9). Bit exacto en el 100% de los casos probados. En todo lo que corrí, la traducción mecánica no cambió el comportamiento ni un bit.

La traducción automática no salió perfecta a la primera. Cuatro tropiezos reales, de los más instructivos:

• Un script de limpieza que borraba archivos enteros. Para sacar los atributos de features de nightly que c2rust agrega (#![feature(extern_types)] y similares) usé primero un sed que borraba desde el inicio del archivo hasta la primera coincidencia del patrón. En los archivos que no tenían ese atributo, el patrón nunca aparecía y el rango de borrado se comía el archivo completo. Lo reemplacé por un script en Python que sigue la profundidad de corchetes a través de atributos #![...] de varias líneas.
• Un memcpy con el puntero equivocado. En el CRC32 traducido, una llamada pasaba un *const u8 donde la firma esperaba *const c_void; c2rust no agrega ese cast automáticamente. Una línea de cast manual, documentada como la única intervención real en ese archivo.
• PPMd7 con SIGABRT por corrupción de memoria. La estructura CPpmd7Head, traducida a mano por no tener un equivalente directo en Rust, reservaba solo 4 KB de relleno final cuando la real necesita cerca de 20 KB para sus tablas de búsqueda. Subir el buffer a 64 KB lo resolvió.
• Repositorios de C anidados sin darme cuenta. Cloné zlib y xz sin borrar su .git interno antes de agregarlos al repositorio del experimento, así que Git los registró como referencias rotas (gitlinks) en vez de como archivos reales. Se corrige borrando el .git anidado y volviendo a agregar el contenido.

Dónde zlib deja plata sobre la mesa

Con la base traducida y probada, fui a mirar cómo zlib decide qué comprimir. Acá está lo interesante.

DEFLATE junta dos decisiones en cada byte: ¿lo escribo tal cual (un “literal”), o digo “esto ya apareció, cópialo de ahí” (un “match”)? Un match se codifica como distancia hacia atrás más largo a copiar, mirando siempre una ventana de historial reciente (hasta 32 KiB).

Esa decisión, tomada byte a byte a lo largo de todo el archivo, es literalmente un problema de camino más corto en un grafo dirigido: cada posición del archivo es un nodo, cada match posible desde ahí es una arista con un costo en bits, un literal es la arista por defecto al nodo siguiente.

zlib nunca resuelve esto exacto. Su algoritmo (deflate_slow, el que usa en los niveles altos) es greedy con un símbolo de anticipación: mira el match actual, mira uno más, y con eso decide. Nunca ve más allá. Es rápido, y para la mayoría de los datos funciona razonablemente bien. Pero no es óptimo.

Reemplacé esa heurística por programación dinámica: para una tabla de costos fija (el árbol de Huffman del momento), calculo el costo mínimo para llegar al final del archivo desde cada posición, yendo hacia atrás, así cuando llego a una posición ya sé el costo real de cada decisión que puedo tomar ahí. Es exacto para esa tabla de costos puntual, no un óptimo global de todo el stream (eso incluiría, además, elegir el árbol de Huffman ideal a la vez, un problema bastante más caro); la sección siguiente cuenta cómo se acerca a eso iterando. Es el mismo algoritmo que resuelve caminos más cortos en un mapa, aplicado a decisiones de compresión.

El árbol de Huffman también se puede mejorar sobre la marcha

Ahí no termina. DEFLATE no solo elige qué copiar; también construye un árbol de Huffman por bloque, dándole códigos más cortos a los símbolos más frecuentes.

El problema es circular: el parseo óptimo depende de saber cuánto cuesta cada símbolo, y eso depende del árbol. Pero el árbol depende de qué símbolos eligió el parseo.

La solución es iterar: parseo con un costo aproximado, cuento qué símbolos usé de verdad, construyo un árbol real con esas frecuencias, recalculo los costos exactos bajo ese árbol, reparseo con el costo mejorado, y repito hasta que deja de mejorar.

En el camino encontré un bug de verdad: mi primera versión del recorte de códigos Huffman muy largos (por encima de 15 bits, el máximo que permite el formato) dejaba el árbol incompleto: la suma de Kraft (la desigualdad que toda tabla de códigos de largo variable tiene que cumplir para ser decodificable) quedaba por debajo de 1 en vez de exactamente en 1. Un código con Kraft menor a 1 no es necesariamente ambiguo en abstracto, pero el formato DEFLATE exige uno completo, y zlib rechaza la tabla al construir sus tablas de decodificación (Z_DATA_ERROR), no en medio de la lectura de un símbolo. Solo lo disparaban los archivos grandes y variados (768 KB de texto en inglés variado alcanza árboles de 18 bits antes de recortar); los archivos chicos del corpus de prueba nunca lo activaban, así que pasó desapercibido hasta que corrí el corpus completo. Se arregla verificando que la suma de Kraft dé exactamente 1, no menos, y recortando el código más largo cuando sobra margen.

Partir el archivo en bloques, cada uno con su propio árbol

Un solo árbol de Huffman para un archivo entero es un compromiso: si las primeras páginas de un libro usan palabras distintas que las últimas, un árbol único no le sienta bien a ninguna de las dos partes. La solución, que ya usa la herramienta zopfli de Google desde hace años, es partir el archivo en varios bloques DEFLATE, cada uno con su árbol ajustado a esa sección.

Implementé un divisor recursivo: prueba puntos de corte candidatos, calcula el costo exacto de tratar el rango como un bloque contra tratarlo como dos con árboles separados, y solo parte si la ganancia paga el costo del segundo árbol (el header de un árbol nuevo no es gratis).

El resultado, medido y verificado

Sobre esos 29 archivos (6.062.277 bytes en total), el resultado final es 2,86% más chico que zlib en su nivel más alto de compresión. El mejor caso, una hoja de cálculo binaria, mejora 11,5%. Los dos únicos que empeoran son la misma imagen binaria repetida en los dos corpus, y solo por 0,5%.

Los 29 archivos decodifican exactos con la zlib original en C. Nada de esto vale si el archivo comprimido no vuelve a ser el original, byte por byte.

Calibrando la expectativa: esto no es un descubrimiento

Acá viene la parte honesta que no suele estar en los posts de “le gané a X algoritmo”. Lo que hice es, en esencia, una réplica de lo que ya hace zopfli, la herramienta de Google, que típicamente logra entre 3% y 8% contra zlib porque tiene un buscador de coincidencias más completo y años de ajuste fino. Mi 2,86% queda en el extremo bajo de ese rango. No inventé nada nuevo; construí, medí y verifiqué una técnica que ya existía, y el número que salió es consistente con lo que la literatura ya sabía.

Un experimento aparte, más interesante para entender el límite real: probé si una versión del mismo truco sirve en LZMA, el algoritmo de 7-Zip. Lo que probé, específicamente, fue cambiarle a mano el arranque de las probabilidades del codificador aritmético usando estadísticas de una pasada previa, en vez del valor neutro fijo con el que arranca siempre. No sirve: el archivo queda ilegible para cualquier decodificador estándar, porque el formato nunca transmite ese estado en el archivo comprimido — decodificador y codificador lo reconstruyen cada uno por su cuenta, en paralelo, byte a byte, y tienen que arrancar exactamente igual para no perder la sincronía. Eso no significa que ningún ajuste sea posible en un codificador adaptativo: Zstandard, por ejemplo, sí implementa una estrategia real de dos pasadas que recolecta estadísticas para la siguiente, sin tocar el arranque de sus probabilidades. Lo que sí queda acotado es la técnica puntual que usé para DEFLATE (reajustar el estado inicial desde afuera): esa no se traslada a un formato que no lo transmite.

También probé el knob más obvio de LZMA (el preset EXTREME, que sube el largo de match aceptado y la profundidad de búsqueda) contra el preset 9 normal: -0,084% agregado, un archivo incluso empeoró 5,6%. Y en bzip2 probé subir las rondas del ciclo EM que arma sus tablas de Huffman alternativas de 4 (el valor fijo desde 1999) a 50: -0,047% agregado. Ninguno de los dos tiene el margen fácil que tuvo DEFLATE; bzip2 porque su selección multi-tabla ya hace, desde hace 25 años, algo parecido al splitting de bloques que a DEFLATE le faltaba, y LZMA porque su formato compacto no deja espacio para declarar ningún ajuste por archivo.

Lo que esto enseña sobre comprimir datos, en general

Tres ideas que valen más que el número final:

1. La entropía de Shannon es un piso, no un desafío técnico. Ningún algoritmo, sin importar cuán ingenioso, comprime por debajo de la información real que tienen los datos sin perder algo. Lo único que se puede mejorar es qué tan cerca del límite se llega, y eso depende de qué tan bien el modelo entiende la estructura de los datos.
2. Las heurísticas rápidas (greedy) dejan plata sobre la mesa, casi siempre poca. zlib usa una heurística de 30 años porque es rápida y funciona razonablemente bien. Resolverlo exacto (camino mínimo, Huffman dinámico, splitting de bloques) da una mejora real pero modesta: unos pocos puntos porcentuales, no un cambio de categoría.
3. El formato del archivo comprimido decide qué optimizaciones son posibles. Un formato que transmite más metadatos (como el árbol de Huffman de DEFLATE) abre la puerta a afinarlos por archivo. Un formato más compacto (como el estado interno de LZMA) cierra esa puerta a cambio de menos overhead. No hay una opción mejor en absoluto: son compromisos distintos, y entender cuál es cuál dice de antemano qué vale la pena intentar.

Si el salto grande de verdad existe, está en la familia de context mixing, que mezcla decenas de modelos con pesos aprendidos bit a bit en vez de un solo modelo con una heurística. Eso sí cambia de categoría, a costa de ser órdenes de magnitud más lento. Pero esa es otra historia.

Cuándo vale la pena esto, y cuándo no

Concreto, para que sirva de algo más que curiosidad:

• Comprimir una vez y descomprimir muchas (assets de un sitio, paquetes de una release, imágenes estáticas) es el caso donde el parseo óptimo vale la pena: el costo extra de comprimir se paga una sola vez, y el archivo queda 2-3% más chico para siempre. Zopfli ya hace esto en producción para exactamente este caso.
• Comprimir en el camino caliente de una petición (gzip de una respuesta HTTP en tiempo real) es el caso donde no vale la pena: la programación dinámica y el reparsado iterativo son varias veces más lentos que el greedy de zlib, y ahí la latencia importa más que un 3% de tamaño.
• Si el formato ya es LZMA, el ajuste puntual que probé acá (reajustar el arranque de las probabilidades desde afuera) no se traslada, por la razón de formato ya explicada; pero el principio de fondo sí: preguntar si el algoritmo en uso resuelve su decisión de forma exacta o con una heurística de una sola pasada suele revelar margen que nadie fue a buscar. Zstandard es un buen ejemplo de que el principio general (una segunda pasada con más información ayuda) sí se puede aplicar a un codificador adaptativo, solo que hay que hacerlo sin tocar el estado que nunca se transmite.

Fuentes

• Deutsch, P. “DEFLATE Compressed Data Format Specification version 1.3.” RFC 1951, IETF, 1996. Sección 3.2.7 (codificación de largos de código con RLE). rfc-editor.org/rfc/rfc1951
• zlib, código fuente oficial (Mark Adler). github.com/madler/zlib
• Zopfli, compresor DEFLATE de Google. github.com/google/zopfli
• Corpus Calgary y Canterbury, descripciones y descarga oficial. corpus.canterbury.ac.nz/descriptions
• Pavlov, I. LZMA SDK y especificación del formato LZMA. 7-zip.org/sdk.html
• c2rust, traductor de C a Rust (Immunant). github.com/immunant/c2rust