Algoritmo de Huffman

UNIVERSIDAD CENTRAL DE VENEZUELA
FACULTAD DE CIENCIAS
ESCUELA DE COMPUTACIÓN
ALGORITMOS Y ESTRUCTURAS DE DATOS

PROYECTO 2: DROPSQUARE
La famosa empresa de almacenamiento de datos en la nubeDropSquare ha decidido regalar a sus suscriptores en el mes
de su cumpleaños una cantidad extra de Gigabytes (aka este mes :-) ). La única condición de DropSquare a sus
suscriptores es que empleen unesquema de codificación de datos tal que puedan maximizar el espacio adicional ofrecido.
La compresión de datos será bajo el esquema de codificación Huffman (1952) el cual resulta ideal para ambaspartes.
Para simplificar las acciones tanto para DropSquare como para los cumpleañeros, solo se emplearán almacenar archivos
de texto. La idea es generar algoritmos para la compresión y descompresiónde los archivos empleando una interfaz
amigable para el usuario. Dicha interfaz debe mostrar los siguientes datos asociados a la compresión:


Codificar un texto y mostrarlo decodificado.

El texto codificado debe ser mostrado empleando ASCII extendido (8 bits)



Porcentaje de compresión. Por ejemplo, el texto de entrada contiene 40 bytes y con la codificación Huffman arroja
unasalida de 25 bytes, el % a mostrar es 37.5% (considere el valor inferior más cercano con 1 decimal de precisión)



Frecuencia de cada una de las letras del alfabeto de entrada (mostrar las 26letras)



El alfabeto de entrada consistirá de letras de la tabla ASCII extendido.

La entrada de datos se realizará de dos formas posibles: escribiendo un texto o a través de un archivo tantopara un texto a
decodificar o un texto decodificado.
Algoritmo básico
El algoritmo de Huffman de codificación construye un árbol binario completo y consiste básicamente en efectuar los
siguientespasos:
1. Leer el texto de la entrada
2. Ordenar los caracteres basados en su frecuencia en el texto (número de apariciones)
3. Construir el árbol de códigos Huffman
4. Recorrer el árbol para...