Compresion de Datos - Como funciona el WinZip

INTRODUCCIÓN

La compresión en términos de tratamiento de la información, consiste en transformar los datos de forma que ocupen un menor espacio en memoria. La información transmitida en datos se puede clasificar de tres formas diferentes de comportamiento.

Relevante

Toda la información que debe tenerse en cuenta para reconstruir con precisión el modelo original de datos.

Irrelevante

Información que por sus características la hace inapreciable para los sentidos del ser humano y resulta susceptible de descarte.

Redundante

Conjunto de datos cíclicos que se pueden clasificar con precisión en un diccionario de patrones redundantes.

Atendiendo a esta clasificación, la compresión de datos se puede clasificar a su vez en dos modelos diferentes.

Reversible

Procesa la información de acuerdo a su frecuencia sin pérdida de datos, permitiendo reconstruir los datos originales con absoluta precisión. Se aplica en cadenas de texto.

Irreversible

Descarta parte de la información que resulta inapreciable a los sentidos de la vista y oído humano. Consigue un nuevo modelo del que no se puede recuperar el objeto primitivo, pero su resultado es prácticamente idéntico al original. Se aplica ventajosamente en imágenes y sonidos, eliminando frecuencias no representativas.

Las utilidades de compresión que todos conocemos y utilizamos en numerosas ocasiones no limitan sus cálculos a un único modelo matemático, y haciendo uso de métodos heurísticos y predicción aplican con éxito diferentes algoritmos dentro del mismo conjunto de datos, consiguiendo ratios de compresión superiores a los que se pueden obtener por el uso de un solo método.

Con la publicación de este artículo pretendo clarificar los fundamentos de los algoritmos de compresión reversibles, con referencia al modelo utilizado por el más nombrado de todos ellos: El algoritmo Huffman.

FUNDAMENTOS

Un algoritmo reversible de compresión de datos tiene por objeto reducir el tamaño de un conjunto de datos relevante y resulta especialmente eficaz en la compresión de texto, utilizando diferentes estructuras de datos y análisis de frecuencias para conseguir su objetivo. Para la correcta comprensión de este documento el lector deberá estar familiarizado con ciertas estructuras de datos y métodos de manipulación; bit-streams, arrays, listas encadenadas y árboles binarios, pues todos ellos intervienen en el proceso de compresión que nos ocupa. No tiene cabida en este documento tratar de representar el código fuente del algoritmo, pues si comprendemos el método, podremos seguir sin dificultad las diferentes versiones de código que se pueden descargar en la web.

Un stream de datos procesado según las normas de Huffman, se transforma en un árbol de frecuencias seguido de un bit-Stream que contiene el patrón de búsqueda de datos en el primero. Paradójicamente esta es la consecuencia de que en algunos casos (Cadenas de poca longitud y bajo grado de libertad entrópica), se produzcan resultados que superan en tamaño a su primitiva, es decir, el tamaño del stream de datos comprimidos es mayor que su propio origen.

Huffman apoya su metodología en el cálculo de entropía de los datos. La entropía se utiliza en física y estadística desde mediados del siglo XIX, aplicado para cuantificar el grado de caos y desorden de un sistema concreto. Básicamente se puede aplicar en otras áreas del conocimiento, y en este caso lo utilizaremos para medir la entropía del sistema a comprimir, consiguiendo implementar una estructura ordenada de frecuencias a partir de la sucesión caótica de caracteres.

METODOLOGIA

El juego de caracteres ASCII se representa por valores comprendidos entre 0 y 255 de tipo byte, así pues podemos representar un carácter por su símbolo (A), por su valor ASCII (65) o por su equivalente binario (01000001); Igualmente debemos mencionar que con la notación binaria de un byte de ocho bits, podemos representar una sucesión de cuatro números con valores comprendidos entre 0-3 o de dos números con valores entre 0-15. Igualmente un bit lo podemos utilizar para determinar falso ‘0’ o verdadero ‘1’; pero que sucede si lo utilizamos para definir el recorrido a seguir para alcanzar un dato dentro de un árbol binario. (0 = Nodo izquierdo; 1 = Nodo derecho). ¿ Localizaremos el dato de 8 bits empleando menos de 8 bits ?; La respuesta es ‘1 = verdadero’

Para comprimir una cadena de caracteres –según Huffman- seguiremos los pasos que se enumeran a continuación:

• Cálculo de la entropía.

• Crear lista ordenada de las frecuencias.

• Convertir lista encadenada en árbol de frecuencia-dato.

• Generar un bit-array con los recorridos de los nodos de frecuencias.

• Construir la cadena comprimida que contendrá el árbol y el bit-array

Entropía.
La aplicación debe recorrer en orden ascendente la cadena de caracteres acumulando en un array tipo Long de 256 elementos la frecuencia de cada carácter contenido en la cadena. Una vez finalizado este proceso se genera un lista encadenada con los valores de todos los caracteres junto a la frecuencia obtenida para cada uno de ellos.

Lista Ordenada.
La lista de valores así obtenida se ordena de menor a mayor.

Árbol de Frecuencias.
Generamos un árbol binario tomando por pares los nodos de la lista, sumando sus frecuencias y desplazando el nuevo nodo dentro de la lista, según el orden establecido, al lugar que le corresponda.

Bit-Array.
Recorremos nuevamente la cadena de caracteres generando una trama de bits con el recorrido necesario para identificar el carácter dentro del árbol.

Comprimida.
Construimos una estructura de datos que recogerá el árbol de frecuencias seguido del bit-array. Esta estructura es la representación comprimida del original.

ENTROPIA de CADENA
Caracter	Frecuencia	Caracter	Frecuencia	Caracter	Frecuencia
''	13	C	6	U	3
O	12	I	6	F	2
A	9	D	5	M	2
T	9	N	5	G	1
R	8	L	4	H	1
E	7	S	4	P	1

Operando recursivamente, obtenemos un árbol con un único nodo raíz que contiene la suma de todas las frecuencias y datos debidamente organizados

Apoyándonos en la estructura e información contenida en el árbol construiremos un bit-array de compresión recorriendo nodos hasta alcanzar el dato deseado, apilando ‘0’ para desplazamientos izquierda y ‘1’ para desplazamientos derecha.

Por ejemplo, el primer carácter de la cadena es (N) y para llegar a él es necesario recorrer 5 nodos a la derecha, por lo tanto su valor transformado será ‘11111’ y operando de igual forma conseguimos como resultado la siguiente trama.

N	11111	L	11110	T	000
O	100	E	1100	A	001
S	11011		101	R	1110
O	100	F	110101	E	1100
T	000	A	001	M	0101011
R	1110	C	0111	O	100
O	100	I	0110	S	11011
S	11011	L	11110		101
	101	I	0110	D	0100

El cálculo de entropía de los datos permite organizarlos de forma adecuada para una compresión eficiente, disponiendo los datos más frecuentes próximos al nodo raíz. Es evidente que si los caracteres que más se repiten en la cadena ocupan el tercer nivel del árbol, su transformada ocupara una trama de 3 bits, los que ocupan el cuarto, 4 bits y así sucesivamente con el consiguiente ahorro de memoria. Se puede comprobar en el gráfico como los caracteres T, A, O y ‘ ‘ ocuparán 3 bits en lugar de los 8 bits que ocuparían si los tratásemos como tipo char o byte.

Concatenando el bit-array para formar bytes de 8 bits conseguimos una compresión de 89 bytes en tan solo 14 bytes tal y como se puede comprobar en la siguiente tabla. Lamentablemente en este ejemplo se cumple la excepción en la que la cadena comprimida ocupa más memoria que la original, pues a los 14 bytes hemos de sumar obligatoriamente los 105 que ocupa el árbol de frecuencias, obteniendo como resultado una cadena de 119 bytes.

252	220	29	55	125	151	82
11111100	11011100	00011101	00110111	01111101	10010111	01010010
237	230	7	177	92	221	64
11101101	11100110	00000111	10110001	01011100	11011101	01000000

Una vez se comprende el funcionamiento de compresión no resultará complicado comprender el mecanismo de descompresión, ya que su mecánica se limita a recorrer nuevamente el árbol de frecuencias almacenado de acuerdo a las direcciones ofrecidas por la trama de bits, hasta conseguir un nodo informado.

Si seguimos la trama de la tabla, comprobaremos que los 5 primeros bits nos conducen al carácter ‘N’, los tres siguientes a ‘O’ los siguientes 5 a ‘S’......y así hasta agotar la trama, momento en el que dispondremos de la cadena descomprimida sin pérdida de datos.

CONCLUSIONES

De lo expuesto hasta el momento se pueden extraer ciertas conclusiones que nos ayudarán a comprender los mecanismos de compresión, y probablemente aplicar eficientemente alguno de sus métodos en otro tipo de aplicaciones.

Un algoritmo reversible funcionará satisfactoriamente siempre que el grado de libertad entrópica sea elevado, en otras palabras, un conjunto de caracteres con pequeña desviación (0 a 9; A-Z y a-z) y elevada redundancia, produce estructuras equilibradas, bit-arrays pequeños y como consecuencia elevados ratios de compresión. Ahora nos resultará fácil comprender la razón por la cual en ficheros de tipo imagen y/o binarios, no se obtienen elevados porcentajes de compresión, obligando a utilizar métodos irreversibles para conseguir el objetivo perseguido.

BIBLIOGRAFÍA

Mathematichal Theory of communication. - Shanon & Weaver

Entropía. - J.L. Piñuel Raigada. Universidad Complutense de Madrid.

Compresión de Imágenes. - S. Sierra Llamazares & J.A. Martínez Heras

Datos del Autor

Nombre
     Leonardo Pradera Osterman
Ubicación
     Madrid - España

Nota del Webmaster
    Leonardo (Acalanto) se ha convertido desde los comienzos de VB-MUNDO en un engranaje fundamental del sitio. Sus conocimientos, Participaciones y lecciones brindados en el foro son sin duda de las delicias de los usuarios
Este amigo Ingeniero posee excelentes conocimientos en el desarrollo de aplicaciones para ingeniería civil y ha desarrollado numerosos aplicativos para ese rubro.

Si quieres conocer más sobre Leonardo haz clic aquí
Si quieres acceder a nuestro exclusivo foro haz clic aquí