Compresión sin pérdidas

Los algoritmos de compresión de datos sin pérdidas no pueden garantizar la compresión de todos los conjuntos de datos de entrada. En otras palabras, para cualquier algoritmo de compresión de datos sin pérdidas, habrá un conjunto de datos de entrada que no se hace más pequeño cuando es procesado por el algoritmo, y para cualquier algoritmo de compresión de datos sin pérdidas que hace al menos un archivo más pequeño, habrá al menos un archivo que hace más grande. Esto se puede demostrar fácilmente con matemáticas elementales utilizando un argumento de recuento, de la siguiente manera:

• Suponga que cada archivo se representa como una cadena de bits de alguna longitud arbitraria.
• Suponga que existe un algoritmo de compresión que transforma cada archivo en un archivo de salida que no es más largo que el archivo original, y que al menos un archivo se comprimirá en un archivo de salida que es más corto que el archivo original.
• Sea M el menor número tal que existe un archivo F con longitud M bits que se comprime a algo más corto. Sea N la longitud (en bits) de la versión comprimida de F.
• Porque N<M, todo archivo de longitud N mantiene su tamaño durante la compresión. Hay 2N archivos de este tipo posibles. Junto con F, esto hace 2N+1 archivos que se comprimen todos en uno de los 2N archivos de longitud N.
• Pero 2N es más pequeño que 2N+1, así que por el principio de encasillamiento debe haber algún archivo de longitud N que sea simultáneamente la salida de la función de compresión en dos entradas diferentes. Ese archivo no puede descomprimirse de forma fiable (¿cuál de los dos originales debería producirse?), lo que contradice la suposición de que el algoritmo era sin pérdidas.
• Por tanto, debemos concluir que nuestra hipótesis original (que la función de compresión no alarga ningún archivo) es necesariamente falsa.

Cualquier algoritmo de compresión sin pérdidas que acorte algunos archivos debe necesariamente alargar algunos archivos, pero no es necesario que esos archivos se alarguen mucho más. La mayoría de los algoritmos de compresión prácticos proporcionan una función de «escape» que puede desactivar la codificación normal de los archivos que se alargarían al ser codificados. En teoría, sólo se necesita un único bit adicional para indicar al descodificador que la codificación normal se ha desactivado para toda la entrada; sin embargo, la mayoría de los algoritmos de codificación utilizan al menos un byte completo (y normalmente más de uno) para este propósito. Por ejemplo, los archivos comprimidos con deflación nunca necesitan crecer más de 5 bytes por cada 65.535 bytes de entrada.

De hecho, si consideramos archivos de longitud N, si todos los archivos fueran igualmente probables, entonces para cualquier compresión sin pérdidas que reduzca el tamaño de algún archivo, la longitud esperada de un archivo comprimido (promediada sobre todos los posibles archivos de longitud N) debe ser necesariamente mayor que N. Así que si no sabemos nada sobre las propiedades de los datos que estamos comprimiendo, bien podríamos no comprimirlos en absoluto. Un algoritmo de compresión sin pérdidas sólo es útil cuando tenemos más probabilidades de comprimir ciertos tipos de archivos que otros; entonces el algoritmo podría diseñarse para comprimir mejor esos tipos de datos.

Así, la principal lección del argumento no es que uno se arriesgue a tener grandes pérdidas, sino simplemente que no se puede ganar siempre. Elegir un algoritmo significa siempre, implícitamente, seleccionar un subconjunto de todos los archivos que se volverán útilmente más cortos. Esta es la razón teórica por la que necesitamos tener diferentes algoritmos de compresión para diferentes tipos de archivos: no puede haber ningún algoritmo que sea bueno para todos los tipos de datos.

El «truco» que permite a los algoritmos de compresión sin pérdidas, utilizados en el tipo de datos para los que fueron diseñados, comprimir sistemáticamente dichos archivos a una forma más corta es que los archivos para los que los algoritmos están diseñados para actuar, tienen alguna forma de redundancia fácilmente modelada que el algoritmo está diseñado para eliminar, y por lo tanto pertenecen al subconjunto de archivos que ese algoritmo puede hacer más cortos, mientras que otros archivos no se comprimirían o incluso se harían más grandes. Los algoritmos suelen estar ajustados de forma bastante específica a un tipo de archivo concreto: por ejemplo, los programas de compresión de audio sin pérdidas no funcionan bien con archivos de texto, y viceversa.

En particular, los archivos de datos aleatorios no pueden ser comprimidos de forma consistente por ningún algoritmo concebible de compresión de datos sin pérdidas: de hecho, este resultado se utiliza para definir el concepto de aleatoriedad en la teoría de la complejidad algorítmica.

Es probadamente imposible crear un algoritmo que pueda comprimir sin pérdidas cualquier dato. Aunque a lo largo de los años ha habido muchas afirmaciones de empresas que han logrado una «compresión perfecta» en la que un número arbitrario N de bits aleatorios siempre puede comprimirse a N – 1 bits, este tipo de afirmaciones pueden descartarse con seguridad sin ni siquiera mirar más detalles sobre el supuesto esquema de compresión. Un algoritmo de este tipo contradice las leyes fundamentales de las matemáticas porque, si existiera, podría aplicarse repetidamente para reducir sin pérdidas cualquier archivo a la longitud 0. Los algoritmos de compresión supuestamente «perfectos» suelen denominarse burlonamente algoritmos de compresión «mágicos» por esta razón.

Por otra parte, también se ha demostrado que no existe ningún algoritmo para determinar si un archivo es incompresible en el sentido de la complejidad de Kolmogorov. De ahí que sea posible que cualquier archivo concreto, aunque parezca aleatorio, pueda estar significativamente comprimido, incluso incluyendo el tamaño del descompresor. Un ejemplo son los dígitos de la constante matemática pi, que parecen aleatorios pero pueden ser generados por un programa muy pequeño. Sin embargo, aunque no se pueda determinar si un archivo concreto es incompresible, un simple teorema sobre las cadenas incompresibles muestra que más del 99% de los archivos de cualquier longitud no pueden comprimirse en más de un byte (incluyendo el tamaño del descompresor).

Contexto matemáticoEditar

Abstractamente, un algoritmo de compresión puede verse como una función sobre secuencias (normalmente de octetos). La compresión tiene éxito si la secuencia resultante es más corta que la secuencia original (y las instrucciones para el mapa de descompresión). Para que un algoritmo de compresión sea sin pérdidas, el mapa de compresión debe formar una inyección desde las secuencias de bits «simples» a las «comprimidas».

El principio de encasillamiento prohíbe una biyección entre la colección de secuencias de longitud N y cualquier subconjunto de la colección de secuencias de longitud N-1. Por lo tanto, no es posible producir un algoritmo sin pérdidas que reduzca el tamaño de cada secuencia de entrada posible.

Puntos de aplicación en la teoría de la compresión realEditar

Los diseñadores de algoritmos de compresión real aceptan que los flujos de alta entropía de la información no pueden ser comprimidos, y en consecuencia, incluyen facilidades para detectar y manejar esta condición. Una forma obvia de detección es aplicar un algoritmo de compresión en bruto y comprobar si su salida es más pequeña que su entrada. A veces, la detección se hace por heurística; por ejemplo, una aplicación de compresión puede considerar que los archivos cuyos nombres terminan en «.zip», «.arj» o «.lha» no son comprimibles sin ninguna detección más sofisticada. Una forma común de manejar esta situación es citar la entrada, o partes no comprimibles de la entrada en la salida, minimizando la sobrecarga de compresión. Por ejemplo, el formato de datos zip especifica el «método de compresión» de «Almacenado» para los archivos de entrada que se han copiado en el archivo textualmente.

El reto del millón de dígitos aleatoriosEditar

Mark Nelson, en respuesta a las reclamaciones de algoritmos de compresión mágicos que aparecen en comp.compresión, ha construido un archivo binario de 415.241 bytes de contenido altamente entrópico, y ha lanzado un reto público de 100 dólares a cualquiera que escriba un programa que, junto con su entrada, sea más pequeño que sus datos binarios proporcionados y que, sin embargo, sea capaz de reconstituirlo sin errores.

El FAQ del grupo de noticias comp.compresión contiene un reto de Mike Goldman que ofrece 5.000 dólares por un programa que pueda comprimir datos aleatorios. Patrick Craig aceptó el reto, pero en lugar de comprimir los datos, los dividió en archivos separados que terminaban todos en el número 5, que no se almacenaba como parte del archivo. La omisión de este carácter permitió que los archivos resultantes (más, de acuerdo con las reglas, el tamaño del programa que los reensambló) fueran más pequeños que el archivo original. Sin embargo, no se produjo ninguna compresión real, y la información almacenada en los nombres de los archivos era necesaria para reensamblarlos en el orden correcto en el archivo original, y esta información no se tuvo en cuenta en la comparación del tamaño del archivo. Por lo tanto, los archivos en sí no son suficientes para reconstituir el archivo original; los nombres de los archivos también son necesarios. Patrick Craig estuvo de acuerdo en que no se había producido una compresión significativa, pero argumentó que la redacción de la impugnación no lo exigía realmente. En el sitio web de Patrick Craig hay una historia completa del evento, incluyendo la discusión sobre si el desafío se cumplió técnicamente o no.