Algoritmo de Compresión de Huffman

El algoritmo de compresión de Huffman se basa en asignar una longitud variable a cada carácter en función de la frecuencia en que aparece en el archivo. Cuanto mas aparezca un carácter menor será su tamaño.

Pasos del algoritmo:

1. Calcular las veces que aparece cada carácter (o elemento) del archivo.
2. Ordenarlos de menor a mayor.
3. Cada elemento se convierte en un árbol (de un solo elemento).
4. Mientras la lista tenga mas de un elemento:
0. Sacar los dos primeros arboles formando un nuevo árbol con ellos.
1. Sumar sus frecuencias.
2. Insertar ordenadamente el árbol en la lista.

5. Los códigos en binario de cada carácter se asignan en función del camino a recorrer en el árbol. Si en el recorrido se toma una rama izquierda se pone un 1 y si se coge una rama derecha se pone un 0, así hasta llegar al elemento.

Por ejemplo para el texto:  

ABRACADABRAPATADECABRA

Las frecuencias saldrían ya ordenadas:

(E, 1) (T, 1) (P,1) (D, 2) (R,3) (B,3) (A,9)

Y el árbol resultante:

Haciéndolo así, los códigos de los caracteres serian:

Para descomprimir un archivo así comprimido se tiene una tabla con la codificación de los caracteres. Se va leyendo bit a bit hasta que localicemos una subcadena que se encuentre en la tabla, la sustituimos por su carácter y seguimos leyendo el siguiente bit. Este algoritmo funciona ya que para un carácter solo hay un recorrido posible en el árbol y dado un recorrido solo hay un carácter posible que lo cumpla.

Un problema que puede surgir con este algoritmo es que la cabecera, la tabla de conversión, sea mayor que los datos comprimidos. Esto pasa para cadenas de texto pequeñas con lo que al final ocupa más comprimido que sin comprimir.

Para solucionarlo se usa la compresión estadistica. Para textos de caracteristicas parecidas se tienen frecuencias de letras tambien parecidas. Por ejemplo en los textos en ingles la letra que más aparece es la 'e' ("El escarabajo de Oro", Edgar A. Poe) Usando este conocimiento se puede prescindir de tener en la cabecera la tabla de conversión. En vez de eso se pondría un indicativo del tipo de texto comprimido. Ejemplos serian texto normal, texto cientifico, texto html y los diferentes idiomas.

El Autor 1

"¿Hace mucho que estás loco? No, realmente no era un buen comienzo. Rincewind estaba intentando encontrar una forma de entablar conversación, pero no conseguía decidirse por ninguna."

Terry Pratchett

1. Este texto es una versión libre de apuntes de clase. La parte de compresión estadistica es propia.