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

	def crearCadenaRand():
	return ''.join([chr(random.randrange(98, 108)) for i in range(50)]) #122 Hay que cambiarlo para que agg
	def getListCadena(cadena):
	return ordenarDiccionario(dict(Counter(list(cadena)).most_common()[::-1])) #regresamos las veces que se repite cada caracter en orden ascendente
	#return OrderedDict(sorted(dict_cadena.items(), key=lambda x: x[1])) #Regresamos ordenado el diccionario
	def ordenarDiccionario(diccionario): #ordenamos el diciconario y regresamos una lista o tupla
	return sorted(diccionario.iteritems(), key=itemgetter(1))

view raw gistfile1.py hosted with ❤ by GitHub

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

	def getList_Llave(tuple_frecuencia):
	arbol_binario = dict()
	while len(tuple_frecuencia) > 1:
	izq = tuple_frecuencia.pop(0) #tomamos y liberamos el 1er valor y se lo asignamos a la izq
	der = tuple_frecuencia.pop(0) #tomamos y liberamos el 2do valir y asignamos a la der
	suma_2nodos = izq[1] + der[1]
	arbol_binario[izq[0], suma_2nodos] = 0 #Asignamos el valor al diccionario que contendrael arbol
	arbol_binario[der[0], suma_2nodos] = 1
	tuple_frecuencia.append([suma_2nodos, suma_2nodos]) #volvemos a meter a la lista el valor obtenido
	tuple_frecuencia = sorted(tuple_frecuencia, key=lambda o: o[1])
	arbol_binario = sorted(arbol_binario.iteritems(), key=lambda o: o[0][1])
	a = list(arbol_binario)
	llaves = list()
	while len(a) > 0:
	now = a.pop(0)
	raiz = list()
	while now != tuple_frecuencia[0][0]:
	raiz.append(now[1])
	now = now[0][1]
	for items in a:
	if items[0][0] == now:
	now = items
	break
	raiz.reverse()
	llaves.append(raiz)
	return(llaves, arbol_binario)

view raw gistfile1.py hosted with ❤ by GitHub

Comprimimos la cadena original y generamos el archivo binario

	def comprimir(cadena, list_valor_nodo):
	m_Binary = ""
	f = file('/tmp/mensajeBin.bin', 'wb')
	for letter in cadena:
	for nodo, valor in list_valor_nodo:
	if nodo == letter:
	m_Binary += ''.join(str(i) for i in valor)
	byte1 = int(''.join(str(i) for i in valor), 2)
	f.write('%c' % byte1)
	break
	return m_Binary

view raw gistfile1.py hosted with ❤ by GitHub

Descomprimimos la cadena comprimida para obtener la original

	def descomprimir(cadenaBinaria, llave):
	cadena = ""
	while len(cadenaBinaria) > 0:
	nodoRaiz = llave[-1][0][1]
	repeticiones == True
	while repeticiones == True:
	for nodos, valorArista in llave:
	if (nodos[1] == nodoRaiz) and (valorArista == int(cadenaBinaria[0])):
	cadenaBinaria = cadenaBinaria[1:]
	nodoRaiz = nodos[0]
	break
	if type(nodoRaiz) == int: repeticiones = False
	cadena += nodoRaiz
	return cadena

view raw gistfile1.py hosted with ❤ by GitHub

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

	def draw_graph(graph, labels=None, graph_layout='shell',
	node_size=1600, node_color='blue', node_alpha=0.3,
	node_text_size=12,
	edge_color='blue', edge_alpha=0.3, edge_tickness=1,
	edge_text_pos=0.3,
	text_font='sans-serif'):
	#https://www.udacity.com/wiki/creating_network_graphs_with_python
	# create networkx graph
	G=nx.Graph()
	# add edges
	for edge in graph:
	G.add_edge(edge[0], edge[1])
	# these are different layouts for the network you may try
	# shell seems to work best
	if graph_layout == 'spring':
	graph_pos=nx.spring_layout(G)
	elif graph_layout == 'spectral':
	graph_pos=nx.spectral_layout(G)
	elif graph_layout == 'random':
	graph_pos=nx.random_layout(G)
	else:
	graph_pos=nx.shell_layout(G)
	# draw graph
	nx.draw_networkx_nodes(G,graph_pos,node_size=node_size,
	alpha=node_alpha, node_color=node_color)
	nx.draw_networkx_edges(G,graph_pos,width=edge_tickness,
	alpha=edge_alpha,edge_color=edge_color)
	nx.draw_networkx_labels(G, graph_pos,font_size=node_text_size,
	font_family=text_font)
	if labels is None:
	labels = range(len(graph))
	edge_labels = dict(zip(graph, labels))
	nx.draw_networkx_edge_labels(G, graph_pos, edge_labels=edge_labels,
	label_pos=edge_text_pos)
	# show graph
	plt.savefig("grafo.png");
	plt.show()

view raw gistfile1.py hosted with ❤ by GitHub

Main

	def main():
	cadenaOriginal = crearCadenaRand()
	f = file('/tmp/mensaje.dat', 'wb')
	ca2 = ''.join(str(i) for i in [bin(ord(ch))[2:].zfill(8) for ch in cadenaOriginal ])
	f.write(ca2)
	list_cadena_original = getListCadena(cadenaOriginal)
	list_valor_nodo, nodos = getlist_Llave(list_cadena_original)
	m_Binary = comprimir(cadenaOriginal, list_valor_nodo)
	cadena = descomprimir(m_Binary, nodos)
	print cadenaOriginal
	print m_Binary
	print cadena
	print '-----'
	print len(ca2)
	print len(m_Binary) + len(list_valor_nodo)
	print ((len(m_Binary)+ len(list_valor_nodo)) * 100.0) / len(ca2)
	draw_graph(nodos)

view raw gistfile1.py hosted with ❤ by GitHub

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