Esta es una traducción automática y el texto original está en inglés. Leer el original
Ningún compresor puede reducir todos los archivos, y la demostración ocupa un solo párrafo
Cada pocos años alguien anuncia un algoritmo que comprime cualquier archivo un 50%. Aplicado dos veces comprimiría cualquier archivo a una cuarta parte, y aplicado las suficientes veces, a un solo bit.
Considera todos los archivos posibles de exactamente 1.000 bits. Hay 2¹⁰⁰⁰ de ellos. Ahora considera todos los archivos posibles más cortos que esa longitud: 999 bits, 998 y así sucesivamente hasta llegar a cero. Súmalos y obtendrás 2¹⁰⁰⁰ − 1 archivos, uno menos de los que tenías al principio.
Un compresor sin pérdidas debe asociar entradas distintas a salidas distintas; de lo contrario, no podría revertir el proceso. Pero no es posible meter 2¹⁰⁰⁰ elementos en 2¹⁰⁰⁰ − 1 cajas sin meter dos en la misma caja. Por lo tanto, ningún compresor sin pérdidas reduce todas las entradas. Si reduce algunas, debe expandir otras.
No ha hecho falta asumir nada sobre el algoritmo, por lo que ningún ingenio puede eludir esta regla. Es el principio del palomar, y es la razón por la que cualquier compresor real tiene un peor caso en el que la salida es ligeramente mayor que la entrada: el original más unos pocos bytes de cabecera.
Qué es lo que realmente se aprovecha
La estructura. La compresión no elimina la "redundancia" en un sentido vago; reasigna los códigos cortos a las cosas que ocurren con frecuencia.
El texto en inglés es enormemente predecible. Tras "th", la letra siguiente es abrumadoramente "e". Los espacios son el carácter más frecuente. Una imagen de una pared contiene largas secuencias de píxeles casi idénticos. En cada caso, el archivo, considerado como una variable aleatoria, tiene una entropía baja —la sorpresa media por símbolo es pequeña— y Shannon demostró en 1948 que esta magnitud es la cota inferior exacta. No se puede codificar una fuente en menos bits por símbolo que su entropía, y siempre es posible acercarse arbitrariamente a ella.
Esto convierte la compresión en una competición de predicción. Un compresor que modela bien la fuente asigna códigos cortos con precisión y se sitúa cerca de la entropía. Un compresor que la modela mal desperdicia bits. Por eso el estado del arte en compresión de texto se parece cada vez más a un modelo de lenguaje: predecir bien el siguiente símbolo y comprimir bien son el mismo problema con diferente disfraz.
Se puede observar cómo se aproxima a la cota inferior en la herramienta Entropy Coding y ver la asignación de códigos en Huffman Encoding.
Por qué comprimir un zip no sirve de nada
A un archivo bien comprimido se le ha eliminado la estructura. Lo que queda se parece, estadísticamente, al ruido: todos los símbolos son casi igualmente probables y no existen correlaciones útiles entre vecinos. Su entropía por bit es cercana a 1, por lo que no queda nada que aprovechar, y una segunda pasada por lo general lo hará muy ligeramente más grande: la cabecera, más la incapacidad del compresor para encontrar algún patrón que valga la pena codificar.
Esto mismo explica por qué un JPEG dentro de un archivo ZIP apenas se reduce, por qué los datos cifrados son incompresibles (un buen cifrado está diseñado específicamente para parecer ruido) y por qué comprimir antes de cifrar es el orden correcto: después ya no hay nada que comprimir.
La versión honesta de "un 50% más pequeño"
Toda afirmación verídica sobre compresión es una afirmación sobre una clase de entradas. "Reduce a la mitad el tamaño de la prosa en inglés" es una declaración real y útil. "Reduce a la mitad el tamaño de cualquier archivo" es demostrablemente falso, y la demostración es el párrafo del principio.
Donde la compresión con pérdidas es un asunto totalmente distinto
Nada de esto limita la compresión con pérdidas, porque esta no tiene por qué ser reversible. JPEG, MP3 y todos los códecs de vídeo descartan información deliberadamente, seleccionando qué perder mediante modelos de lo que los ojos y oídos humanos no logran percibir.
Eso cambia la pregunta de "cuánta estructura hay" a "cuánto se puede descartar antes de que alguien se queje", lo cual es una cuestión de percepción más que de matemáticas. Por eso también el compromiso en la compresión con pérdidas tiene un control de ajuste y en la sin pérdidas no: la entropía es un hecho propio de los datos, pero la distorsión aceptable es un juicio sobre la audiencia.
Lo único que ambas comparten es que la especificación sincera es siempre condicional. Un compresor sin pérdidas es bueno para una clase de entradas. Uno con pérdidas es bueno para una distorsión determinada.