El código de Huffman

La codificación de Huffman es un método de compresión de datos sin pérdida de información. Esta compresión se lleva a cabo creando un código para el conjunto de símbolos del mensaje a comprimir. El código conseguido con este método es de longitud variable, la representación de cada símbolo tiene un número distinto de bits, y en ningún caso la representación de un símbolo es prefijo de la representación de otro símbolo. Este código es el más eficiente que se puede conseguir, medido en la longitud media por cada símbolo en el mensaje codificado.

Para construir el código de Huffman de un conjunto de símbolos, se va construyendo un árbol binario, guiándose por la frecuencia de los caracteres del conjunto de símbolos. El árbol se construye de abajo a arriba, desde las hojas hasta la raíz. Inicialmente, se crea un conjunto de árboles con un único nodo. Cada uno de estos árboles contiene en su raíz uno de los símbolos y su frecuencia. A partir de ahí, los árboles se van combinando para formar árboles más grandes hasta tener un solo árbol. En cada paso se escogen los dos árboles de frecuencias menores y se combinan en otro cuya frecuencia será la suma de ambos. Los nodos intermedios del árbol no representan ningún símbolo.

Por ejemplo, para los caracteres y frecuencias ((a, 25), (b, 15), (c, 50), (d, 20)), se tiene la siguiente secuencia hasta llegar al árbol final:

(a, 25)  |     (a, 25)     |     (c, 50)          |         (*, 110)
         |                 |                      |          /     \
(b, 15)  |     (c, 50)     |     (*, 60)          |      (*, 60)  (c, 50)
         |                 |     /      \         |      /      \
(c, 50)  |     (*, 35)     | (a, 25)  (*, 35)     |  (a, 25)  (*, 35)
         |     /     \     |          /     \     |           /     \
(d, 20)  | (b, 15) (d, 20) |      (b, 15) (d, 20) |       (b, 15) (d, 20)

Una vez construido el árbol, se puede obtener el código de Huffman para ese conjunto de símbolos. El código de cada símbolo viene dado por el recorrido desde la raíz del árbol hasta la hoja que contiene el síbolo. Si se baja por el hijo izquierdo, se incluye un '0', por ejemplo en el código de ese síbolo. Si se baja por la derecha se incluye un '1'. Haciendo un recorrido del árbol, por ejemplo en inorden, se puede obtener el código para todos los símbolos.

Para el árbol anterior, el código resultante sería:

((a, 00), (b, 010), (d, 011), (c, 1))

En esta práctica se hará uso de varios tipos abstractos de datos.

Árbol binario para ir construyendo el árbol de frecuencias. El contenido de los nodos debe incluir un símbolo, que en la práctica serán caracteres, y su frecuencia.
Un contenedor que guarde los árboles intermedios que se vayan creando. Hay dos opciones, usar un tipo que los mantenga ordenados los elementos en función de la frecuencia, como una cola de prioridad, o una estructura donde, en principio, por su definición no se mantengan ordenados los elementos, como una lista posicional, y escoger posteriormente en cada iteración los elementos menores, bien insertando los elementos ordenadamente o bien haciendo una búqueda a lo largo de toda la estructura. La cola de prioridad se implementará mediante un montículo basado en memoria estática.
Una estructura para almacenar los caracteres y su frecuencia o número de repeticiones correspondiente.

Algunos de estos tipos han de ser clases genéricas, plantillas, instanciadas con los tipos apropiados. Hay que definir los tipos apropiados para los nodos del árbol y los elementos de las estructuras lineales.

Uso de la plantilla priority_queue de la STL de C++

La Standard Template Library (STL) de C++ incluye, entre otras cosas, una colección de tipos contenedores. Estos tipos están implementados mediante plantillas de clases. Algunos de esos tipos ofrecen la funcionalidad que se necesita en esta práctica, por lo que se puede implementar ésta haciendo uso de ellos.

Se puede usar la plantilla de clase priority_queue. Esta clase implementa una cola de prioridad, similar a la vista en clase. Se insertan elementos y se devuelve y se borra el de mayor valor. El tipo de los elementos de la cola de prioridad tiene que tener definida la operación <.

Las operaciones necesarias para el manejo de la clase queue en esta práctica son:

Hay que incluir el fichero <queue>, donde se define el tipo.
La instancia de la plantilla de clase se hace normalmente. Por ejemplo, priority_queue<int> declara una cola de prioridad que contiene enteros.
void push(const &T). Inserta un elemento del tipo T en el objeto.
bool empty(). Devuelve true si y sólo si no hay elementos en la cola.
T & top(). Devuelve el elemento que está en el frente de la cola. La precondición de esta operación es que la cola no esté vacía.
void pop(). Elimina el elemento que está en el frente de la cola. La precondición de esta operación es que la cola no esté vacía.

La cola de prioridad se puede usar para ir almacenando ordenadamente los árboles intermedios. Para que esto tenga sentido, es necesario dotar a los árboles de una operación que permita saber si un árbol es menor que otro. El orden entre los árboles viene dado por la relación entre la frecuencia de su raíz, por lo que el operador < para árboles devolverá la relación entre sus raíces y, más concretamente, entre las frecuencias de sus raíces. Hay que notar que interesa que esté en el frente de la cola de prioridad el árbol con menor peso mientras que en la cola de prioridad se pone en el frente el elemento de mayor valor.

Se pide que, haciendo uso del tipo Arbol binario suministrado, del tipo Par que también se da, y de la clase priority_queue de la STL, se construya un programa principal que admita por teclado una secuencia de pares letra-repeticiones y muestre por pantalla el código de Huffman para cada una de tales letras.

Nota:

Opcionalmente puede usarse la clase Map para almacenar un par letra-repeticiones y la función

bool operator<(const &T t1, const &T t2);

para establecer cuando un arbol es menor que otro.