Tarea #3

For this homework I worked in huffman compression algorithm, the huffman compression consist in the use of a  table of codes of variable long assigned to characters that the element to compress contains.

How works?
The algorithm consist in make a tree based in the frequency in that the characters appears in the string.

First, when we have a string we search the frequency of the characters, for example:

'Adriana'

And this is the frequency:

Then the characters are added to a list ordered from lowest to highest according to their reps.

From the list from the tree as follows:

• First we take the first two nodes of the list and create a new node in which its root will be NULL and the sum of the number of repetitions of these two nodes.

• Nodes taken from the list are removed and the new node is added to the list and we have as follows:

• Repeat the process to combine the following lower nodes and get this:

Now, this is my code:

[

	import sys
	def contar(cadena):
	letras = dict()
	for l in cadena: #l = letras en cadena
	if l in letras:
	letras[l] +=1
	else:
	letras[l] = 1
	print letras
	return letras
	def ordenarMayor(letras):
	return sorted(letras.items(), key=lambda x: x[1])
	def crearNodos(ordenar):
	nodovalor = []
	nodos = []
	print ordenar
	for i in range (len(ordenar)):
	nodovalor.append(ordenar[i][1])
	print nodovalor
	while (len(nodovalor))>1: #mayor ke la suma
	z = nodovalor[0] # valor min 1
	print z
	a=0
	for i in range (len(nodovalor)):
	if nodovalor[i]<z:
	z = nodovalor[i]
	a = i
	nodovalor.pop(a)
	v = nodovalor[0] #valor min 2
	print v
	b = 0
	for i in range(len(nodovalor)):
	if nodovalor[i]<v:
	v = nodovalor[i]
	b = i
	suma = z + v # suma de minimos
	nodovalor[b] = suma ##aqui guardas los cambios
	print ':O'
	def main():
	cadena=str(raw_input("cadena:"))
	print cadena
	letras = contar(cadena)
	ordenar = ordenarMayor(letras)
	print ordenar
	nodo = crearNodos(ordenar)
	main()

view raw nodos.py hosted with ❤ by GitHub

]

:B 

To be continued...

References:

• Link