Entrada # 3

Teoría de la Información y 

Métodos de Codificación

Algoritmo de Huffman

Para esta ocasión haremos uso del algoritmo de huffman para realizar la compresión en forma binaria de una frase.

Primeramente que es Algoritmo de Huffman

Este algoritmo fue creado por David A. Huffman con el propósito de la compresión de frases demasiado grandes.

El propósito de algoritmo es crear un árbol binario, a fin de obtener un código, la gran ayuda del árbol es que al seguir la raíz de arriba hacia abajo se obtiene el código de una manera fácil y gráfica.

Los pasos del Algoritmo:

• Se crean varios arboles uno por cada letra de la frase, a estas se le coloca su letra respectiva y la cantidad de veces que aparece.

• Se eligen los dos que tengan la menor frecuencia, estos se unen para crear un nuevo árbol (nodo) y los dos arboles que se unieron se unen mediante ramas (líneas) para indicar que son raíces del árbol que se acaba de crear. A este árbol que se creo, al igual que los anteriores, debe de tener su letra y la cantidad de repeticiones ... Estas se obtienen uniendo las dos letras  y se suman la frecuencia de estas letras.

• Se repite el paso anterior hasta que solo quede un solo árbol el cuál contendrá todas las letras y el tamaño de la frase (o la suma de las frecuencias de los arboles).

El proceso del programa es el siguiente:

• Te pide la frase a la que se le aplicara el algoritmo

• Se obtiene la cantidad de veces que se encuentra un carácter en la frase, por ejemplo: en la frase 'perro' nos detectaría 1 p, 1 e, 2 r, 1 o

• Después se ordena de menor a mayor en base a la cantidad de veces que esta cada carácter.

• La parte siguiente seria aplicar el Algoritmo.

• Teniendo lo que vale cada letra solo se sustituye el binario con la palabra y se obtendría la frase.

• Para regresar la frase solo se lee cada parte del binario y se compara si esta existe en la lista, si no existe se incrementa lo que va ahorita con el siguiente y se vuelve a aplicar el proceso

Código Realizado en Python

Imágenes del Resultado

Como ven en la imagen, nos pide la frase a comprimir; después obtiene la cantidad de veces que aparece cada letra y las ordena en base de menor a mayor según la cantidad de veces que aparece.

Una vez aplica el proceso del árbol y obtenemos una lista la cuál se barrera para obtener el binario de cada letra y para obtener el grafo.

Se obtiene la frase en binario y después se descomprime.

Imagen del grafo:

Corriendo con otra frase:

El único problema que tuve fue que no encontré el como acomodar la imagen a fin de que tenga una mejor presentación ya que mientras existían mas letras la imagen se veía mas horrible.

Referencias

http://networkx.github.io/documentation/latest/tutorial/tutorial.html
http://networkx.lanl.gov/pygraphviz/tutorial.html
http://www.danielmunoz.com.ar/blog/2010/07/07/el-algoritmo-de-huffman/
http://es.wikipedia.org/wiki/Algoritmo_de_Huffman