Cómo funciona realmente la compresión de archivos: Huffman Coding, LZ77 y DEFLATE explicados

Todo desarrollador ha trabajado con archivos comprimidos. Descomprimes un paquete, sirves una respuesta codificada con gzip, o exportas un PNG — y bajo el capó ocurre compresión. Pero la pregunta que la mayoría de los tutoriales esquivan es: ¿por qué funciona? ¿Por qué puedes tomar un archivo de texto de 500 KB y reducirlo a 180 KB sin perder ni un solo byte, pero no puedes comprimir significativamente un archivo ZIP?

La respuesta está en la teoría de la información y un puñado de algoritmos elegantes. Este artículo recorre la mecánica real: desde la entropía de Shannon hasta los árboles de Huffman y el formato DEFLATE que sustenta ZIP, gzip y PNG.

Por qué los archivos son comprimibles

Los archivos son comprimibles porque contienen redundancia — patrones, repeticiones y secuencias predecibles que llevan menos información de la que sugiere su recuento de bytes sin procesar.

Considera un ejemplo sencillo. La cadena AAAAAAAAAA (diez A) ocupa 10 bytes en ASCII. Pero el contenido informativo es trivial: podrías describirla perfectamente como "diez A". Un algoritmo de compresión hace exactamente eso: reemplaza datos verbosos y redundantes por una descripción más corta.

Los archivos reales están llenos de este tipo de redundancia:

• El texto en español reutiliza palabras comunes y combinaciones de letras constantemente. "que", "ción", "mente" aparecen mucho más frecuentemente que "xqz".
• El código fuente tiene una estructura profundamente repetitiva: function, return, const, sangrados, líneas en blanco.
• Las imágenes de mapa de bits contienen largas secuencias horizontales de píxeles idénticos o casi idénticos, especialmente en áreas de color plano.
• Los archivos de registro repiten marcas de tiempo, nombres de host y códigos de estado miles de veces.

Cuanto más redundante es el dato, más comprimible es. Cuanto menos redundante — cuanto más aleatorio — más difícil resulta comprimirlo.

Entropía: el límite absoluto de la compresión

El paper de Claude Shannon de 1948, A Mathematical Theory of Communication, introdujo una forma precisa de medir el contenido de información: la entropía, medida en bits.

La entropía de Shannon responde a la pregunta: ¿cuántos bits necesitas realmente, en promedio, para representar un símbolo de esta fuente de datos?

La fórmula para una fuente con símbolos s₁, s₂, ..., sₙ y probabilidades p₁, p₂, ..., pₙ es:

H = -Σ pᵢ × log₂(pᵢ)

Esto es lo que significa en la práctica. Supón que tienes un archivo que contiene solo dos caracteres: A (aparece el 90% de las veces) y B (aparece el 10% de las veces).

H = -(0.9 × log₂(0.9)) - (0.1 × log₂(0.1))
H = -(0.9 × -0.152) - (0.1 × -3.322)
H ≈ 0.137 + 0.332
H ≈ 0.469 bits por símbolo

Una codificación ingenua usa 1 bit por símbolo (0 para A, 1 para B). Pero la entropía dice que el mínimo teórico es de 0,469 bits por símbolo — menos de la mitad. Un buen algoritmo de compresión se aproxima a ese límite.

Considera ahora un archivo verdaderamente aleatorio donde cada valor de byte (0–255) aparece con igual probabilidad (1/256 cada uno):

H = -(256 × (1/256) × log₂(1/256))
H = log₂(256) = 8 bits por byte

Ocho bits por byte — entropía máxima. No hay redundancia que explotar. Esta es la razón por la que no puedes comprimir más un archivo ZIP: ya está cerca de la entropía máxima. Cada bit lleva información; no quedan patrones que eliminar.

Codificación por longitud de ejecución: la forma más simple

Antes de llegar a los algoritmos más complejos, la codificación por longitud de ejecución (RLE) ilustra la idea central de forma clara.

RLE reemplaza una secuencia de símbolos repetidos por un contador y el símbolo:

Original:  AAABBBBBCCDDDDDD
RLE:       3A 5B 2C 6D

Original: 16 caracteres. Codificado: 8 caracteres. Reducción del 50%.

RLE se usa en transmisión de fax (CCITT Grupo 3/4), archivos BMP y como subpaso dentro de formatos más complejos. Su debilidad es obvia: funciona mal con datos que no tienen largas secuencias repetidas. La cadena ABABABAB no tiene secuencias, por lo que RLE la hace más grande al anteponer contadores de 1 en todas partes.

Esa debilidad es precisamente la que impulsa enfoques más sofisticados.

Huffman Coding: códigos más cortos para símbolos frecuentes

En ASCII estándar, cada carácter recibe 8 bits independientemente de la frecuencia con que aparezca. Huffman coding rompe esa suposición. Los símbolos frecuentes reciben códigos más cortos; los símbolos raros reciben códigos más largos. La longitud media del código disminuye y el archivo se encoge.

Construyendo un árbol de Huffman

Tomemos la cadena AABBBCCCC (9 caracteres). Contamos las frecuencias:

Paso 1. Coloca cada símbolo en un nodo hoja ponderado por su frecuencia.

[A:2]  [B:3]  [C:4]

Paso 2. Fusiona repetidamente los dos nodos de menor peso en un nodo padre cuyo peso es su suma, hasta que quede un solo árbol.

Fusiona [A:2] y [B:3] → padre [AB:5]:

      [AB:5]
      /     \
   [A:2]  [B:3]

[C:4]

Fusiona [C:4] y [AB:5] → raíz [ABC:9]:

         [ABC:9]
         /      \
      [C:4]  [AB:5]
              /    \
           [A:2]  [B:3]

Paso 3. Asigna códigos recorriendo el árbol: arista izquierda = 0, arista derecha = 1.

Contando el ahorro de bits

Con los códigos de Huffman, codificar AABBBCCCC cuesta:

A × 2 ocurrencias × 2 bits = 4 bits
B × 3 ocurrencias × 2 bits = 6 bits
C × 4 ocurrencias × 1 bit  = 4 bits
Total = 14 bits

Con ASCII fijo de 8 bits:

9 caracteres × 8 bits = 72 bits

14 bits frente a 72 bits — una reducción del 81% en este ejemplo de juguete. Las ganancias reales son menores, pero el principio se mantiene. El texto en español típicamente se comprime a 4–5 bits por carácter solo con Huffman, frente a los 8 originales.

La idea clave: los códigos de Huffman son libres de prefijos. Ningún código es prefijo de otro, lo que significa que un decodificador puede reconstruir inequívocamente el flujo original sin separadores. La estructura del árbol en sí se almacena en la cabecera del archivo comprimido para que el decodificador pueda reconstruirlo.

LZ77 y LZ78: explotando secuencias repetidas

Huffman coding trabaja con frecuencias individuales de símbolos. Pero ignora una clase mayor de redundancia: las secuencias repetidas. La palabra "función" en el código fuente lleva 6 bytes cada vez que aparece. Si pudieras reemplazar la segunda y siguientes ocurrencias con un puntero a la primera, ahorrarías significativamente.

Eso es exactamente lo que Abraham Lempel y Jacob Ziv describieron en sus papers de 1977 y 1978, dándonos LZ77 y LZ78.

LZ77: compresión de ventana deslizante

LZ77 mantiene una ventana deslizante — un buffer de datos vistos recientemente. A medida que el codificador procesa nuevos datos, mira hacia atrás por la ventana para encontrar la coincidencia más larga con lo que viene a continuación. Si la encuentra, emite una referencia posterior (desplazamiento, longitud) en lugar de los bytes literales.

Considera codificar la cadena:

abcabc

Procesando abc: sin historial previo, emite literales a, b, c.

Procesando el segundo abc: el codificador mira hacia atrás y encuentra abc comenzando 3 posiciones atrás, con longitud 3. Emite la referencia posterior (desplazamiento=3, longitud=3) en lugar de tres bytes literales.

El decodificador, al ver (3, 3), retrocede 3 posiciones en su buffer de salida y copia 3 bytes — reconstruyendo abc perfectamente.

En una implementación real, la búsqueda de coincidencias está limitada por el tamaño de la ventana (gzip usa una ventana de 32 KB). Una ventana más larga encuentra más coincidencias pero cuesta más memoria y tiempo de búsqueda.

La referencia posterior (desplazamiento, longitud) suele ser de 2–3 bytes. Por lo tanto, reemplazar una secuencia repetida de 10 bytes por una referencia de 2 bytes ahorra 8 bytes. Cuanto más larga sea la coincidencia, mejor será la relación.

LZ78 y LZW

LZ78 construye un diccionario explícito de patrones encontrados en lugar de usar una ventana deslizante. LZW (Lempel-Ziv-Welch), un derivado, se hizo famoso como el algoritmo detrás de la compresión GIF y la utilidad compress de Unix. LZW codifica los patrones como índices de diccionario únicos, haciendo crecer el diccionario sobre la marcha durante la codificación y la decodificación.

DEFLATE: LZ77 más Huffman Coding

DEFLATE, definido en la RFC 1951, combina LZ77 y Huffman coding en secuencia:

1. Paso LZ77: Reemplaza secuencias repetidas con referencias posteriores (desplazamiento, longitud). La salida es un flujo de literales y referencias posteriores.
2. Paso Huffman: Aplica Huffman coding a ese flujo. Los literales frecuentes reciben códigos cortos; los valores de referencia posterior raros reciben códigos más largos.

Las dos técnicas atacan diferentes tipos de redundancia. LZ77 elimina la repetición de largo alcance. Huffman coding elimina entonces la redundancia basada en la frecuencia en lo que queda. Juntas logran ratios de compresión que ninguna por sí sola podría alcanzar.

Los datos DEFLATE se organizan en bloques. Cada bloque puede usar uno de tres modos:

• Sin compresión — para datos donde la compresión expandiría la salida (datos ya aleatorios)
• Códigos Huffman fijos — una tabla de códigos acordada previamente, ahorrando la sobrecarga de almacenar un árbol personalizado
• Códigos Huffman dinámicos — un árbol personalizado optimizado para este bloque específico, almacenado en la cabecera del bloque

El modo dinámico se usa para la mayoría de los datos comprimibles. El codificador analiza el bloque, construye un árbol Huffman óptimo, lo almacena al inicio del bloque y luego codifica los datos usando ese árbol.

Dónde vive DEFLATE en los formatos de archivo reales

ZIP

Los archivos ZIP almacenan cada entrada de forma independiente con su propio flujo comprimido con DEFLATE. Esta compresión por entrada significa que puedes extraer un solo archivo de un ZIP sin descomprimir todo el archivo. El formato ZIP también admite un modo "almacenado" (sin compresión) para archivos que ya están comprimidos.

gzip

gzip envuelve un único flujo DEFLATE con una cabecera (número mágico, OS, hora de modificación) y una suma de verificación CRC32. Es el formato de compresión estándar para HTTP Content-Encoding: gzip y para los archivos .tar.gz. La extensión .gz es siempre un único flujo DEFLATE.

PNG

PNG usa DEFLATE (vía zlib) para comprimir sus datos de píxeles. Antes de la compresión, PNG aplica un paso de filtrado: transforma cada fila de píxeles en diferencias respecto a una predicción (codificación delta). Esto aumenta drásticamente las secuencias y repeticiones que LZ77 puede explotar, mejorando significativamente la compresión. Para capturas de pantalla y diagramas típicos, PNG se comprime al 20–50% del tamaño de los datos de píxeles sin procesar. Las herramientas de compresión de imágenes que exportan PNG dependen de esta cadena de procesamiento.

zlib

zlib es un formato envolvente alrededor de DEFLATE — agrega una cabecera de dos bytes y una suma de verificación Adler-32. Los flujos PDF usan zlib/DEFLATE al comprimir contenido incrustado (la compresión de PDF reduce el tamaño del archivo recomprimiendo o eliminando estos flujos). HTTP, WebSockets y muchos protocolos de red también usan zlib.

JPEG: un enfoque diferente

Vale la pena hacer una pausa aquí porque JPEG usa una estrategia de compresión completamente diferente — una que deliberadamente pierde datos.

JPEG aplica una Transformada Discreta del Coseno (DCT) a bloques de 8×8 píxeles. La DCT convierte los valores de píxeles en componentes de frecuencia (similar a una transformada de Fourier). Los componentes de alta frecuencia — detalles finos — se cuantizan agresivamente (se redondean a valores más burdos o se descartan por completo). Los coeficientes restantes se codifican con Huffman coding, pero el paso de cuantización con pérdidas es lo que hace que JPEG sea mucho más pequeño que PNG para fotografías.

La compensación: JPEG no puede reconstruir perfectamente los píxeles originales. PNG sí puede. Esta es la distinción entre sin pérdida y con pérdida explorada en profundidad en nuestro artículo sobre conversión de archivos con pérdida vs. sin pérdida.

Para una fotografía, JPEG con calidad 80 puede usar el 10% de los bytes que necesitaría un PNG sin pérdida. Para una captura de pantalla con colores planos y bordes nítidos, PNG suele ganar porque los artefactos DCT son visibles y DEFLATE comprime las regiones planas de manera excelente.

Por qué no puedes comprimir más un archivo ZIP

Esta es una fuente común de confusión. Si la compresión funciona encontrando patrones, ¿por qué comprimir un archivo ya comprimido no produce casi nada?

Porque DEFLATE está haciendo su trabajo correctamente. Un flujo DEFLATE bien comprimido parece estadísticamente aleatorio — por diseño. Las referencias posteriores y los códigos Huffman eliminan los patrones predecibles. Lo que queda está cerca del límite de entropía de los datos.

Pasa un segundo compresor sobre él y no encontrará secuencias (LZ77 no encuentra coincidencias largas) ni sesgo de frecuencia (Huffman ve una distribución de símbolos casi uniforme). La entropía ya es de 7,9+ bits por byte. No hay nada más que explotar.

Esta es también la razón por la que nunca deberías comprimir medios ya comprimidos. Envolver un JPEG dentro de un ZIP te cuesta la sobrecarga del ZIP sin ningún beneficio en tamaño. Lo mismo se aplica a MP3, MP4, HEIC — todos son formatos comprimidos que ya están cerca de su techo de entropía.

Comparación de algoritmos

Poniéndolo todo junto

La cadena desde datos sin procesar hasta bytes comprimidos para un archivo gzip tiene este aspecto:

1. Entrada: Flujo de bytes sin procesar (p. ej., un archivo de texto)
2. LZ77: Escanea en busca de referencias posteriores con una ventana deslizante de 32 KB, produciendo un flujo de literales y pares (desplazamiento, longitud)
3. Huffman coding: Construye dos árboles — uno para literales/longitudes, otro para desplazamientos — y codifica la salida de LZ77
4. Bloques DEFLATE: Empaqueta los árboles Huffman y los datos codificados en uno o más bloques
5. Envoltorio gzip: Antepone la cabecera gzip, agrega el CRC32 y el tamaño del archivo original
6. Salida: Archivo .gz, típicamente un 30–70% más pequeño para entradas comprimibles

La descompresión funciona estrictamente a la inversa: analiza la cabecera gzip, lee y reconstruye los árboles Huffman de las cabeceras de bloque, decodifica el flujo Huffman de vuelta a tokens LZ77, aplica referencias posteriores para reconstruir el flujo de bytes original. La descompresión siempre es más rápida que la compresión porque el trabajo duro (buscar coincidencias óptimas, construir árboles óptimos) solo se hace una vez.

Conclusiones clave

• Los archivos son comprimibles porque contienen redundancia — patrones repetidos y frecuencias de símbolos sesgadas.
• La entropía de Shannon establece el piso absoluto: los datos verdaderamente aleatorios no se pueden comprimir porque cada bit ya lleva información.
• RLE maneja la repetición de forma tosca. Huffman coding maneja el sesgo de frecuencia elegantemente. LZ77 maneja la repetición de secuencias de largo alcance.
• DEFLATE encadena LZ77 y Huffman en secuencia, por lo que supera a cualquier algoritmo por sí solo. Es el motor dentro de ZIP, gzip, PNG y los flujos PDF comprimidos con zlib.
• JPEG adopta un enfoque fundamentalmente diferente: cuantización DCT con pérdida seguida de Huffman sin pérdida, intercambiando precisión de píxeles por una reducción de tamaño dramática.
• Comprimir un archivo comprimido no logra nada porque una buena compresión produce una salida de entropía casi máxima.

Comprender estos algoritmos importa cuando estás eligiendo un formato, diagnosticando archivos inesperadamente grandes o depurando una cadena de compresión. La próxima vez que uses la compresión de PDF, extraigas un archivo ZIP o exportes un PNG para la compresión de imágenes, sabrás exactamente lo que el software está haciendo con tus bits.