Toda persona que utilice Internet se habrá dado cuenta de lo importante que es comprimir la información antes de enviarla a través de la red. Un nuevo modo de comprimir datos puede originar a veces a una auténtica revolución en mundo del internet, como ha ocurrido con el formato mp3. Pero la compresión de datos es un problema matemático cuya importancia va más allá de estas aplicaciones y afecta a cuestiones tan fundamentales como la definición objetiva del azar.
Claude Shannon demostró que el tamaño mínimo al que se puede reducir un fichero de datos es igual a su incertidumbre o entropía y mostró la manera de calcular esta entropía en casos sencillos. Uno de los algoritmos de compresión más conocido es el llamado de Lempel-Ziv (LZ), desarrollado por Abraham Lempel and Jacob Ziv. El programa compress del sistema operativo UNIX y todos los programas que generan ficheros .arj, .zip o .gif en Windows utilizan variantes suyas. Lo que hace el algoritmo es aprovechar de forma bastante simple las repeticiones de ciertas “frases” que aparecen en una cadena de bit, es decir, en una cadena de dígitos 0 o 1. Para ello se fragmenta primero la cadena de modo que no aparezca la misma frase dos veces. Esto se consigue colocando comas de forma sucesiva: se coloca una coma después del primer dígito; la siguiente se coloca de modo que el fragmento entre comas resultante sea el más corto posible que no haya aparecido antes.
Por ejemplo, en la cadena de bit: 1011100010101010100
La fragmentación proporcionará:
1,0,11,10,00,101,01,010,100
Se puede observar que cada fragmento es siempre la concatenación de un fragmento aparecido con anterioridad y de un bit 0 o 1. Los llamaremos fragmento prefijo y bit adicional, respectivamente.
Por ejemplo, el tercer fragmento, 11, es el primero seguido de un 1; el sexto fragmento, 101, es el cuarto seguido de un 1; y así sucesivamente. Podemos ahora numerar los fragmentos y sustituir cada uno de ellos por el número del prefijo y por el bit adicional. El 0 indicará por convención la falta de prefijo o “prefijo vacío”. En nuestro ejemplo: (0,1),(0,0),(1,1),(1,0),(2,0),(4,1),(2,1),(7,0),(4,0) Finalmente se representan en binario los números que indican el prefijo para obtener una nueva cadena de bit. Veamos cómo se realiza este paso en nuestro ejemplo. Como hemos utilizado siete prefijos, se necesitan tres bit para representar cada uno de ellos:
(000,1),(000,0),(001,1),(001,0),(010,0),(100,1),(010,1), (111,0),(100,0)
Ahora se pueden quitar los paréntesis y las comas
y obtener así la cadena de bit comprimida:
000100000011001001001001010111101000.
0 comentarios:
Publicar un comentario