Lo primero que se necesita es nuestro texto: "avedocaaave".
Lo segundo que se tiene que hacer es ordenar nuestros valores con respecto a la cantidad de repeticiones:
código
código
Imagen de nuestro texto ordenado por frecuencias de menor a mayor:
Teniendo esto, ya podemos hacer nuestro árbol binario a travez del método de huffman.
1-. Lo primero que se hizo fue crear una lista de los nodos iniciales, quedando de la siguiente manera:
lista = [(c,0,0),(d,0,0),(o,0,0),(e,0,0),(v,0,0),(a,0,0)]
Donde el primer elemento es el nombre del nodo, el segundo elemnto es el peso de la arista y el tercer elemnto con que nodo esta conectado en cada elemento de la lista.
2-. Empesamos eligiendo los dos nodos que tengna menores frecuencias, en este ejemplo c y d , sumamos sus frecuencias y creamos un nuevo nodo, llamado 0 quedando la tabla de frecuencia de la siguiente manera:
nueva frecuencia: [2,1,2,2,4]
Y nuestra lista de la siguiente manera:
lista = [(c,1,0),(d,0,0),(o,0,0),(e,0,0),(v,0,0),(a,0,0),(0,0,0)]
Si nos fijamos agregamos un nuevo nodo y modificamos los respectivos pesos de las aristas, teniendo en cuenta que las uniones del lado izquierdo son unos y lados derechos son ceros.
Y repetimos este proceso hasta terminar el árbol.
Aquí una imagen de como quedaría gráficamente:
Usando el nodo mayor respecto a los números, se obtiene los diferentes códigos para la letras que necesitamos posteriormente.
Código de generacion del árbol
Código de generacion del árbol
Posteriormente recorremos nuestro árbol para obtener los diferentes códigos binarios de nuestras letras.Y juntamos todos los caracteres con respecto a la cadena original, generando un string de muchos ceros y unos.
Ya teniendo nuestro string en binario, el siguiente paso es pasarlo a bytes.
¿Como se hace esto?
En este método, se agarra de 8 bits del stringn, pero se tomo en cuenta que si existe un cero al inicio de la cadena, se pasa directo y se continua con el siguiente bits, asta completar los 8 y pasarlos a bytes o hexadecimal.
Quedando de la siguiente manera:
Código de bytes y descompresión
Código de bytes y descompresión
Resultado:
Extra:
Bueno les hablare aquí un poco de networkx
networkx es una libreria de python, sustituyendo el anterio py-graph
Esta libreria nos permite generar diferentes imagenes de grafos usando diferente tipo de informacion, Esta libreria se uso para este ejmplo y poder pintar el arbol.
Para instalar la librería la podemos buscar directamente desde synaptic e instalarla
Aquí el código que se usó para este ejemplo
Aquí el código que se usó para este ejemplo
Es todo por hoy
Link para descargar todo el código: Aqui
cadena = cadena.replace("\t","").replace("\n","") mejor poner cadena = cadena.replace("\t"," ").replace("\n"," ") para que no se peguen juntas las palabras... ¿bubblesort es lo más eficiente que se te ocurrió? o_0 para lo de peor caso y caso típico, me hubiera gustado algo tipo estadístico sobre las diferencias; lo de networkx es bueno :) Van 7+6 pts.
ResponderEliminar