Descripción

     La Códificación Huffman binaria, constituye la versión original y más simple de este conjunto de técnicas.

    Fue planteada por David A. Huffman en el año 1951, en su trabajo "A Method for the Construction of Minimum-Redundancy Codes" durante sus años de estudio en el MIT.

   Como su nombre lo indica, la codificación huffman orientada a bits, produce codigos binarios, generados a partir de un árbol binario.

   Este tipo de codificación se utiliza se orientada principalmente a caracteres o símbolos individuales. Es decir, se obtiene un código único por cada carácter en el texto de entrada. Aunque en algunas ocasiones se utiliza orientado a palabras, es preferible utilizar para estos casos un método orientado a bytes.

Procedimiento

 

1 . Crear un nodo por cada símbolo en el vocabulario de entrada, con su respectiva frecuencia/probabilidad de aparición e  insertarlo en una tabla de nodos (por lo general se utiliza una cola de prioridad para dicha tabla)

2. Se extrae de la tabla de nodos  los dos nodos que presenten la frecuencia más baja, se unen como hijos de un nuevo nodo, como si estos fueran un único símbolo, con frecuencia igual a la suma de las frecuencias de ambos términos y se inserta el nuevo nodo  en la tabla.

3. Se continúa el proceso hasta que solo queden dos nodos en la tabla, en cuyo caso se unen formando la raíz del árbol.

 4. La codificación de los términos se puede obtener, una vez construido el árbol, por medio de un algoritmo recursivo, que recorra el mismo (como Preorden) y vaya asignando los códigos por niveles. También es posible generar los códigos mientras se va construyendo el árbol.

5. Se realiza un mapeo de los símbolos originales, con los códigos obtenidos.

6. Se puede agrupar la codificación en bloques de 8 bits, para ser almacenados como caracteres.

  Ejemplo de árbol resultado del algoritmo (pasos 1 - 4):

                                                                                                             
                                                                                                                                           Tomado de: http://mathworld.wolfram.com/images/eps-gif/HuffmanCoding_701.gif

   En este caso los cuadrados rojos representan los símbolos en el texto de entrada, los números dentro de los cuadrados son las frecuencias de dichos símbolos (los símbolos en sí se obvian, ya que son irrelevantes).

   Los circulos representan nodos intermedios, los cuales corresponden a la unión de dos símbolos de entrada, de un símbolo de entrada con un nodo intermedio, o de dos nodos intermedios. Los números dentro de los círculos representa la suma de las frecuencias de los hijos de dicho nodo.

Ejemplo Completo del Algoritmo

    1. Se cuenta con los símbolos de entrada y su respectiva frecuencia.

  
 2. Se ordenan descendentemente, por su frecuencia.

   3. Se toman los dos símbolos con menor frecuencia y se unen.

   4. Se inserta el nuevo símbolo en la tabla.

   5. Se toman los dos símbolos con menor frecuencia y se unen.

   6. Se inserta el nuevo símbolo en la tabla.

     7. Se toman los dos símbolos con menor frecuencia y se unen.

       

   8. Se inserta el nuevo símbolo en la tabla.

9. Se toman los dos símbolos con menor frecuencia y se unen.

10. Como no quedan símbolos en la tabla se ha terminado de construir el árbol.

11. Se obtienen los códigos para cada símbolo de entrada.

                  

12. Se codifica la entrada utilizando la tabla de códigos.

     Entrada:  “escuela ejemplo casa perro escuela perro”

     Salida:     1010111100101100

     Salida diferenciando cada término: 101_01_11_100_101_100 (cada guión baja separa un término)

13.  Opcionalmente, se puede agrupar la hilera codificada en grupos de 8 bits para ser almacenada como los caracteres    correspondientes (ASCII).  

                 10101111         00101100

Ascii:               ¯                       ,