Huffman y su compresión

Buenas compañeros y gente que nos visitan, en esta ocación les traemos como realizar el árbol binaro de Huffman y usar este mismo árbol para la compresión de los datos. Bueno empecemos.


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