Compresión de datos usando Huffman tree

El código de Huffman se utiliza para comprimir datos. Hace poco estuve buscando un ejemplo que funcione, pero no lo encontré, así que decidí hacerlo yo mismo.

Aquí no explicaré la teoría del código de Huffman, ya que hay mucha información acerca del mismo en Internet. Si quieres saber en qué consiste, puedes visitar los siguientes enlaces (hay muchas más páginas donde se explica, yo solo puse aquí algunas):

https://en.wikipedia.org/wiki/Huffman_coding

http://www.csc.lsu.edu/~kundu/dstr/4-huffman.pdf

http://cs-study.blogspot.com/2012/11/huffman-encoding.html

La implementación que comparto aquí, la saqué de los libros de Tenenbaum y de Sedgewick. En ninguno de ellos viene el código completo, por eso lo publico aquí. Está escrito en C++.

Primero, como simpre, vienen el encabezado del programa:

#include <bits/stdc++.h>

using namespace std;

Se necesitan dos estructuras, una para el árbol y una para los códigos de los caracteres comprimidos:

struct Codigo{

       int bits; // codigo, por ejemplo "10110" que equivale a 22 en binario

       int len; // n bits tomados desde la derecha

};

struct Nodo{

       int frecuencia;

       int father;

       int left;

       int right;

       bool isleft; // en vez de esta bandera, podría usarse el campo de frecuencia con un signo positivo para el hijo derecho y un signo negativo para el izquierdo

};

Después viene la declaración de los arreglos que se necesitarán. Se han declarado como globales para no tener que inicializarlos:

// mensaje

char mensaje[1000];

char mensaje_descomp[1000];

int len_mensaje;

// árbol de huffman

struct Nodo arbol[255]; // arbol

char alfabeto[128]; /// en este programa no es necesario, porque es el codigo ascii

struct Codigo codigos[128]; // códigos que genera este programa

int pq; // apuntador a la cola de prioridad

int pQueue[128]; // se usa para ir obteniendo siempre el par de elementos que aparecen con menor frecuencia

// mensaje comprimido

unsigned char comprimido[1000];

int cantidad_bits;

El arreglo del alfabeto no es necesario en este programa, porque se utilizan los caracteres del código ascii estándar. Sin embargo, se incluyó para que el programa quede más general y pueda usarse con cualquier conjunto de caracteres que se necesite.

Se necesita una cola de prioridad para obtener el elemento que aparece con la menor frecuencia en el texto. Podría usarse un montículo, sin embargo, como el conjunto de caracteres es pequeño, se uso una cola muy sencilla:

// Cola de prioridad

void pqinsert(int valor){ // Agrega un valor a la pQueue

       pQueue[++pq] = valor;

}

int pqmindelete(){ // Quita el siguiente valor (el de menor  valor) y lo devuelve

       int min, valor;

       min = 0;

       for (int i = 1; i <= pq; i++) // busca y toma el menor de todos

            if (arbol[pQueue[i]].frecuencia < arbol[pQueue[min]].frecuencia) {

                min = i;

            }

       valor = pQueue[min];

       pQueue[min] = pQueue[pq--];

       return valor;

}

Las siguientes dos funciones no son necesarias en realidad. Solo se usan para visualizar el código que se generó para cada caracter, y también el mensaje completo comprimido:

/// rutina para ver como quedaron los códigos

void Ver_Codigos(){

       int c;

       cout << "\n\n";

       // imprime el codigo

       for (int i = 0; i<128; i++){

             if (arbol[i].frecuencia>0){

                    cout << alfabeto[i] << "  " << arbol[i].frecuencia << "  ";

                    for (int k = codigos[i].len; k>0; k--){

                          if (codigos[i].bits & (1 << (k - 1))) cout << 1;

                          else cout << 0;

                    }

                    cout << "\n";

             }

       }

}

void Ver_Mensaje_Comprimido(){

       int f = 0;

       int bit = 128;

       // muestra el mensaje comprimido

       cout << "\n\nTamano comprimido: " << cantidad_bits / 8 << " bits\n\n";

       for (int i = 0; i<cantidad_bits; i++){

             if (comprimido[f] & bit) cout << 1;

             else cout << 0;

             bit /= 2;

             if (bit == 0){

                    bit = 128;

                    f++;

             }

       }

}

Las siguientes dos funciones sí son necesarias, aunque pudieron haber quedado como parte del programa principal (main). Las puse como funciones solo para mayor claridad:

Esta función obtiene el mensaje:

void Leer_Mensaje(){

       // Lee el mensaje

       gets(mensaje);

       len_mensaje = strlen(mensaje);

}

Esta función cuenta la frecuencia con la que aparece cada caracter en el mensaje.

void Contar_Frecuencia() {

       // cuenta cuantas veces aparece cada caracter en el mensaje

       for (int i = 0; i<len_mensaje; i++){

             arbol[mensaje[i]].frecuencia++;

       }

}

Por último viene el programa principal. Primero se declaran e inicializan algunas variables y apuntadores*:

int main() {

       int rootnodes = 0;

       int p, p1, p2, root;

       pq = -1;

       cantidad_bits = 0;

       Leer_Mensaje();

       Contar_Frecuencia();

       // tamaño original

       cout << "\n\nTamano original: " << len_mensaje << " bits.";

       ........

 }

*Nota. Aquí no se usaron apuntadores reales de memoria, sino que son variables que apuntan a localidades dentro de los arreglos.

Lo que sigue ahora, es preparar el alfabeto con el que está escrito el mensaje original. A la vez se va tomando la frecuencia con la que aparece cada caracter y se va agregando a la cola de prioridad. Es importante aclarar que en el arreglo del árbol, se usaron las primeras 127 celdas para almacenar ahí los caracteres originales, o sea, las hojas del árbol. El resto del árbol comienza a construirse a partir de la celda número 128.

       // prepara el arreglo del alfabeto y la cola de prioridad

       for (int i = 0; i<128; i++){

             alfabeto[i] = i; /// en este programa no es necesario, porque es el código ascii

             if (arbol[i].frecuencia>0) { // solo toma los caracteres que realmente están en el mensaje

                    pqinsert(i);

             }

       }

Ahora se construye el árbol. Para ello, se van tomando de la cola de prioridad los dos elementos que aparecen con menor frecuencia, y con ellos se construye un nuevo nodo que almacenará la frecuencia de ambos, y ese nuevo elemento se agrega a la cola:

       // construye el arbol

       for (p = 128; pq >= 1; p++){

             // toma los nodos p1 y p2 con menores frecuencias

             p1 = pqmindelete();

             p2 = pqmindelete();

             // los pone como hijos de un nuevo nodo

             arbol[p1].father = p;

             arbol[p1].isleft = true;

             arbol[p].left = p1;

             arbol[p2].father = p;

             arbol[p2].isleft = false;

             arbol[p].right = p2;

             arbol[p].frecuencia = arbol[p1].frecuencia + arbol[p2].frecuencia;

             pqinsert(p);

       }

Aquí ya está construido todo el árbol. A continuación se obtienen los códigos de los caracteres y se almacenan en el arreglo de códigos. Este paso no es absolutamente necesario, pues los códigos podrían irse tomando directamente del árbol. Para formar cada código, parte de una hoja, y va subiendo por el árbol hasta llegar a la raíz. Si era un hijo izquierdo le agrega un 0 al código, y si era un hijo derecho le agrega un 1.

       // extrae los códigos del árbol

       // Esto no es necesario. Solo es para probarlo. Podrían irse tomando

       // los códigos diretamente desde el árbol

       root = pqmindelete();

       for (int i = 0; i<128; i++){

             if (arbol[i].frecuencia>0){

                    // sube por el arbol

                    p = i;

                    while (p != root){

                          // aqui va construyendo el codigo

                          if (arbol[p].isleft) /* no le suma nada*/;

                          else codigos[i].bits += (1 << codigos[i].len); // le suma un 2^len

                          codigos[i].len++;

                          p = arbol[p].father;

                    } 

             }

       }

       Ver_Codigos();

En el campo "bits" quedan los bits que forman un código de un caracter (como están en una misma variable, representan un número); y en el campo "len" se almacena la cantidad de bits que tiene cada código. Así sabrá, del campo "bits", cuantos bits debe tomar realmente.

Ahora realiza la compresión. Para esto, solo va tomando cada caracter del mensaje original, y lo va reemplazando por su código huffman que ahora está en el arreglo de códigos:

       // Realiza la compresión. 

       int f = 0;

       int bit = 128;

       unsigned char c = 0;

       for (int i = 0; i<len_mensaje; i++){ // recorre todo el mensaje

             // toma el código de ese caracter

             for (int k = codigos[mensaje[i]].len; k>0; k--){

                    if (codigos[mensaje[i]].bits & (1 << (k - 1))) c += bit;

                    else c += 0;

                    cantidad_bits++;

                    bit /= 2;

                    if (bit == 0) { // ya terminó de llenar todo un byte, lo agrega al mensaje

                          comprimido[f++] = c;

                          c = 0;

                          bit = 128;

                    }

             }

       }

       // tal vez aún quedan caracteres por poner en el mensaje comprimido

       if (bit != 128) comprimido[f++] = c;

       Ver_Mensaje_Comprimido();

Debe recordarse que los caracteres se encuentran en las primeras 127 celdas del arreglo del árbol. También necesita ir llevando la cuenta de la cantidad de bits que tendrá el mensaje comprimido.

Por último, realiza la descompresión del mensaje, para volverlo a su estado original. Para ello, va tomando cada bit del mensaje comprimido, y recorre el árbol desde la raíz, bajando por la izquierda si es un 0 y bajando por la derecha si es un 1, hasta llegar a una hoja del árbol:

       // Realiza la descompresión 

       f = 0;

       bit = 128;

       c = comprimido[f];

       int m = 0;

       while (cantidad_bits>0){

             // recorre el árbol

             p = root;

             while (p >= 128) {

                    if (c&bit) { // baja por la derecha

                          p = arbol[p].right;

                    }

                    else {  // baja por la izquierda

                          p = arbol[p].left;

                    }

                    cantidad_bits--;

                    bit /= 2;

                    if (bit == 0){

                          c = comprimido[++f];

                          bit = 128;

                    }

             }

             // ya llegó a una hoja (las hojas están en los primeros 127 posiciones)

             mensaje_descomp[m++] = alfabeto[p];

       }

       // muestra el mensaje descomprimido

       cout << "\n\n" << mensaje_descomp;

Aquí puedes ver la salida que genera el programa con el mensaje: 

"Me gustan mucho las galletas!"

Tamaño original: 232 bits.

Tamaño comprimido: 108 bits.

100111010011101100010101101111110010111100000011000010001000001100111101001110111110010011010110111101010010

Aquí se muestran los códigos que generó para cada caracter:

   4  011

!  1  10010

M  1  10011

a  4  111

c  1  10000

e  2  1010

g  2  1011

h  1  10001

l  3  001

m  1  11000

n  1  11001

o  1  0000

s  3  010

t  2  1101

u  2  0001

Para hacer la cuenta se consideraron 8 bits para cada caracter del mensaje original. Si se consideran solo 5 bits (con 5 bits por caracter son suficientes para almacenar el mensaje original) se necesitarían 145 bits. Es un ahorro del 53% en el primer caso y del 25% en el segundo caso.

Descarga aquí el código fuente completo.