La manera en que hice mi algoritmo adaptativo fue ir pasando carácter por carácter al codificador, entonces de manera que el primer carácter que entrara tuviera la frecuencia 1, pero que la raíz siempre tuviera dos hijos, el derecho y el izquierdo en donde el izquierdo es un nodo auxiliar que es el que va a ayudar a ir colocando los nuevos símbolos en el árbol cuando se encuentra que se colocó en un nodo algunas frecuencias al revés por ejemplo "casualmente aparecen al principio 10 letras "e" y 5 letras "a" " con eso el árbol piensa que e merece un código más pequeño, pero después empiezan a aparecer las letras "a" y entonces se modifican los nodos para que siempre se cumpla con esa regla. Cada vez que entra un nuevo carácter se va modificando la tabla de frecuencia y con esto podemos acomodar los nuevos nodos.
Decodificación
Para la decodificación se fueron guardando cada una de las tablas de frecuencia, y así al igual que en la entrada pasada simplemente, se leyó el archivo con la entrada y se empezó a decodificar cada uno de estos con los caracteres que ya se tenían previamente. Se fue leyendo el árbol para así poder decodificar y escribir en otro archivo el texto decodificado.
Experimento
Caso típico.- Para el experimento se tomo un texto de 100000 (el mismo de la tarea pasada)caracteres de un libro en inglés para poder representar el caso típico.
Peor caso.- Se escogió con random.choice de una lista que contiene ascci, del mismo largo que el texto que se tomo de ejemplo.
Y con estos dos textos de prueba se hicieron las pruebas con las siguientes variaciones:
- Se cambió el largo que va agarrando, a lo que yo llamé "paso en el código", se fue cambiando de 10 en 10.
- Se tomaron 10000 pruebas para gráficar.
Obviamente la impresión de esto es casi imposible así que solo para mostrar como corre el programa aquí dejo una captura con muy pocos caracteres:
Y el árbol de manera gráfica de otro ejemplo muy simple:
 |
| Aquí aun aparecía más veces la "b" |
 |
| Después apareció más veces la "a" y cambiaron las posiciones |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #!/usr/bin/python | |
| import string | |
| import time | |
| import random | |
| import matplotlib.pyplot as plt | |
| import operator | |
| from pylab import * | |
| from random import choice | |
| #DEBUG = True | |
| DEBUG = False | |
| class Nodo: | |
| """nodo hoja | |
| """ | |
| def __init__(self, simbolo, peso): | |
| self.simbolo = simbolo | |
| self.peso = peso | |
| self.der = None | |
| self.izq = None | |
| self.padre = None | |
| def graficar(x1, y1, titulo1, x2,y2, titulo2): | |
| """grafica dividiendo el canvas en 2 | |
| columnas y renglones | |
| """ | |
| fig = plt.figure() | |
| fig.subplots_adjust(hspace=.5) | |
| uno = fig.add_subplot(221) | |
| uno.plot(x1, y1) | |
| uno.set_yscale('log') | |
| uno.set_xlabel('tamano de transmision') | |
| uno.set_ylabel('tiempo') | |
| uno.set_title(titulo1) | |
| uno.grid(True) | |
| dos = fig.add_subplot(223) | |
| dos.plot(x2, y2) | |
| uno.set_yscale('log') | |
| dos.set_xlabel('tamano de transmision') | |
| dos.set_ylabel('tiempo') | |
| dos.set_title(titulo2) | |
| dos.grid(True) | |
| plt.savefig('hola.png') | |
| def actualiza_arbol(frec): | |
| """hace el arbol de acuerdo a las frecuencias | |
| regresa la raiz del arbol | |
| """ | |
| nodos = [] | |
| ordenados = sorted(frec, key=frec.get) | |
| for i in ordenados: | |
| nodos.append(Nodo(i, frec[i])) | |
| while True: | |
| if len(nodos)>1: | |
| izq = nodos[0] | |
| nodos = nodos[1:] | |
| der = nodos[0] | |
| nodos = nodos[1:] | |
| x = Nodo(str(izq.simbolo)+str(der.simbolo), izq.peso + der.peso) | |
| x.izq = izq | |
| x.der = der | |
| nodos.append(x) | |
| der.padre = x | |
| izq.padre = x | |
| nodos = sorted(nodos, key=lambda x: x.peso) | |
| if DEBUG: | |
| print "*papa %s %s, *izq %s %s *der %s %s" %(x.peso, x.simbolo, | |
| x.izq.peso,x.izq.simbolo, | |
| x.der.peso,x.der.simbolo) | |
| elif len(nodos)==1: | |
| padre = Nodo(str(izq.simbolo)+str(der.simbolo), izq.peso + der.peso) | |
| padre.izq = izq | |
| padre.der = der | |
| nodos = [] | |
| if DEBUG: | |
| print "*papa %s %s, *izq %s %s *der %s %s" %(padre.peso, padre.simbolo, padre.izq.peso,padre.izq.simbolo, padre.der.peso, padre.der.simbolo) | |
| else: | |
| break | |
| return padre | |
| def decodificar(raiz): | |
| """decodifica | |
| """ | |
| f = open("frase_codificada.txt") | |
| frase_codificada = f.read() | |
| #print frase_codificada | |
| frase_encontrada = "" | |
| padre = raiz | |
| while len(frase_codificada)>0: | |
| s = str(frase_codificada[0]) | |
| frase_codificada = frase_codificada[1:] | |
| if s == "0": | |
| raiz = raiz.der | |
| else: | |
| raiz = raiz.izq | |
| if raiz.der == None and raiz.izq == None: | |
| frase_encontrada = frase_encontrada+raiz.simbolo | |
| raiz = padre | |
| return frase_encontrada | |
| def codigos(hojas): | |
| """obtiene los codigos haciendo un recorrido desde la | |
| hoja a la raiz | |
| """ | |
| lista = [] | |
| dic = {} | |
| for i in hojas: | |
| byte = "" | |
| padre = i.padre | |
| actual = i | |
| while True: | |
| if padre: | |
| pass | |
| else: | |
| break | |
| if actual == padre.izq: | |
| byte = byte + "1" | |
| else: | |
| byte = byte + "0" | |
| actual = padre | |
| padre = padre.padre | |
| lista.append((i.simbolo, i.peso, byte[::-1])) | |
| dic[i.simbolo]=byte[::-1] | |
| if DEBUG: | |
| print lista, dic | |
| return lista, dic | |
| def obtiene_hojas(nodos): | |
| """obtiene las hojas del arbol, recibe como entrada | |
| toda la lista de nodos | |
| """ | |
| hojas = [] | |
| for nodo in nodos: | |
| if nodo.der == None and nodo.izq == None: | |
| hojas.append(nodo) | |
| if DEBUG: | |
| print "Numero de hojas %s" %(len(hojas)) | |
| return hojas | |
| def recorrer(padre, lista_nodos, lista_pesos): | |
| """recorrido en preorden solo para obtener la lista de | |
| todos los nodos | |
| """ | |
| if padre != None: | |
| lista_nodos.append(padre) | |
| lista_pesos.append(padre.peso) | |
| recorrer(padre.izq, lista_nodos, lista_pesos) | |
| recorrer(padre.der, lista_nodos, lista_pesos) | |
| return lista_nodos, lista_pesos | |
| def escribe_codigos(frase, codigos): | |
| """escribe la frase codificada | |
| """ | |
| f = open("frase_codificada.txt", "w") | |
| for i in frase: | |
| try: | |
| f.write("%s" %codigos[i]) | |
| except: | |
| pass | |
| f = open("frase_codificada.txt") | |
| texto = f.read() | |
| f.close() | |
| return len(texto) | |
| def escribe_tabla(codigos): | |
| """escribe el diccionario en un archivo | |
| """ | |
| f = open("tabla_frecuencias.txt", "w") | |
| for i in codigos: | |
| f.write("%s %s\n" %(i[0], i[2])) | |
| def frecuencia(frase, frec): | |
| """obtiene la frecuencia de los simbolos | |
| en la frase | |
| """ | |
| frec_temp = {} | |
| for l in frase: | |
| if not(l in frec_temp): | |
| frec_temp[l] = frase.count(l) | |
| frec = dict([(n, frec.get(n, 0)+frec_temp.get(n, 0)) for n in set(frec)|set(frec_temp)]) | |
| return frec | |
| def leer_texto(): | |
| """ | |
| """ | |
| f = open("texto.txt") | |
| texto = f.read() | |
| texto = texto.replace("\n","") | |
| return texto | |
| def genera_dist_unif(n): | |
| """ | |
| """ | |
| texto = '' | |
| caracteres = list(string.printable[:80]) | |
| for i in range(n): | |
| texto += choice(list(string.printable[:80])) | |
| return texto | |
| def pasos(texto, paso): | |
| frec = {} | |
| for i in range(0,len(texto), paso): | |
| fragmento = texto[i:i+paso] | |
| frec = frecuencia(fragmento, frec) | |
| raiz = actualiza_arbol(frec) | |
| #recorrido en preorden | |
| lista_pesos = [] | |
| lista_nodos = [] | |
| lista_nodos, lista_pesos = recorrer(raiz, lista_nodos, lista_pesos) | |
| print "Recorrido en preorden %s" %lista_pesos | |
| #obtengo hojas del arbol | |
| hojas = obtiene_hojas(lista_nodos) | |
| #se obtienen los codigos para cada simbolo | |
| lista_codigos, dic_codigos = codigos(hojas) | |
| #se escribe una tabla con sus frecuencias | |
| escribe_tabla(lista_codigos) | |
| #se pasa el texto normal a los codigos encontrados | |
| len_codificado = escribe_codigos(texto, dic_codigos) | |
| #se decodifica | |
| frase_decodificada = decodificar(raiz) | |
| print "La frase encontrada: %s" %frase_decodificada | |
| def huffman_adaptativo(texto): | |
| """experimento | |
| """ | |
| inicio = time.time() | |
| x = [] | |
| y = [] | |
| for i in range(3, 10000, 100): | |
| paso = i | |
| inicio = time.time() | |
| pasos(texto, paso) | |
| total = time.time()-inicio | |
| print i, total | |
| x.append(i) | |
| y.append(total) | |
| return x, y | |
| def main(): | |
| texto = leer_texto() | |
| x1,y1 = huffman_adaptativo(texto) | |
| texto = genera_dist_unif(len(texto)) | |
| x2,y2 = huffman_adaptativo(texto) | |
| graficar(x1,y1, "Caso tipico", x2,y2,"Distribucion uniforme") | |
| main() |
Y las gráficas generadas se ven así:
 |
| Se puede apreciar ligeramente que el caso típico hace menos tiempo que el peor caso |
Con lo que podemos concluir que el algoritmo funciona mejor cuando se empieza a pasar de más de 100 caracteres, además podemos comprobar también que funciona mejor para el caso típico en cuestión de tiempo y ratio que para el peor caso.
Además se puede ver que el algoritmo funciona bien cuando el archivo es grande pero la tasa de compresión alcanzable es desfavorable al comienzo de la codificación o para archivos pequeños.
Para mejorarlo se podría tener ya una lista de probabilidades estándar en el idioma que se usa para así poder ir acomodando los nodos mientras van llegando sabiendo cual es su frecuencia también establecer siempre que el paso de caracteres sea siempre el mínimo por default 100 por ejemplo para poder evitar que entren pocos caracteres y se hagan probabilidades erróneas.
Referencias
Elisa Schaeffer-Métodos adaptativos
Bien; 5+5. Cuida la ortografía.
ResponderEliminar