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:

juanma@garfield:~/opr> ls -l gzip_1.2.4.tar
-rw-------   1 juanma   juanma     368640 Mar  7 02:30 gzip_1.2.4.tar
juanma@garfield:~/opr> gzip gzip_1.2.4.tar
juanma@garfield:~/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

COMPARTIR EN FACEBOOK
COMPARTIR EN TWITTER
COMPARTIR EN LINKEDIN
COMPARTIR EN WHATSAPP
ARTÍCULO ANTERIOR

SIGUIENTE ARTÍCULO