El algoritmo de Huffman es un algoritmo para la construcción de códigos de Huffman, desarrollado por David A. Huffman en 1952 y descrito en A Method for the Construction of Minimum-Redundancy Codes.
Este algoritmo toma un alfabeto de n símbolos, junto con sus frecuencias de aparición asociadas, y produce un código de Huffman para ese alfabeto y esas frecuencias.
El algoritmo consiste en la creación de un árbol binario que tiene cada uno de los símbolos por 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 a él.
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:
Para obtener un símbolo a partir de un código se debe hacer así:
En la práctica, casi siempre se utiliza el árbol para obtener todos los códigos de una sola vez; luego se guardan en tablas y se descarta el árbol.
La tabla describe el alfabeto a codificar, junto con las frecuencias de sus símbolos. En el gráfico se muestra el árbol construido a partir de este alfabeto siguiendo el algoritmo descrito.
Se puede ver con facilidad cuál es el código del símbolo E: subiendo por el árbol se recorren ramas etiquetadas con 1, 1 y 0; por lo tanto, el código es 011. Para obtener el código de D se recorren las ramas 0, 1, 1 y 1, por lo que el código es 1110.
La operación inversa también es fácil de realizar: dado el código 10 se recorren desde la raíz las ramas 1 y 0, obteniéndose el símbolo C. Para descodificar 010 se recorren las ramas 0, 1 y 0, obteniéndose el símbolo A.
Para poder utilizar el algoritmo de Huffman es necesario conocer de antemano las frecuencias de aparición de cada símbolo, y su eficiencia depende de lo próximas a las frecuencias reales que sean las estimadas. Algunas implementaciones del algoritmo de Huffman son adaptativas, actualizando las frecuencias de cada símbolo conforme recorre el texto.
La eficiencia de la codificación de Huffman también depende del balance que exista entre los hijos de cada nodo del árbol, siendo más eficiente conforme menor sea la diferencia de frecuencias entre los dos hijos de cada nodo.
Ejemplos:
Una manera de resolver este problema consiste en agrupar los símbolos en palabras antes de ejecutar el algoritmo. Por ejemplo, si se tiene la cadena de longitud 64
El algoritmo de Huffman aplicado únicamente a los símbolos devuelve el código:
También de longitud 64. Sin embargo, si antes de utilizar el algoritmo, se agrupan los símbolos en las palabras "AA", "AB" y "B" (que se codifican como 1, 01 y 00), el algoritmo devuelve la siguiente cadena:
que tiene longitud 33, la mitad que si no se hubiera agrupado. Si observa el árbol de Huffman, se puede comprobar que la diferencia de frecuencias entre las ramas del árbol es menor que en el caso anterior.
Es posible crear códigos de Huffman ternarios, cuaternarios, y, en general, n-arios. Para ello solo es necesario realizar dos modificaciones al algoritmo:
Escribe un comentario o lo que quieras sobre Algoritmo de Huffman (directo, no tienes que registrarte)
Comentarios
(de más nuevos a más antiguos)