Tarea #4. Método adatpativo

For this week we ask you to make a coding algorithm based adaptive Huffman coding.

Try to modify my above code to make it adaptive only manage to finish a bit to read me the frequency of characters within a compressed textro something that was not yet finished.


Remembering some algorithm process:


1. We look for the frequency of unique characters in the text above.
2. Each of the characters is created as a tree and add them to a list, each tree has its associated symbol and frequency number.
3. The ordered from lowest to highest according to the frequencies.
4. From the above it will select the first two trees from the list and will form a new tree with them, before the tree will delete the two trees in the list. The root of the new tree will be the sum of the frequencies of the roots of the two trees to be joined and the trees will now child nodes of this. 
5. We add to the list the new tree created by ordering from low to high 
6. Already having obtained the tree end we have to begin to explore it in order to get the binary code of each of the characters, as we know is a binary tree that has the following tags that link one node to another.

Codigo

	from Tkinter import *
	from sys import argv
	import math
	import sys, string
	cam = list()
	codigos = list()
	frec = list()
	simbolos = {}
	arbol_fin =''
	class Principal:
	#der=None
	#izq=None
	#padre=None
	def __init__(self, padre, izq=None, der=None):
	#self.der.append(None)
	#self.izq.append(None)
	#self.padre.append(None)
	self.padre=padre
	self.izq=izq
	self.der=der
	#arbol por ramas y frecuencias
	def nodos(frec,texto):
	global arbol_fin
	bosque = list()
	while ((len(frec) > 1)):
	print "raiz", frec[0][1] + frec[1][1]
	ramas = Principal(frec[0][1] + frec[1][1],frec[0][0],frec[1][0])
	print "nodo izquierdo",frec[0][0]
	print "nodo derecho",frec[1][0]
	frec.append((ramas,frec[0][1] + frec[1][1]))
	del frec[0]
	del frec[1]
	frec=sorted(frec,key=lambda it: it[1])
	raw_input()
	arbol_ordenado(frec[0][0],'')
	for i in texto:
	arbol_fin+=simbolos[i]
	return frec[0][0]
	#ordenamos de menor a mayor
	def ordenar(texto):
	for i in texto:
	if (i) not in codigos:
	codigos.append(i)
	cam.append((Principal(i),simbolos[i]))
	frec=sorted(cam,key=lambda it: it[1])
	print 'prueba',frec
	raw_input()
	return frec
	def arbol_ordenado(frec,cam):
	if frec==None:
	return cam[:-1]
	if type(frec.datos) == str:
	print frec.datos, ':',cam
	simbolos[frec.padre]=arbol_fin=arbol_ordenado(frec.izq,cam=cam+'0')
	simbolos[frec.padre]=arbol_fin=arbol_ordenado(frec.der,cam=cam+'1')
	def juntos(texto):
	for i in texto:
	if i not in simbolos:
	simbolos[i]=1
	else:
	simbolos[i]=simbolos[i]+1
	return
	def mostrar(palabra_1):
	#print palabra_1
	valor=palabra_1
	palabara = ''
	for i in arbol_final:
	if i=='0':
	valor=valor.izq
	if valor.izq==None and valor.der==None:
	palabra+=valor.padre
	valor=palabra_1
	else:
	valor=valor.der
	if valor.izq==None and valor.der==None:
	palabra+=valor.padre
	valor=palabra_1
	print 'Cadena descomprimida:',palabra
	def main():
	texto=raw_input('Cadena a utilizar: ')
	juntos(texto)
	frec=ordenar(texto)
	palabra_1=nodos(frec,texto)
	print 'Cadena comprimida',arbol_final
	mostrar(palabra_1)
	if __name__ == "__main__":
	main()

view raw notermiando.py hosted with ❤ by GitHub

The idea to make a little adaptive was possible to continue updating the tree and updates during ordering property is maintained, for example, nodes (internal and leaves) were ordered according to increasing their weights.

When it is necessary to exchange the farthest node with a certain weight is exchange with the node whose weight is increased.

Be tree could be seen differently when exchanging nodes and perform better compression level and still have the same efficiency.

But the program didn't work :(