Introducción a la compresión de datos: Lempel-Ziv, Gzip

Seguramente todo el mundo sabe lo que es comprimir datos. Si no lo ha hecho nunca, basta con que busque un fichero, preferiblemente grande (para que el resultado sea más impactante) y de texto (puesto que estos ficheros suelen tener más redundancia que los ficheros binarios) y hacer:

ls -l fichero_grande
gzip fichero_grande
ls -l fichero_grande.gz

Puesto que en este artículo vamos a explicar el método de compresión en el que se basa gzip, resulta interesante comprobar cuánto comprime gzip su propio código fuente. Inicialmente tenemos todo el código fuente archivado en un .tar, que es un formato que sólamente junta ficheros; no los comprime. Veamos lo que ocupa este tar antes y después de la compresión:

[email protected]:~/opr> ls -l gzip_1.2.4.tar
-rw-------   1 juanma   juanma     368640 Mar  7 02:30 gzip_1.2.4.tar
[email protected]:~/opr> gzip gzip_1.2.4.tar
[email protected]:~/opr> ls -l gzip_1.2.4.tar.gz
-rw-------   1 juanma   juanma     103898 Mar  7 02:30 gzip_1.2.4.tar.gz

Hemos pasado de ocupar 368.640 bytes a menos de la tercera parte: 103.898. No está nada mal.

La compresión es posible porque normalmente en una fuente (en este caso el fichero con el código fuente del gzip) además de información hay también redundancia, es decir, datos que no nos aportan más información, en general porque pueden obtenerse a partir de los datos anteriores.

¿Exite un límite en cuanto a lo que podemos llegar a comprimir esos 368.640 bytes, un punto a partir del cual no se pueda reducir ya más el tamaño de la fuente, un punto en el que se haya eliminado toda la redundancia y ya sólo quede información? La intuición nos dice que sí. Si llegáramos a comprimirlo hasta 0 ó 1 byte, parece difícil que seamos capaces de sacar toda esa información -10.460 líneas de código- de ahí.

Dentro de la Teoría de la Información, que es la rama de la ciencia que se ocupa de la compresión de datos, hace tiempo que se ha demostrado que ese límite, efectivamente, existe, y recibe el nombre de entropía.

COMPARTE ESTE ARTÍCULO

ENVIAR A UN AMIGO
COMPARTIR EN FACEBOOK
COMPARTIR EN TWITTER
COMPARTIR EN GOOGLE +
ARTÍCULO ANTERIOR

SIGUIENTE ARTÍCULO

¡SÉ EL PRIMERO EN COMENTAR!
Conéctate o Regístrate para dejar tu comentario.