Huffman adaptativo

Codificación adaptativa

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

Este es el código:



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