Pensamientos computables - www.pensamientoscomputables.com
110

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

Publicado el: 26/08/2012
compresion archivos
¿Te ha pasado alguna vez que has comprimido un video o una imagen, ya sea en formato gzip, zip o rar y te has encontrado que el archivo comprimido ocupaba más que el original? ¿Quieres saber por qué?

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 log2(número de símbolos)=log2(2)=1 que nos indicará la cantidad de información que contiene:

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

-(0,9*log2(0,9)+0,1*log2(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)=-log2(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í)=-log2(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)*log2(P(0))+P(1)*log2(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.

Pensamientos (4): Ver comentarios Comentar
Categorías: ,

Comparte:

Copia y pega en tu página:

Comparte
Escribe tus pensamientos computables

Respondiendo a los siguientes comentarios:

Para comprobar que eres un humano responde correctamente:

Esta pregunta no me gusta, ¡cambialá!

Ninguno de estos datos será almacenado.

(Escribe el correo electrónico)

Campo obligatorio.

(Escribe el correo eléctronico o los correos electrónicos separados por comas)

Campo obligatorio.

Para comprobar que eres un humano responde correctamente:

Esta pregunta no me gusta, ¡cambialá!

Pensamientos
Anónimo
Fecha: 27/09/2012 Hora: 15:26:10
Estoy muy agradecido por la gran cantidad de información, valga la redundancia, que posee tu artículo. Nunca había visto un artículo tan interesante como éste, más que nada porque me ha introducido en un mundo que desconocía y que por fortuna me da la posibilidad de aumentar mis conocimientos informáticos. Además, me has dado alguna que otra idea para seguir tirando en mi odisea informática. He aquí un lector que vas a tener de por vida. Sigue así, muchas gracias. Un saludo.
Anónimo
Fecha: 13/02/2013 Hora: 6:36:13
Muy interesante, cabe recalcar q he visto un archivo de win xp de 700 mb comprimido a tan solo 10 mb, aun me parece increible como puede pasar esto wao...
Le responde 1 comentario Ver comentario
Respondiendo a 1 comentario Ver comentario
Daiatron
Fecha: 16/02/2013 Hora: 11:37:25
Eso suele pasar con algunas imágenes de DVD o CD que ocupan la totalidad del dispositivo pero en realidad sólo una parte tiene información, el resto son todo ceros, lo que supone mucha información repetida que se puede comprimir facilmente, siendo lo más eficiente en este caso, guardar sólo el número de ceros que encuentre (algoritmo RLE).
Studiosi
Fecha: 24/07/2013 Hora: 10:40:39

La optimalidad de la compresión no sólo depende del tamaño y de los datos añadidos, también depende de la distribución estadística de los símbolos. Usando esta misma teoría se puede demostrar que un flujo de datos en el cual todos los símbolos tengan la misma probabilidad de aparecer será incompresible independientemente de su tamaño.

Buen blog.

Daiatron en Google+