El algoritmo de huffman. « El blog de Daniel Muñoz

7jul/100

El algoritmo de huffman.

(ver la implementación del algoritmo de huffman en c++)

El algoritmo de Huffman es un algoritmo de compresión de información. Este algoritmo está basado en la idea de que algunos caracteres aparecen muchas más veces que otros. Es especialmente eficaz en archivos de texto, donde más de la mitad de los caracteres difícilmente aparezcan alguna vez. Y entre los caracteres que aparecen, hay algunos que aparecen mucho más que otros.

Cada caracter se almacena en una secuencia de 8 bits. Este algoritmo se encarga de asignar códigos más cortos a los caracteres que más se repiten, y códigos más largos a los que menos se repiten. De esta manera a cada caracter se le asigna una longitud que puede variar entre 1 y 255 bits.

¿Cómo se hace esto?

Mediante un árbol binario. Veamos un ejemplo.

Supongamos que en un archivo tenemos el texto: “mi mama me mima”. Este texto ocupa 120 bits (15 bytes). Lo que propone el algoritmo de Huffman es lo siguiente:

Contemos cuantas veces aparece cada letra: m(6), i(2), “espacio”(3), a(3), e(1) (De ahora en adelante llamemos “~” al “espacio” para hacer las cosas más faciles).
Ordenamos las letras por su frecuencia, de mayor a menor:
m(6)~(3)a(3)i(2)e(1)
Sumamos las últimas dos “hojas”, y en su lugar ponemos un “nodo” que tendrá la frecuencia de las dos hojas sumadas (y hagamos esto sucesivamente).

m(6)   ~(3)   a(3)   (3)// Sumamos.
/ \
i(2) e(1)

m(6)   ~(3)   (6)// Sumamos.
/ \
a(3) (3)
/ \
i(2) e(1)

m(6)   (6)   ~(3)// Reordenamos por frecuencia.
/ \
a(3) (3)
/ \
i(2) e(1)

m(6)   (9)// Sumamos.
/ \
(6) ~(3)
/ \
a(3) (3)
/ \
i(2) e(1)

(15)// Reordenamos y sumamos.
/ \
(9) m(6)
/ \
(6) ~(3)
/ \
a(3) (3)
/ \
i(2) e(1)
Ahora debemos crear una convención. En este ejemplo, convengamos: “0” a la izquierda y “1” a la derecha. De esta manera debemos recorrer el árbol hasta las hojas para crear los códigos de los caracteres. Por ejemplo, el carácter “i” está a: izquierda-izquierda-derecha-izquierda. Esto equivale a: 0010. Podemos hacer lo mismo con los otros, y obtendríamos estos códigos:
m = 1.
~ = 01.
a = 000.
i = 0010.
e = 0011.
Y ahora nos resta leer el archivo y por cada caracter leído escribir su correspondiente código en el archivo de salida. Para hacerlo más simple para nuestro análisis humano pondremos un punto entre cada código, pero en el archivo lo escribiremos todo junto. En el caso de “mi mama me mima”, tendríamos un archivo de salida así:
1.0010.01.1.000.1.000.01.1.0011.01.1.0010.1.000.
Esto suma un total de 33 bits. Mucho menos que el archivo original de 120 bits.

¿No habrá ambigüedades?

Ahora, como el lector sabe que en el archivo no escribiremos los puntos, se estará preguntando: ¿Y que pasa si al leer la información comprimida imagino los puntos en otras ubicaciones, que voy a interpretar?.

Hagamos la prueba, no le pongamos ningún punto: 100100110001000011001101100101000.

Pero recordemos seguir esta regla: Teniendo el árbol “a mano” situémonos en el nodo principal y vayamos leyendo la información. Cada vez que leamos un bit, movámonos al nodo inferior que esté a la derecha o a la izquierda según indique el bit. Cuando nos encontremos con que nos movimos a una hoja en vez de a un nodo, escribamos el carácter de la hoja, movámonos al principio del árbol y sigamos leyendo bit por bit desde donde nos habíamos quedado. Repitamos este proceso hasta el último bit.

Esto es lo que leeremos para nuestro ejemplo:

Derecha (hoja). Ponemos la m. Volvemos arriba.
Izquierda-izquierda-derecha-izquierda (hoja). Ponemos la i. Volvemos arriba.
Izquierda-derecha (hoja). Ponemos ~. Volvemos arriba.
Etc…

Al final habremos formado: mi mama me mima. Y no habrá posibilidades de formar otra frase con ese árbol y esa secuencia de bits. Haga algunos intentos y quedará convencido de que es así.

Debemos notar que para cada archivo habrá un árbol diferente de acuerdo a las frecuencias de los caracteres en ese archivo en particular, y una secuencia de bits diferente de acuerdo a la ubicación de los caracteres.

Ahora el lector habrá notado que el descompresor abre el archivo comprimido y “ve” la secuencia de bits, pero se estará preguntando ¿cómo sabe el descompresor cual es el árbol de ese archivo? ¡Claro, habíamos dicho que para cada archivo hay un árbol y una secuencia de bits diferentes! Así que el descompresor también deberá conocer el árbol.

Guardando el árbol.

Veamos una manera sencilla de guardar el árbol, aunque no es tan sencillo explicarlo.

Para guardar la secuencia de bits nosotros sabíamos si estábamos en un nodo o en una hoja, y lo que anotábamos era la dirección hacia la que nos movíamos.

Ahora hagamos justamente lo opuesto. Recorramos el árbol en una dirección (secuencia) conocida y anotemos si estamos en un nodo o en una hoja, y si estamos en una hoja anotemos su caracter.

Para eso convengamos esta regla: Cada nodo/hoja al ser llamado anotará un 1 si es una hoja y un 0 si es un nodo. Luego si es una hoja anotará los 8 bits que representan el caracter de esa hoja. Y si es un nodo, llamará al nodo/hoja de la izquierda y luego al de la derecha para que hagan lo mismo (recursivamente). Por último, después de hacer todo lo que tiene que hacer, devolverá “el mando” al nodo que lo llamó.

De esta forma nuestro árbol de ejemplo (más abajo) quedaría guardado así:

(15) dice: Soy nodo, escribo 0. Llamo a nodo (9)
(9) dice: Soy nodo, escribo 0. Llamo a nodo (6).
(6) dice: Soy nodo, escribo 0. Llamo a hoja a(3).
a(3) dice: Soy hoja, escribo 1. Escribo mi código: 01100001. Retorno a (6).
(6) dice: Ahora llamo a nodo (3).
(3) dice: Soy nodo, escribo 0. Llamo a hoja i(2).
i(2) dice: Soy hoja, escribo 1. Escribo mi código: 01101001. Retorno a (3).
(3) dice: Ahora llamo a hoja e(1).
e(1) dice: Soy hoja, escribo 1. Escribo mi código: 01100101. Retorno a (3).
(3) dice: Retorno a (6).
(6) dice: Retorno a (9).
(9) dice: Ahora llamo a hoja ~(3).
~(3) dice: Soy hoja, escribo 1. Escribo mi código: 00100000. Retorno a (9).
(9) dice: Retorno a (15).
(15) dice: Ahora llamo a hoja m(6).
m(6) dice: Soy hoja, escribo 1. Escribo mi código: 01101101. Retorno a (15).
(15) dice: Terminamos (retorno a quien sea que haya preguntado el código del árbol).

Árbol:

(15)
/ \
(9) m(6)
/ \
(6) ~(3)
/ \
a(3) (3)
/ \
i(2) e(1)

Tamaño de la descripción del árbol.

El código que se acaba de generar sería el siguiente:

0001011000010101101001101100101100100000101101101 (49 bits).

Éste código debe ir antes que la secuencia de bits del archivo para que el descompresor pueda armar el árbol antes de leer la secuencia de bits. En total el archivo generado tendrá 82 bits. Esto equivale a 10,25 bytes. Pero como no podemos guardar medio byte, tendremos que redondear a 11 bytes. Así un archivo de 15 bytes quedó reducido a 11 bytes.

Note el lector que casi el 60% del archivo comprimido está ocupado por la descripción del árbol. Ya que una descripción de árbol varía entre los 0 bits, en caso de un archivo vacío, y los 2559 bits (320 bytes), en caso de que un caracter se repita más que todos los otros juntos, y que el siguiente que más se repite se repita más que todos los otros que se repiten menos que él juntos y así sucesivamente, vemos que la descripción del árbol ocupará a lo sumo 320 bytes.

Esto es prácticamente insignificante para archivos de varios KB, por lo tanto el porcentaje de compresión va a ser mayor que para este ejemplo ya que aquí más del 59,75% del archivo es la pura descripción del árbol, (en este caso es muy significante).

Leyendo la descripción del árbol.

Para descomprimir el archivo basta armar el árbol a medida que vamos leyendo su descripción. Dejémoslo como tarea para el lector… Está bien, hagámoslo juntos. En la descripción leemos:
0: Dibujamos un nodo.
( )
/ \

0: Dibujamos otro nodo.
( )
/ \
( )
/ \

0: Dibujamos otro nodo.
( )
/ \
( )
/ \
( )
/ \

1: Dibujamos una hoja y leemos los 8 bits de su código (01100001=a).
( )
/ \
( )
/ \
( )
/ \
a( )

Nos movemos al próximo lugar vacío y leemos: 0: dibujamos un nodo.
( )
/ \
( )
/ \
( )
/ \
a( ) ( )

1: Dibujamos una hoja y leemos los 8 bits de su código (01101001=i).
( )
/ \
( )
/ \
( )
/ \
a( ) ( )
/ \
i( )

1: Dibujamos una hoja y leemos los 8 bits de su código (01100101=e).
( )
/ \
( )
/ \
( )
/ \
a( ) ( )
/ \
i( ) e( )

1: Dibujamos una hoja y leemos los 8 bits de su código (00100000=~).
( )
/ \
( )
/ \
( ) ~( )
/ \
a( ) ( )
/ \
i( ) e( )

1: Dibujamos una hoja y leemos los 8 bits de su código (01101101=m).
( )
/ \
( ) m( )
/ \
( ) ~( )
/ \
a( ) ( )
/ \
i( ) e( )

El nodo principal devuelve el control al que lo llamó. Y podemos ver que esto ocurre justamente cuando se terminan los bits. No hay ambigüedades.

Esto es todo.

Bueno, con esta información ya somos capaces de comprimir y descomprimir archivos mediante el algoritmo de Huffman. Ahora veremos como implementar el algoritmo de huffman en c++.