[TEORÍA DE LA INFORMACIÓN] Codificación Adaptativa

Para esta semana se encargó realizar un algoritmo de codificación adaptativa basado en la codificación Huffman.

Realicé unas modificaciones a la tarea anterior para hacerlo lo más adaptativo posible.

Anteriormente procesaba todo el texto en una sola iteración y generaba una tabla de frecuencias de caracteres. Después generaba una lista de nodos y al final generaba un árbol.

Ahora he cambiado ciertas cosas en el código, no proceso el texto de la misma manera, sino que ahora lo divido en palabras de N caracteres y cada una las proceso por separado, genero los nodos para esa palabra y por cada palabra modifico un árbol con los nuevos nodos.


Al correr el programa, se genera y se imprime la lista de palabras de N caracteres, despues se corren los algoritmos, finalmente se imprime el texto original junto con el texto decodificado. Tambien se imprimen los datos de la corrida del programa.

Pensé que generar varios arboles optimizaría un poco el tiempo puesto que se procesan más rápido y la codificación se genera con mayor velocidad, una vez generada el arbol se mantendrá constante, a diferencia de la versión anterior, que una vez procesado el texto generaba el arbol de forma recursiva y con tiempos ligeramente más elevados.

El código es el siguiente:
Realmente es algo demasiado sencillo pero cumple con las especificaciones:

• No hay un calculo de las frecuencias en un principio (solo se calcula frecuencias de caracteres por cada palabra generada).
• No hay conocimiento de la distribución de símbolos.

Algo que destaca es que dependiendo de el valor de N el algoritmo se comportará distinto, se puede observar que para pocas letras no hay eficiencia, llegando a compresiones que generan archivos mayores al original.

Para hacer unas pruebas, usé un archivo de texto con 10000 caracteres aproximadamente, se puede ver como en un principio hay dificultades, pero se estabiliza.

Como se puede ver, a medida que la cantidad de caracteres por palabra generada aumenta, el radio de compresión disminuye.

El tiempo que tarda en procesar cada palabra generada también disminuye, se puede ver que aproximadamente 10 caracteres por palabra es lo más óptimo para el texto que seleccioné.

Comparado con la implementación normal estos fueron los resultados:

Para los radios de compresión, la implementación anterior es constante.

Los tiempos son muy variables. Depende de la computadora.

Mi conclusión es que se puede mejorar el algoritmo, puesto que bajo ciertas circunstancias tiene un nivel de compresión ligeramente mejor, y sus tiempos son buenos comparados con la implementación normal, el algoritmo hace demasiado uso de recursiones y excepciones para generar la codificación, y cada recursión significa menos eficiencia, y las excepciones son una mala práctica, combinarlas es algo que mejor se debe evitar. 

Así que lo mejor que se puede hacer para mejorar el rendimiento es buscar una alternativa. A nivel compresión seguiría teniendo la misma eficiencia, a nivel de tiempo podría mejorar.