Algoritmo de Huffman

En esta entrada lo que se buscó fue la implementación del algoritmo de Huffman que básicamente consiste en comprimir cadenas.

Algoritmo de Huffman:
Dejo un video donde nos explican sencillamente como se hace éste algoritmo


Implementación:
Para su implementación se desarrollo en python y lo buscado fue que el programa te generara una cadena aleatoria, esta cadena es guardada en binaria, a la cadena creada aplicamos el algoritmo de huffman, y esta es guardada en binario, teniendo éstos dos nos servirá para hacer una pequeña demostración de lo obtenido.

Generar Cadena, obtenemos las veces las veces que se repiten y Ordenamos la lista

Obtenemos las llaves por así decirlo (uniones o enlaces) que se tienen de los nodos

Comprimimos la cadena original y generamos el archivo binario

Descomprimimos la cadena comprimida para obtener la original

Generamos gráfo de nuestra llaves, la cual se empleo la librería networkx, donde me base de éste código

Main

Experimento

Las salidas que podemos ver en mi experimento fue la longitud del tamaño de la cadena original comparando con la cadena binaria y su llave.

Obteniendo como resultado, que si se tiene una diferencia de la longitud de las cadenas siendo mucho más pequeña cuando se aplica el algoritmo de Huffman y en el ejemplo mencionado podemos ver que ocupa solo el 29.8% porciento del la longitud de la cadena original, asi que podemos decir que se redujo hasta un 70% el mensaje.

También se crearon dos archivos el primero que contiene la cadena original y el segundo que es un archivo binario, com se puede ver el tamaño de éstos tiene una gran diferencia, que en archivo con la cadena es de 37KB y en el archivo binario de 5KB.

También podemos ver como éstan enlazados los nodos de las llaves obtenidas y cuales son los nodos con mayor peso.

Notas:
Debo de mencionar un agradecimiento a un compañero de clase por ayudarme en el desarrollo del programa, dejo el link del blog.

Referencias:
https://www.udacity.com/wiki/creating_network_graphs_with_python
http://es.wikipedia.org/wiki/Codificaci%C3%B3n_Huffman
http://stackoverflow.com/questions/10804659/python-dictionary-count
http://wiki.python.org/moin/HowTo/Sorting/
http://www.youtube.com/watch?v=8Gf8wutvS1w