Codificación Huffman

Teoría de la Información y Métodos de Codificación
Tarea 3

La codificación Huffman es un algoritmo usado para compresión de datos.

El término se refiere al uso de una tabla de códigos de longitud variable para codificar un determinado símbolo (como un carácter), donde la tabla ha sido rellenada de una manera específica basándose en la probabilidad estimada de aparición de cada posible valor de dicho símbolo.

El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos en una hoja, y construido de tal forma que siguiéndolo desde la raíz a cada una de sus hojas se obtiene el código Huffman asociado.

Pasos:

1. Crear un nodo hoja para cada símbolo, asociando un peso según su frecuencia de aparición e insertarlo en la lista ordenada ascendentemente.
2. Mientras haya mas de un nodo en la lista:
   • Eliminar los dos nodos con menor probabilidad de la lista.
   • Crear un nuevo nodo interno que enlace a los nodos anteriores, asignándole como peso la suma de los pesos de los nodos hijos.
   • Insertar el nuevo nodo en la lista, (en el lugar que le corresponda según el peso).
3. El nodo que quede es el nodo raíz del árbol.

Con este árbol se puede conocer el código asociado a un símbolo, así como obtener el símbolo asociado a un determinado código.

Para obtener el código asociado a un símbolo se debe proceder del siguiente modo:

1. Comenzar con un código vacío.
2. Iniciar el recorrido del árbol en la hoja asociada al símbolo.
3. Comenzar un recorrido del árbol hacia arriba.
4. Cada vez que se suba un nivel, añadir al código la etiqueta de la rama que se ha recorrido.
5. Tras llegar a la raíz, invertir el código.
6. El resultado es el código Huffman deseado.

Un ejemplo de un árbol dibujado es el siguiente donde los nodos hijos finales son a los que les corresponde un símbolo y una frecuencia, y los nodos padres de estos últimos se conectan como pequeños árboles a otros nodos. Los nodos con puros números indican la suma de las frecuencias de los nodos hijos correspondientes.

Código

Pruebas con diferentes textos.

El algoritmo de Huffman aplicado sobre un alfabeto de únicamente dos símbolos distintos, asignará siempre un 1 al primero y un 0 al segundo, independientemente de la frecuencia de aparición de dichos símbolos. En este caso, de hecho uno de los peores casos, nunca se realiza compresión de los datos, mientras que otros algoritmos sí podrían conseguirlo.

Otra prueba de ejecución con un texto algo mas extenso que las anteriores.

Referencias:
Codificación Huffman
Ejemplo de Codificación Huffman Python dictionary