## 2.3.3 CÓDIGOS DE HUFFMAN

Es un método general de codificación y compresión diseñado para minimizar el número medio de bits necesarios para transmitir un símbolo cuando se debe transmitir varias copias independientes y estadísticamente equivalentes de dicho símbolo. Este método determina cómo los distintos valores del símbolo deben representarse como cadenas binarias.

Fue desarrollado por el norteamericano David Albert Huffman en 1952 mientras hacía el doctorado en el MIT. El método fue publicado en una revista como A Method for the Construction of Minimum-Redundancy Codes. El algoritmo funciona a partir de un conjunto dado de símbolos con sus respectivos pesos. Los pesos son la frecuencia de aparición en una cadena. Por ejemplo en la cadena Algoritmos el peso del símbolo o es 2, ya que aparece en dos ocasiones. La salida del algoritmo es el mismo conjunto de símbolos de entrada codificado mediante un código binario con un tamaño menor.

Descripción

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.

1. Se crean varios árboles, uno por cada uno de los símbolos del alfabeto, consistiendo cada uno de los árboles en un nodo sin hijos, y etiquetado cada uno con su símbolo asociado y su frecuencia de aparición.

2. Se toman los dos árboles de menor frecuencia, y se unen creando un nuevo árbol. La etiqueta de la raíz será la suma de las frecuencias de las raíces de los dos árboles que se unen, y cada uno de estos árboles será un hijo del nuevo árbol. También se etiquetan las dos ramas del nuevo árbol: con un 0 la de la izquierda, y con un 1 la de la derecha.

3. Se repite el paso 2 hasta que sólo quede un á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.

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.

Para obtener un símbolo a partir de un código se debe hacer así:

1. Comenzar el recorrido del árbol en la raíz de éste.

2. Extraer el primer símbolo del código a descodificar.

3. Descender por la rama etiquetada con ese símbolo.

4. Volver al paso 2 hasta que se llegue a una hoja, que será el símbolo asociado al código.

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.

Limitaciones

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.

###