Número 2 - NOVIEMBRE 1992

COMPRESION DE DATOS

By Warlord/Impulse

El tema de la compresión de datos, es algo que un programador se suele plantear tarde o temprano, sobre todo si su programa utiliza muchos dibujos o músicas. Y también, tarde o temprano se suele caer en el vicio de comprimir lo ya comprimido. La pregunta en principio, puede parecer lógica: Si tengo un fichero de datos ya comprimido, ¿por qué no puedo comprimirlo de nuevo?. Para responder a esta pregunta, antes hay que explicar un poco como se pueden comprimir los datos.

Lo primero que uno piensa en comprimir, son los espacios en blanco, que suelen abundar en todos los programas. Por ejemplo, podríamos pensar en sustituir espacios en blanco por #No espacios, con lo que ahorraríamos algunos bytes. De todos modos, esto no ahorraría mucho(quizás un 5%) y además habría que tener en cuenta que al descompactar, si se encontrara con el símbolo "#" seguido de un número, lo tomaría como "tantos espacios en blanco", cuando pudiera ser que casualmente indicara otra cosa. El siguiente paso sería en compactar "palabras". Veamos, ¿cuántas veces aparece un artículo en un texto?. Podríamos sustituir "el" por "®" o "la" por "ð", pero si el fichero fuera de datos (sólo números), nada de esto serviría para nada. Vamos pues, a exponer la familias de compresores de datos más conocida internacionalmente:

LEMPEL-ZIV 1977-78 (LZ77-LZ78)

Son las familias de algoritmos más populares de compresores de datos. Son utilizados por ejemplo, en el LHARC o PKZIP, que aunque poco utilizados en el amiga, son muy populares en otros ordenadores y sistemas (pe, UNIX). El algoritmo es bastante simple pero eficaz en determinados casos. Consiste en sustituir frases repetidas por un cierto código, formando una especie de diccionario formado de frases. Cada frase de este "diccionario" lleva consigo un código que es el que aparece en el fichero comprimido. Las pegas son obvias. En un fichero donde abunden los datos, la compresión sería un fracaso. Hay una numerosa bibliografía sobre este algoritmo pues no en vano, la patente fue adquirida por Unisys.

Esta idea, en principio sencilla de entender ha ido sufriendo importantes modificaciones encaminadas a la optimización de estos compresores, no en vano, el famoso y antes mencionado LHARC es fruto de una de ellas. Consiste en el método antes citado, sólo que usa el llamado "método de Huffman". En este caso, seguiremos sustituyendos frases por códigos, pero contra más veces aparece una frase, menor longitud de código se le asigna. Por ejemplo, la frase más repetida llevaría asignado el bit "1", la siguiente el 01 y así sucesivamente ...

Los modernos algoritmos de compresión, estructuran los datos en forma de árboles y utilizan punteros para cada nodo del árbol. Esta técnica es bastante reciente (1989) y aún no ha sido optimizada ni mucho menos, pero se espera que este sea el desarrollo futuro de estos algoritmos ...