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:  

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.

Luis Jose Cabellos