[TEORÍA DE LA INFORMACIÓN] Fundamentos de compresión - Codificación Huffman

Para esta tarea se encargó realizar un programa que al introducirle una cadena de texto genere una codificación Huffman.

David Huffman propuso un método estadístico que permitía asignar un código binario a cada caracter  La longitud de cada código no es idéntica para todos los caracteres: se asignan códigos cortos a los caracteres utilizados con más frecuencia, mientras que los caracteres menos frecuentes reciben códigos binarios más largos.

El algoritmo es simple:

1. Se recorre la cadena de texto y se hace una tabla de frecuencias para cada caracter.
2. Creamos un nodo por cada caracter, éste tendrá 2 valores, el caracter y la frecuencia.
3. Ordenamos de forma ascendente con respecto a las frecuencias y se toman los dos nodos con frecuencias menores.
4. Se agrega un nodo padre para los 2 nodos anteriores y su peso es la suma de frecuencias de ambos. Se agrega a la lista de nodos en su posición correspondiente y se eliminan los nodos hijos.
5. Se repite el proceso hasta que quede un solo nodo en la lista.

El gif de ejemplo de wikipedia:

Y el código es el siguiente:

Y su salida es la siguiente:

Pero ahora realizaré un par de experimentos; será el análisis del peor y el típico caso. Para ésto generaré un par de archivos de texto con las siguientes características.

• El peor caso, es donde existe la misma cantidad de frecuencias para cada caracter.
• El típico caso es donde las frecuencias son generadas aleatoriamente.

Analicé el tamaño original VS el tiempo que tarda, el resultado es el siguiente:

En teoría el tiempo del peor caso es menor puesto que todas sus frecuencias son iguales.

En cambio se puede ver que las compresiones son muy similares, siendo apenas un poco menor la del caso típico.

Finalmente comparo el radio de compresión, puesto que en el peor caso siempre hay frecuencias de caracteres fijos, parece mantener un radio constante.