Adaptive Code

For this week's homework, we had to implement a compression algorithm that doesn't compress all the input at once, but to make the compression in parts. That's the adaptive part of the coding.

This is how I implement it: For each part of the input that was going to be processed, take the input letters and make a dictionary with each letter as key, and its frequency as value. Next, a new dictionary is created, but this time the value is going to be its probability of apearing in the spanish alphabet.  Also, for each part we had to see if the some letter hasn't appear before.

With this, we create a graph where each node is added by "asking": is it greater than the actual node? (go to right); is it lower than the actual node? (go to left).

This is what I did:
Clase principal:

	from GestorArchivos import GestorArchivos
	from Adaptativo import Adaptativo
	impresiones = True
	data_in = "data_in.txt"
	data_out = "data_out.txt"
	def main():
	ges = GestorArchivos()
	contenido = ges.leer(data_in).lower().replace("\t", "").replace("\n", "")
	copyContenido = contenido
	alg = Adaptativo(("Padre", 6.5))
	while len(contenido) > 0:
	pedazo = alg.dividir(contenido)
	letraFrecuencia = alg.obtenerFrecuencia(pedazo)
	if impresiones:
	print pedazo
	print letraFrecuencia
	print "---------------"
	alg.adaptar(letraFrecuencia)
	contenido = contenido[10:]
	if impresiones:
	print "ARBOL:"
	print alg.getGrafoUniones()
	print "-------------"
	msnComprimido = alg.comprimir(copyContenido)
	main()

view raw Main.py hosted with ❤ by GitHub

Algoritmo:

	def obtenerLetras(cadena):
	letrasUnicas = dict()
	for caracter in cadena:
	if caracter in letrasUnicas:
	letrasUnicas[caracter] += 1
	else:
	letrasUnicas[caracter] = 1
	letrasUnicas = letrasUnicas.items()
	return letrasUnicas
	def ordenarMenorMayor(lista, metodo="listaTuplas"):
	if metodo == "listaTuplas":
	return sorted(lista, key=lambda o: o[1])
	else:
	return sorted(lista, key=lambda o: o[0][1])
	class Algoritmo:
	def __init__(self, nodoPadre):
	self.nodoPadre = nodoPadre
	self.nombreNodo = nodoPadre[0]
	self.valorNodo = nodoPadre[1]
	self.grafo = list()
	self.grafoUniones= list()
	self.frecuenciaAbecedario =\
	{"a": 12.53, "b": 1.42, "c": 4.68, "d": 5.86,\
	"e": 13.68, "f": 0.69, "g": 1.01, "h": 0.70,\
	"i": 6.25, "j": 0.44, "k": 0.01, "l": 4.97,\
	"m": 3.15, "n": 6.71, "o": 8.68, "p": 2.51,\
	"q": 0.88, "r": 6.87, "s": 7.98, "t": 4.63,\
	"u": 3.93, "v": 0.90, "w": 0.02, "x": 0.22,\
	"y": 0.90, "z": 0.52, " ": 17.6, nodoPadre[0]:nodoPadre[1]}
	def dividir(self, cadena):
	return cadena[:10]
	def obtenerFrecuencia(self, pedazo): # pedazo = string
	letrasUnicas = obtenerLetras(pedazo)
	letraFrecuencia = list()
	for caracter, aparicion in letrasUnicas:
	if caracter in self.frecuenciaAbecedario:
	letraFrecuencia.append([caracter, self.frecuenciaAbecedario[caracter]])
	letraFrecuencia = ordenarMenorMayor(letraFrecuencia)
	letraFrecuencia.reverse()
	return letraFrecuencia
	def rastrearNodoFinal(self, nodo):
	if len(self.grafoUniones) != 0:
	if self.frecuenciaAbecedario[nodo] < self.frecuenciaAbecedario[self.nombreNodo]:
	sig = False
	for elemento in self.grafoUniones:
	if elemento[0][0] == self.nombreNodo:# and\
	#elemento[1] == 0: # izquierda
	self.nombreNodo = elemento[0][1]
	sig = True
	if sig:
	self.rastrearNodoFinal(self.nombreNodo)
	else:
	return
	else:
	sig = False
	for elemento in self.grafoUniones:
	if elemento[0][0] == self.nombreNodo: #and\
	#elemento[1] == 1: # derecha
	self.nombreNodo = elemento[0][1]
	sig = True
	if sig:
	self.rastrearNodoFinal(self.nombreNodo)
	else:
	return
	else:
	return
	def adaptar(self, letraFrecuencia):
	for letra, frecuencia in letraFrecuencia:
	self.nombreNodo = self.nodoPadre[0] # reiniciamos el nombre raiz
	if letra not in self.grafo:
	self.grafo.append(letra)
	self.rastrearNodoFinal(letra)
	if self.frecuenciaAbecedario[letra] < self.frecuenciaAbecedario[self.nombreNodo]:
	self.grafoUniones.append([[self.nombreNodo, letra], 0]) # unimos
	else:
	self.grafoUniones.append([[self.nombreNodo, letra], 1]) # unimos
	return
	def getGrafoUniones(self):
	return self.grafoUniones
	def comprimir(self, cadena):
	print "ENTRAMOS"
	msnComprimido = ""
	for caracter in cadena:
	sig = True
	valor = ""
	nodoActual = caracter
	while sig:
	for nodo in self.grafoUniones:
	if nodo[0][1] == nodoActual:
	valor += str(nodo[1])
	nodoActual = nodo[0][0]
	sig = True
	# convertir una cadena de INT en STR
	#msnComprimido += "".join(map(str, codigo))
	break
	print "--------------"
	print "LETRA: ", nodo[0][1]
	print valor
	if nodoActual == "Padre":
	sig = False
	print self.grafoUniones
	return msnComprimido

view raw Adaptativo.py hosted with ❤ by GitHub

Archivos

	class GestorArchivos:
	def leer(self, nombreArchivo):
	try:
	archivo_in = open(nombreArchivo, "r")
	except:
	return '''La desventaja no era algo que se podria
	imaginar en la cancha, pues los potosinos ya jugaban
	con un hombre menos por la expulsion de Emilio
	Lopez el autor del gol tambien se iria
	a las regaderas
	'''
	contenido = ""
	for linea in archivo_in.readlines():
	contenido += "".join(linea)
	archivo_in.close()
	return contenido
	def guardar(self, nombreArchivo, cadena):
	archivo = open(nombreArchivo, "w")
	print >> archivo, cadena
	archivo.close()
	return

view raw GestorArchivos.py hosted with ❤ by GitHub

El resultado se cicla :(