¿Por qué algunos archivos se comprimen más que otros?

Para explicar este fenómeno voy a hacer uso de una medida estadística inventada por E. Shannon llamada entropía de la información. Esta herramienta matemática nos permite medir la cantidad de información de algo.

Las aplicaciones de la entropía dentro y fuera de la informática son infinitas. Dentro de la informática se puede usar en compresión, reconocimiento del habla, reconocimiento de textos, predicción del tiempo, etc. En arqueología, por ejemplo, para conocer si símbolos antiguos pertenecen a un lenguaje. En biología para calcular la cantidad de información del ADN. En física, para calcular el desorden de un sistema de partículas (en este último caso calcula de forma ligeramente distinta y se llama entropía termodinámica) y un largo etc.

Para entender la entropía supongamos que tenemos un lenguaje formado por símbolos. Estos los podemos definir como más nos convenga, es decir, pueden ser palabras, caracteres o grupos de caracteres. Veamos un ejemplo donde el conjunto de símbolos posibles está formado por las palabras "Sí" y "No". A continuación generaremos un mensaje de este lenguaje y calcularemos su entropía. En el mensaje cada símbolo nos indicará si nos ha tocado algo o no en la lotería por cada vez que jugamos:

M="No No No No Sí No No No No No"

Como el mensaje "No" aparece 9 veces, la probabilidad de que aparezca un "No" es 9 entre los 10 símbolos que aparecen en el mensaje P(No)=9/10=0,9.

Mientras que la probabilidad del mensaje "Sí" es de P(Sí)=1/10=0,1

Con estos datos ya podemos calcular la entropía del mensaje denotada por H(M), esta nos dará un valor entre 0 y log₂(número de símbolos)=log₂(2)=1 que nos indicará la cantidad de información que contiene:

H(M)=-(P(No)*log₂(P(No))+P(Sí)*log₂(P(Sí))=

-(0,9*log₂(0,9)+0,1*log₂(0,1))=0,46 bits promedio por símbolo.

Estos 0,46 bits representan la cantidad de información promedio que contienen los símbolos del mensaje. También se puede definir estadísticamente como la esperanza de la incertidumbre del mensaje. En este caso como es difícil que nos toque algo en la lotería, la incertidumbre de que no nos toque es poca I(No)=-log₂(0,9)=0,15, ya que vamos a dudar poco de que salga "No" al ser lo más probable, y la de que sí toque es alta I(Sí)=-log₂(0,1)=3,32, porque es muy difícil predecir si nos tocará, por lo tanto la entropía nos da un valor de la cantidad media de esta incertidumbre. Ahora sigamos con el tema principal ¿por qué no se puede comprimir un archivo varias veces hasta que ocupe poco?

Cuando se aplica un algoritmo de compresión como el Lempel Ziv sobre un archivo, se cambia la codificación agrupando símbolos del lenguaje y asignando otros símbolos más cortos a las combinaciones más probables. La codificación es simplemente cambiar un símbolo por otro, por ejemplo, para el mensaje anterior podríamos usar la siguiente codificación:

"No No" equivale a 0

"Sí No" equivale a 1

Por lo que el mensaje comprimido M' quedaría así:

M'=00100

El tamaño del mensaje es menor. Sin embargo, si os fijaís, para recuperar el mensaje original, necesitamos guardar también información adicional para saber como descodificar cada símbolo, por lo que en este caso no ganamos espacio debido a lo que ocupa esta información adicional, por lo tanto ya sabemos que si comprimimos un archivo muy pequeño no vamos a reducir mucho el tamaño.

En la práctica los archivos no suelen ser tan pequeños y comprimirlos sí permite ganar espacio, ya que la información adicional que se guarda para descomprimirlo es poca en comparación con el tamaño total del archivo.

Entonces, ¿por qué algunos archivos grandes no reducen su tamaño al comprimirlos? Para responder a esta pregunta quiero que os fijéis en otro efecto que se ha producido en el archivo comprimido anterior, la entropía del nuevo mensaje generado ha aumentado. Quedaría así:

P(0)=4/5=0,8

P(1)=1/5=0,2

H(M')=-1*(P(0)*log₂(P(0))+P(1)*log₂(P(1)))=0,72 bits promedio necesarios para codificar cada símbolo

Ahora el mensaje contiene más información y por lo tanto es más difícil comprimirlo. Si lo volviésemos a comprimir no sólo no ocuparía menos, si no que ocuparía más aún, debido a la información adicional que habría que añadir para descomprimirlo y a que la entropía no puede condensarse mucho más.

En conclusión, los lenguajes que contienen mucha información como los que podemos encontrar dentro de un archivo ya comprimido en ZIP, RAR, JPEG, MP3, etc. obtienen valores altos de entropía. Mientras que lenguajes con mucha repetición de palabras o símbolos, por ejemplo, una conversación de chat, un documento de texto, una página Web, un archivo WAV, etc. darán valores muy bajos de ésta. Si la entropía es baja podremos comprimir más la información, construyendo con otros símbolos un mensaje más breve con la información más condensada, por otro lado, si es alta no podremos hacer nada para comprimirla, ya que al intentarlo haremos que ocupe más, debido a que el mensaje ocupará más o menos lo mismo y tendremos que añadir la información necesaria para descomprimirlo.