Algoritmo de huffman

Algoritmo de Huffman

Inconvenientes que originan el uso del algoritmo:
1) Insuficiente cantidad de espacio en discos y diskettes.
2) Tiempos de transmisión prolongados y costos elevados.

Introducción.
Por lo general, las computadoras codifican los caracteres mediante códigos como el ASCII y el EBCDIC. En el caso del ASCII, se maneja con 8 bits para la representación de un byte, por lotanto hay 28 posibles representaciones de caracteres pero siempre de longitud fija.
Una posibilidad de disminuir el espacio, sería la de utilizar códigos de representación de longitud variable.
Así por ejemplo, podría representarse la letra a con el valor binario 0, la letra b con el valor binario 1, la letra c con el valor 01 y así sucesivamente. Pero ante la codificación 0101 podríainterpretarse como abab o bien como cc.
El problema de decodificar un 01 podría solucionarse mediante la utilización de un prefijo antes de la codificación del caracter que indique el comienzo de un caracter y el fin del anterior, pero esto encarecería nuevamente el tema del espacio que es el que ahora nos preocupa.

Concepto del algoritmo.
El algoritmo de Huffman define un código variable para cadacaracter sin la necesidad de utilizar un prefijo. De esta manera es posible que, aquellos caracteres que son más frecuentes dentro de un alfabeto, se codifiquen con la menor cantidad de bits posibles mientras que aquellos que no sean tan frecuentes podrán tener una codificación un poco más amplia, pero siempre tendiendo a ser la menor posible. Es obvio pensar que en el alfabeto del lenguaje castellanola letra a es usada con mucha más frecuencia que la letra x. Este concepto se optimizaría si en lugar de aplicarlo a un alfabeto se aplicara a cada texto en particular, es decir, conocer con exactitud cuántas veces se repite un caracter dentro del texto para, de esa manera darle un código variable que sea el menor posible para aquellos que se repitan con mayor frecuencia y a medida que seanecesario utilizar más bits para codificar un caracter, que la frecuencia con que el caracter se usa en el texto sea menor.
Para ello, Huffman hace uso de una tabla de frecuencias donde se guardan los caracteres empleados en el texto y la cantidad de veces que son utilizados y de un árbol binario como estructura de datos. El código generado por el algoritmo, está basado en el código Morse y define unalongitud variable de codificación basada en valores estadísticos.

Tabla de Frecuencias.
Huffman toma el archivo a compactar y genera una tabla de frecuencias con los caracteres utilizados. Por ejemplo supongamos que el archivo a compactar tiene el siguiente texto (no tomar en cuenta las comillas):
"tomamos como ejemplo esta frase”.

La tabla de frecuencias sería la siguiente.

Si sehubiera codificado mediante código ASCII, la cantidad de bits utilizados sería igual a 256, es decir que mediante el código de Huffman, sin ninguna optimización en especial, se obtuvo un archivo compactado en un 57%.

¿Cómo obtiene Huffman el código de cada caracter?
Mediante el uso de:
a) una tabla de frecuencias
b) un árbol binario como estructura de datos donde:
* Cada hijo izquierdodistinto de nil representa un 0 binario
* Cada hijo derecho distinto de nil representa un 1 binario
* Cada hoja del árbol es un caracter
En el ejemplo planteado, el árbol asociado sería el de la Figura 1. :

El nodo del árbol binario que utiliza Huffman tiene el siguiente diseño mostrado en la Figura 2:

El algoritmo se basa en:
1) Hallar los dos caracteres con la frecuencia más baja de la tablade frecuencias. Si un caracter tiene frecuencia cero se ignora. Si dos o más caracteres tienen igual frecuencia se eligen dos cualesquiera.
2) Combinar los dos caracteres en un árbol binario. (Ver Figura 3).
Cada hoja de este árbol contiene uno de los caracteres que se quiere codificar en el campo identificador, la frecuencia obtenida de la tabla de frecuencias en el campo frecuencia, nil en...