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

	import networkx as netx
	import matplotlib.pyplot as grafica #Con este se genera la grafica \o/
	def arbol(Lista):
	G = netx.Graph()
	lista1 = list(Lista)
	lista2 = list()
	i = 1
	for i in range(len(Lista) - 1):
	pu = list([lista1.pop(0)])
	var1, var2 = pu[0][0], pu[0][1]
	pu = list([lista1.pop(0)])
	var3, var4 = pu[0][0], pu[0][1]
	d1 = 0
	d2 = 0
	if var2 > var4: #Si el primer valor es mayor
	d1 = 1
	d2 = 0
	else: #Si el segundo valor es mayor
	d1 = 0
	d2 = 1
	lista2.append((var1, d1))
	lista2.append((var3, d2))
	c = var1+''+var3
	d = var2 + var4
	G.add_node(var1)
	G.add_node(var3)
	G.add_node(c)
	G.add_edge(c, var1, color='blue')
	G.add_edge(c, var3, color='blue')
	puddi = lista1
	lista1 = list([(c, d)])
	for i in puddi:
	lista1.append(i)
	lista1 = ordenar2(lista1)
	netx.draw(G)
	#grafica.show() #Con este muestro en pantalla
	grafica.savefig("Hola.png") #Con este genero el grafo en una imagen
	return lista1, lista2
	def ordenar2(lista):
	dicc = ({})
	for i, j in lista:
	dicc[i] = j
	lista1 = sorted(dicc.items(), key=lambda x: x[1])
	return lista1
	def final(elementos, palabras):
	lisfi = ({})
	lista = elementos
	for i in range(len(elementos)):
	s = list(lista.pop(-1))
	var1, var2 = s[0], s[1] #Var1 es la palabra, y var2 es el valor (0 o 1)
	for j in palabras:
	if var1.find(j) != -1:
	if lisfi.has_key(j) == True: #Si la letra ya esta en el diccionario
	valor = lisfi[j]
	valor = str(valor)+str(var2)
	lisfi[j] = valor
	else:
	lisfi[j] = str(var2)
	return lisfi
	def atras(lista, comprimido):
	var1 = ''
	var2 = 0
	palabra = ''
	for i in comprimido:
	if var2 == 0:
	var1 = var1 + i
	for l in lista.keys():
	j = lista[l]
	if var1 == j:
	var1 = ''
	palabra = palabra + l
	var2 == 1
	else:
	var2 == 0
	return palabra
	def datos(lista):
	lista1 = list()
	for i, j in lista:
	lista1.append(i)
	return lista1
	def ordenar(dicc):
	dicc2 = sorted(dicc.items(), key=lambda x: x[1]) #Le los elementos del diccionario y los ordena de menor a mayor segun el valor de las claves
	return dicc2
	def contador(frase):
	lista = list(frase)
	lista2 = lista
	dicc = ({})
	for i in range(len(lista2)):
	a = lista.pop(0)
	if dicc.has_key(a) == True:
	valor = dicc[a]
	dicc[a] = valor + 1
	else:
	dicc[a] = 1
	return dicc
	def main():
	frase = raw_input('Frase a comprimir: ')
	diccionario = contador(frase)
	print 'Cantidad de letras en la frase: '+str(diccionario)
	diccionario = ordenar(diccionario)
	print 'Lista de Letras Ordenadas: '+str(diccionario)
	diccionario = list(diccionario)
	d, a = arbol(diccionario) #Se manda llamar el metodo arbol y recibe dos variables ...
	print '\nResultado del Arbol: '+str(a)
	palabras = datos(diccionario) #Este metodo separa el diccionario en una lista
	ListaFinal = final(a, palabras)
	print 'Binario: '+str(ListaFinal)
	compri = ''
	Lista = list(frase) #Se separa la frase en una lista
	for i in Lista:
	compri = compri+ListaFinal[i] #Se obtiene el binario del diccionario utilizando la letra de la frase y se almacena a compri
	compri = compri.replace(' ', '')
	print 'Comprimido : '+str(compri)
	desprin = atras(ListaFinal, compri)
	print 'Descomprimido: '+str(desprin)
	main()

view raw Compresor.py hosted with ❤ by GitHub

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