1. El principio del palomar: por qué no puede existir un compresor universal que reduzca todos los archivos

Cuando usamos a diario herramientas como zip, gzip, zstd, 7z o PNG para reducir documentos, código fuente o imágenes a una fracción de su tamaño original y al descomprimirlos recuperamos hasta el último bit intacto (compresión sin pérdida / reversible), surge una pregunta intuitiva: si un compresor reduce el tamaño de un archivo, ¿por qué no volvemos a comprimir el archivo .zip resultante diez veces seguidas hasta reducir cualquier película o base de datos a un solo byte?

La respuesta es rotunda: es matemáticamente imposible. Para demostrarlo ni siquiera hace falta recurrir a la teoría de la información avanzada; basta con el principio del palomar (Pigeonhole Principle) de la combinatoria elemental.

Sea $E: \{0,1\}^* \to \{0,1\}^*$ una función de codificación sin pérdida y $D: \{0,1\}^* \to \{0,1\}^*$ su función de decodificación. Para garantizar una reversibilidad exacta $D(E(x)) = x$ para cualquier secuencia binaria $x$, la aplicación $E$ debe ser necesariamente inyectiva (uno a uno): si dos archivos distintos $x_1 \ne x_2$ se comprimieran en la misma cadena corta $y = E(x_1) = E(x_2)$, el decodificador jamás podría saber si debe restaurar $x_1$ o $x_2$.

Consideremos ahora el conjunto de todos los archivos binarios de longitud exacta $N$ bits: existen $2^N$ archivos posibles. En cambio, el número total de cadenas binarias estrictamente más cortas que $N$ bits (de longitud $0$ a $N-1$) es:

Como hay $2^N$ archivos de entrada («palomas») pero solo $2^N - 1$ cadenas más cortas («palomares»), cualquier algoritmo de compresión sin pérdida que acorte al menos un archivo DEBE forzosamente alargar otros! Más aún, la fracción de archivos de $N$ bits que pueden reducirse en al menos $c$ bits cumple:

Casi todas las cadenas binarias aleatorias son algorítmicamente incompresibles. La razón por la que nuestros compresores cotidianos reducen casi cualquier archivo real es que el texto humano, el código fuente y las imágenes naturales habitan un subconjunto minúsculo, altamente estructurado y de baja entropía dentro del océano $\{0,1\}^N$.

2. El teorema de codificación de fuentes de Shannon y la entropía: el límite físico absoluto

En 1948, Claude E. Shannon formuló en «A Mathematical Theory of Communication» el límite fundamental de la compresión. Para una fuente discreta sin memoria que emite símbolos de un alfabeto $\mathcal{A} = \{s_1, \dots, s_m\}$ con probabilidades $P = (p_1, \dots, p_m)$, la autoinformación (Surprisal) de un símbolo $s_i$ y su valor esperado, la entropía de Shannon $H(X)$, vienen dados por:

Todo código libre de prefijos (instantáneo) con longitudes de palabra $\ell_1, \dots, \ell_m$ debe satisfacer la desigualdad de Kraft-McMillan:

Aplicando la no negatividad de la divergencia de Kullback-Leibler $D_{\text{KL}}(P \,\|\, Q) \ge 0$ con $q_i = 2^{-\ell_i}/Z$ ($Z = \sum 2^{-\ell_i} \le 1$), se demuestra el teorema de codificación de fuentes sin ruido de Shannon para la longitud media $L = \sum_{i=1}^m p_i \ell_i$:

  flowchart TD
    A["Flujo de datos original (Texto / Imagen / Binario)"] --> B["Etapa 1: Transformación y modelado por diccionario (BWT / LZ77)"]
    B --> C["Distribución de probabilidad P(s) de símbolos y punteros (distancia, longitud)"]
    C --> D["Etapa 2: Codificación entrópica estadística (Huffman / Aritmética / ANS)"]
    D --> E["Flujo de bits compacto cercano al límite de Shannon N·H(X)"]

3. Tres generaciones de codificación entrópica: Huffman, Codificación Aritmética y ANS

3.1 Codificación de Huffman (1952): árboles de prefijos óptimos de longitud entera

El algoritmo voraz de David A. Huffman construye en tiempo $O(m \log m)$ el árbol libre de prefijos de menor longitud media fusionando iterativamente los dos símbolos menos probables. Su limitación estructural es que cada palabra de código debe tener un número entero de bits ($\ell_i \ge 1$): un símbolo con probabilidad $p_1 = 0,99$ contiene solo $-\log_2(0,99) \approx 0,0145\,\text{bits}$ de información, pero consume al menos $1\,\text{bit}$ entero.

3.2 Codificación Aritmética (Arithmetic / Range Coding): bits fraccionarios

La codificación aritmética (Rissanen, Pasco, Witten et al.) supera la barrera entera representando toda la secuencia del mensaje $x_1 x_2 \dots x_N$ como un único subintervalo $[L_{\text{low}}, H_{\text{high}}) \subset [0, 1)$ cuya anchura final $\Delta = \prod_{t=1}^N P(x_t)$ requiere $\lceil -\log_2 \Delta \rceil + 1 \approx N \cdot H(X)$ bits, logrando bits fraccionarios a cambio de un mayor coste computacional por multiplicación.

3.3 Sistemas Numéricos Asimétricos (ANS, Jarek Duda 2009–2014)

Inventados por el físico e informático polaco Jarek Duda, los Asymmetric Numeral Systems (tANS y rANS) combinan la razón de compresión óptima de la codificación aritmética con la velocidad de tabla de búsqueda de Huffman. Al codificar un símbolo $s$ de probabilidad $p_s$ en el estado entero $x \in \mathbb{N}$, el estado se actualiza según:

Hoy ANS es el motor central de Zstandard (zstd) de Meta, LZFSE de Apple y JPEG XL de Google.

4. Compresión por diccionario y transformaciones: LZ77, DEFLATE, BWT y «Comprimir es predecir»

Para explotar la repetición de subcadenas y la estructura contextual, los compresores modernos combinan diccionarios con codificadores entrópicos:

• LZ77 (Lempel y Ziv, 1977): reemplaza subcadenas repetidas dentro de una ventana deslizante por punteros hacia atrás (distance, length). Junto con Huffman forma DEFLATE (gzip, zip, PNG); junto con ANS forma Zstandard (zstd).
• Transformada de Burrows-Wheeler (BWT, 1994, bzip2): ordena lexicográficamente todas las rotaciones cíclicas de un bloque y toma la última columna $L$, agrupando caracteres con idéntico contexto posterior para que Move-To-Front (MTF) y Run-Length Encoding (RLE) los compriman drásticamente.

  flowchart TD
    A["Flujo de bytes de entrada"] --> B["Búsqueda de la coincidencia más larga en ventana deslizante (LZ77)"]
    B --> C{"¿Longitud de coincidencia >= 3?"}
    C -- "Sí" --> D["Emitir puntero hacia atrás (distance, length)"]
    C -- "No" --> E["Emitir byte literal original (Literal)"]
    D --> F["Codificación entrópica mediante Huffman (DEFLATE) o ANS (Zstandard)"]
    E --> F

En el sentido matemático más profundo, comprimir es exactamente equivalente a predecir: cualquier modelo (incluidos los grandes modelos lingüísticos Transformer) que minimice la entropía cruzada $-\sum \log_2 P_\theta(x_t \mid x_{