El blog de Daniel Muñoz “No hay mayor riqueza que el conocimiento ni mayor pobreza que la ignorancia.” – Alí ibn Abi-Talib

1. huffman.cpp
2. huffman.h
3. compresor.cpp

A continuación explico el código (ver la explicación del algoritmo de huffman).

Escritura a un archivo.

No se puede escribir bit por bit a un archivo. Para que nuestro programa pueda ir escribiendo bit por bit la información requerida necesitamos crear una clase (objeto) que actúe como intermediario entre el algoritmo de compresión y el archivo. La llamaremos ARCH_OUT:

class ARCH_OUT
{
	FILE *Arch;
	unsigned char indice;
	unsigned char byte;
public:
	ARCH_OUT(unsigned char*,unsigned char*);
	~ARCH_OUT();
	bool Fallo(){return !Arch;}
	void Bit(unsigned int);
	void Buffer(unsigned char*,unsigned int);
};

Esta clase contiene tres variables. La primera es de tipo FILE y sirve para almacenar el puntero al archivo abierto.

Dijimos que no podemos escribir bit por bit a un archivo. Entonces haremos lo siguiente: Escribiremos los datos en un buffer de un byte, llenándolo bit a bit, y cuando esté lleno lo vaciaremos al archivo.

Entonces la segunda variable es la que nos indica en que bit del buffer vamos escribiendo, y la tercera variable es el buffer.

Ésta clase tiene un constructor y un destructor. El constructor se encarga de crear el archivo con el nombre y atributos especificados. El destructor tiene que escribir lo último que nos quedó en el buffer (si es que quedó) y cerrar el archivo.

También tiene tres métodos. El primero, llamado “Fallo”, retorna un valor verdadero si el archivo no pudo ser creado y un valor falso si fue creado exitosamente. El segundo, llamado “Bit”, recibe un bit y lo almacena en el buffer para guardarlo al archivo. Si éste último está lleno entonces vacía el buffer al archivo y pone a cero el índice.

El tercer método se encarga de escribir un buffer de bits al archivo. Esto es muy útil ya que dijimos que los caracteres codificados podían tener una longitud de bits variable. Entonces esta función simplemente recibe el puntero al buffer y la cantidad de bits que debe tomar de allí y los escribe al archivo. Debemos tener en cuenta que esta función escribirá primeramente los bits existentes en el buffer si los hay, luego los bits recién indicados, y por último dejará en el buffer los bits que no alcanzaron a completar un byte para ser escritos.

Lectura desde archivo.

Así como no se puede escribir a un archivo bit por bit, tampoco se puede leer desde un archivo bit por bit. Así que nuestra clase intermedia se llamará ARCH_IN:

class ARCH_IN
{
	FILE *Arch;
	unsigned char indice;
	unsigned char byte;
public:
	ARCH_IN(unsigned char*,unsigned char*);
	~ARCH_IN();
	bool Fallo(){return !Arch;}
	unsigned int Bit();
	unsigned int Byte();
	FILE *Base(){return Arch;}
};

Las tres variables tienen el mismo propósito que las de la clase anterior (ARCH_OUT). El constructor solamente abre el archivo y pone a cero el índice. El destructor simplemente cierra el archivo. El método “Fallo” tiene el mismo objetivo que el de la clase anterior.

El método “Bit” tiene se fija si hay bits en el buffer. Si los hay, lee el que corresponde e incrementa el índice. Si no los hay, lee un byte del archivo (cargando así el buffer) y lee el primer bit incrementando luego el índice.

El método “Byte” es utilizado para leer un byte desde el archivo. Nótese que parecería que uno simplemente podría leer ese byte normalmente con las funciones estándares del lenguaje. Pero esto no es así debido a que ese byte puede, por ejemplo, ser los últimos tres bits de un byte y los primeros 5 del siguiente. Éste fenómeno se da al leer el árbol.

En esta clase no es necesaria una función para leer una cantidad de bits variable. Esto se debe a que cuando leemos el archivo original leemos byte por byte, y cuando leemos el archivo comprimido leemos bit a bit o byte a byte, pero nunca otra longitud de bits.

Y por último el método “Base” devuelve un puntero al archivo abierto para que el descompresor pueda verificar por su cuenta, de corrido (sin sucesivas llamadas al método “Byte”), los primeros caracteres del archivo. Éstos contienen el sello “hfm” que indica que el archivo está comprimido mediante este algoritmo. Ese sello lo ponemos nosotros al crear el archivo comprimido.

Hojas del árbol compresor.

Las hojas del árbol creado al comprimir tienen métodos y variables diferentes a las utilizadas para descomprimir.

Ésta es la clase “HOJA”, utilizada para comprimir (también es utilizada por los nodos):

class HOJA
{
	unsigned int cCod;
	class HOJA *HojaIzquierda;
	class HOJA *HojaDerecha;
	class HOJA *pNIzq;
	class HOJA *pNDer;
	unsigned int lFrec;
	bool EsNodo;
public:
	HOJA(unsigned int Codigo){pNIzq=NULL;pNDer=NULL;
	HojaIzquierda=NULL;HojaDerecha=NULL;lFrec=0;
	cCod=Codigo;EsNodo=false;}
	HOJA(HOJA *Izquierda, HOJA *Derecha);
	~HOJA();
	unsigned int Frecuencia(){return lFrec;}
	void Frecuencia(unsigned int Cuanto){lFrec=Cuanto;}
	class HOJA *HojaDer(){return HojaDerecha;}
	void HojaDer(HOJA *Cual){HojaDerecha=Cual;}
	class HOJA *HojaIzq(){return HojaIzquierda;}
	void HojaIzq(HOJA *Cual){HojaIzquierda=Cual;}
	unsigned char Codigo(){return cCod;}
	bool MoverADer();
	bool MoverAIzq();
	void CrearCodigo(class CABECERA*,struct CODIGO*);
	void CrearCabecera(class ARCH_OUT*);
};

La variable “cCod” almacenará el código del carácter correspondiente a esa hoja si es que es una hoja y no un nodo. Esto último lo determina la variable booleana “EsNodo”. La variable “lFrec” almacenará cuantas veces se repite ese carácter en el archivo, o sea, su frecuencia.

Las variables “HojaIzquierda” y “HojaDerecha” apuntarán a la hoja inmediatamente a la izquierda o derecha mientras dure el proceso de conteo de frecuencias y ordenación según frecuencia. Recordemos que en este periodo el árbol no es un árbol todavía sino una alfombra de hojas.

Cuando ya hayamos recorrido todo el archivo y contado todas sus frecuencias y ordenado las hojas según su frecuencia empezaremos a armar el árbol. Las variables “pNIzq” y “pNDer” apuntarán a la hoja u nodo que se encuentre inmediatamente abajo a la derecha o abajo a la izquierda de este nodo. En el caso de que este objeto fuera una hoja y no un nodo, ambas variables estarían puestas a cero, ya que no tendrían nada abajo.

Veamos ahora el constructor. Como dijimos que este objeto puede ser tanto una hoja como un nodo, el constructor está sobrecargado. Así, si queremos crear una hoja llamaremos al constructor pasándole como argumento solamente el código del carácter para esa hoja. Si en cambio le pasamos dos argumentos, la clase interpretará que es un nodo y supondrá que le estamos pasando el puntero a la hoja izquierda y a la derecha.

El destructor también es interesante. Éste destruye primero las hojas u nodos que tenga abajo, si es que los tiene. De esta forma uno elimina el nodo de la raíz del árbol y éste se encarga de eliminar todo el árbol antes de desaparecer.

Como las variables del objeto son privadas y no públicas, los siguientes 7 métodos simplemente devuelven el valor de alguna de estas variables al que lo solicite.

Cuando queramos armar el árbol necesitaremos ir ordenando las hojas y nodos según su frecuencia. Para eso necesitaremos moverlas a la derecha o a la izquierda de la otra hoja u nodo. De eso se encargan los métodos “MoverADer” y “MoverAIzq”.

La función “CrearCabecera” es recursiva. La primera llamada debe ser a la raíz del árbol. Éste se encargará de ir llamando a cada nodo y hoja para que vayan escribiendo en el archivo su parte del código de la composición del árbol, que debe ser leído después por el descompresor para saber como era el árbol. Este método recibe como parámetro el puntero a la clase intermedia al archivo de salida.

La función “CrearCodigo” también es recursiva, y se encarga de crear los nuevos códigos para cada carácter de acuerdo a su ubicación en el árbol.

Hojas del árbol descompresor.

Este árbol es más simple que el anterior:

class HOJA_DESC
{
	class HOJA_DESC* pHDer;
	class HOJA_DESC* pHIzq;
	bool EsNodo;
	unsigned int Cod;
public:
	HOJA_DESC(class ARCH_IN*);
	~HOJA_DESC();
	unsigned int Descomprimir(class ARCH_IN*,FILE*,
		unsigned int);
};

Este árbol no tendrá una hoja u nodo a la izquierda ni a la derecha, sino solo abajo a la izquierda o la derecha. Esto es así porque este árbol no se arma ordenando frecuencias sino leyendo directamente como es el árbol. Por lo tanto tampoco tiene la variable que contiene la frecuencia de aparición del carácter, no es necesaria.

El constructor recibe como parámetro el puntero a la clase intermedia al archivo de entrada. El constructor es recursivo, según lo que encuentre en el archivo de entrada seguirá creando todas las hojas y nodos necesarios hasta terminar de construir el árbol. De esta forma es suficiente crear una hoja pasándole el puntero a la clase intermedia para que se construya todo el árbol automáticamente.

El método “Descomprimir” también es recursivo, y basta con llamarlo en la raíz del árbol para que descomprima todo el archivo.

Código del caracter.

Esta estructura guarda el código binario que representará a tal o cual caracter.

struct CODIGO
{
	unsigned char *Cod;
	unsigned int Tam;
};

Por ejemplo, si la letra ‘a’ (ASCII=97) ahora está ubicada dos nodos a la derecha, su código será 11 binario (3 decimal). Entonces en este ejemplo la variable Cod apuntaría a un array de un carácter que contendrá un 3 (decimal) y la variable Tam será igual a 2, ya que la longitud del código binario es igual a 2 (11, son dos unos).

Clase “CABECERA”.

Esta clase es utilizada por la clase “HOJA” para ir guardando el código de cómo fue armado el árbol para luego ser volcada al archivo. Esta información será necesaria cuando queramos descomprimir, ya que deberemos saber como es el árbol para este archivo.

class CABECERA
{
	unsigned char Buf[322];
	unsigned int nIndice;
public:
	CABECERA(){nIndice=0;}
	bool Bit();
	void Bit(bool);
	unsigned char Byte();
	void Byte(unsigned char);
	unsigned int Tamano(){return nIndice;}
	unsigned char *Buffer(){return Buf;}
	void Reset(){nIndice=0;}
	void Adelante(unsigned int nBits){nIndice+=nBits;}
	void Atras(unsigned int nBits){nIndice-=nBits;}
};

Los métodos sobrecargados “Bit” sirven para leer o escribir un bit en el buffer. Los métodos sobrecargados “Byte” sirven para leer o escribir un byte en el buffer. El método “Tamano” devuelve el tamaño en bits del buffer. El método “Buffer” devuelve un puntero al Buffer. Reset pone a cero el contador. “Adelante” se mueve un bit hacia delante y “Atrás” se mueve un bit hacia atrás.

Clase HUFFMAN.

La clase principal, “HUFFMAN”, es la única que debe ser definida en nuestro programa compresor. Ésta se encargará de definir todas las otras e inclusive creará y manejará los archivos con solo pasarle el nombre. Esta es la definición de la clase:

class HUFFMAN
{
	unsigned int lFrec[257];
	HOJA *pUltima;
	CODIGO Caracter[257];
	void UnoMas(unsigned char Cual){lFrec[Cual]++;}
	void CrearHojas();
	void OrdenarHojas();
	void CrearArbol();
	void CrearCodigos();
public:
	HUFFMAN();
	~HUFFMAN();
	bool Comprimir(char*);
	bool Descomprimir(char*);
	unsigned int Procesar(char*);
};

Las variables que contiene la clase son:

• lFrec. Es un array que contiene la frecuencia con la que se repite cada valor. 
• pUltima. Un puntero a la última hoja de nuestra alfombra. También será la raíz del árbol cuando sea creado. 
• Caracter. Es un puntero a las estructuras que contienen el código que ahora representará a cada carácter. 

El método “UnoMas” “avisa” que apareció una vez más dicho caracter. Los métodos “CrearHojas”, “OrdenarHojas”, “CrearArbol”, son obvios. El método “CrearCódigos” es llamado luego de la creación del árbol y lo que hace es crear los códigos para cada caracter de acuerdo a su ubicación en el árbol.

El método “Comprimir” recibe como argumento el nombre del archivo a comprimir. El método “Descomprimir” recibe como argumento el nombre del archivo a descomprimir. Y el método “Procesar” recibe como argumento un nombre de archivo, y él se encarga de ver si está comprimido o no. Si está comprimido lo descomprime y viceversa.

Programa.

Para implementar la clase HUFFMAN hice un programita que se utiliza de la siguiente manera: Uno arrastra un archivo con el ratón sobre el programita y lo suelta. Si el archivo está comprimido lo descomprimirá, y viceversa.

Este es el código:

#include "huffman.h"

void main(int argc, char* argv[])
{
	HUFFMAN *Compresor;
	Compresor = new HUFFMAN();
	if(argc > 1)
		Compresor->Procesar(argv[1]);
	delete Compresor;
}

(ver la implementación del algoritmo de huffman en c++)

El algoritmo de Huffman es un algoritmo de compresión de información. Este algoritmo está basado en la idea de que algunos caracteres aparecen muchas más veces que otros. Es especialmente eficaz en archivos de texto, donde más de la mitad de los caracteres difícilmente aparezcan alguna vez. Y entre los caracteres que aparecen, hay algunos que aparecen mucho más que otros.

Cada caracter se almacena en una secuencia de 8 bits. Este algoritmo se encarga de asignar códigos más cortos a los caracteres que más se repiten, y códigos más largos a los que menos se repiten. De esta manera a cada caracter se le asigna una longitud que puede variar entre 1 y 255 bits.

¿Cómo se hace esto?

Mediante un árbol binario. Veamos un ejemplo.

Supongamos que en un archivo tenemos el texto: “mi mama me mima”. Este texto ocupa 120 bits (15 bytes). Lo que propone el algoritmo de Huffman es lo siguiente:

1. Contemos cuantas veces aparece cada letra: m(6), i(2), “espacio”(3), a(3), e(1) (De ahora en adelante llamemos “~” al “espacio” para hacer las cosas más faciles).

2. Ordenamos las letras por su frecuencia, de mayor a menor:
   m(6)~(3)a(3)i(2)e(1) 

3. Sumamos las últimas dos “hojas”, y en su lugar ponemos un “nodo” que tendrá la frecuencia de las dos hojas sumadas (y hagamos esto sucesivamente).
   
   m(6)   ~(3)   a(3)   (3)// Sumamos.
   /   \
   i(2)  e(1)
   
   
   m(6)   ~(3)   (6)// Sumamos.
   /    \
   a(3)  (3)
   /    \
   i(2)  e(1)
   
   
   m(6)   (6)   ~(3)// Reordenamos por frecuencia.
   /    \
   a(3)  (3)
   /    \
   i(2)  e(1)
   
   
   m(6)   (9)// Sumamos.
   /    \
   (6)  ~(3)
   /    \
   a(3)    (3)
   /    \
   i(2)  e(1)
   
   
   (15)// Reordenamos y sumamos.
   /     \
   (9)    m(6)
   /    \
   (6)  ~(3)
   /    \
   a(3)    (3)
   /    \
   i(2)  e(1)
   
   

4. Ahora debemos crear una convención. En este ejemplo, convengamos: “0” a la izquierda y “1” a la derecha. De esta manera debemos recorrer el árbol hasta las hojas para crear los códigos de los caracteres. Por ejemplo, el carácter “i” está a: izquierda-izquierda-derecha-izquierda. Esto equivale a: 0010. Podemos hacer lo mismo con los otros, y obtendríamos estos códigos:
   m = 1.
   ~ = 01.
   a = 000.
   i = 0010.
   e = 0011.
   

5. Y ahora nos resta leer el archivo y por cada caracter leído escribir su correspondiente código en el archivo de salida. Para hacerlo más simple para nuestro análisis humano pondremos un punto entre cada código, pero en el archivo lo escribiremos todo junto. En el caso de “mi mama me mima”, tendríamos un archivo de salida así:
   1.0010.01.1.000.1.000.01.1.0011.01.1.0010.1.000.
   Esto suma un total de 33 bits. Mucho menos que el archivo original de 120 bits.

¿No habrá ambigüedades?

Ahora, como el lector sabe que en el archivo no escribiremos los puntos, se estará preguntando: ¿Y que pasa si al leer la información comprimida imagino los puntos en otras ubicaciones, que voy a interpretar?.

Hagamos la prueba, no le pongamos ningún punto: 100100110001000011001101100101000.

Pero recordemos seguir esta regla: Teniendo el árbol “a mano” situémonos en el nodo principal y vayamos leyendo la información. Cada vez que leamos un bit, movámonos al nodo inferior que esté a la derecha o a la izquierda según indique el bit. Cuando nos encontremos con que nos movimos a una hoja en vez de a un nodo, escribamos el carácter de la hoja, movámonos al principio del árbol y sigamos leyendo bit por bit desde donde nos habíamos quedado. Repitamos este proceso hasta el último bit.

Esto es lo que leeremos para nuestro ejemplo:

• Derecha (hoja). Ponemos la m. Volvemos arriba.
• Izquierda-izquierda-derecha-izquierda (hoja). Ponemos la i. Volvemos arriba.
• Izquierda-derecha (hoja). Ponemos ~. Volvemos arriba.
• Etc…

Al final habremos formado: mi mama me mima. Y no habrá posibilidades de formar otra frase con ese árbol y esa secuencia de bits. Haga algunos intentos y quedará convencido de que es así.

Debemos notar que para cada archivo habrá un árbol diferente de acuerdo a las frecuencias de los caracteres en ese archivo en particular, y una secuencia de bits diferente de acuerdo a la ubicación de los caracteres.

Ahora el lector habrá notado que el descompresor abre el archivo comprimido y “ve” la secuencia de bits, pero se estará preguntando ¿cómo sabe el descompresor cual es el árbol de ese archivo? ¡Claro, habíamos dicho que para cada archivo hay un árbol y una secuencia de bits diferentes! Así que el descompresor también deberá conocer el árbol.

Guardando el árbol.

Veamos una manera sencilla de guardar el árbol, aunque no es tan sencillo explicarlo.

Para guardar la secuencia de bits nosotros sabíamos si estábamos en un nodo o en una hoja, y lo que anotábamos era la dirección hacia la que nos movíamos.

Ahora hagamos justamente lo opuesto. Recorramos el árbol en una dirección (secuencia) conocida y anotemos si estamos en un nodo o en una hoja, y si estamos en una hoja anotemos su caracter.

Para eso convengamos esta regla: Cada nodo/hoja al ser llamado anotará un 1 si es una hoja y un 0 si es un nodo. Luego si es una hoja anotará los 8 bits que representan el caracter de esa hoja. Y si es un nodo, llamará al nodo/hoja de la izquierda y luego al de la derecha para que hagan lo mismo (recursivamente). Por último, después de hacer todo lo que tiene que hacer, devolverá “el mando” al nodo que lo llamó.

De esta forma nuestro árbol de ejemplo (más abajo) quedaría guardado así:

1. (15) dice: Soy nodo, escribo 0. Llamo a nodo (9)
2. (9) dice: Soy nodo, escribo 0. Llamo a nodo (6).
3. (6) dice: Soy nodo, escribo 0. Llamo a hoja a(3).
4. a(3) dice: Soy hoja, escribo 1. Escribo mi código: 01100001. Retorno a (6).
5. (6) dice: Ahora llamo a nodo (3).
6. (3) dice: Soy nodo, escribo 0. Llamo a hoja i(2).
7. i(2) dice: Soy hoja, escribo 1. Escribo mi código: 01101001. Retorno a (3).
8. (3) dice: Ahora llamo a hoja e(1).
9. e(1) dice: Soy hoja, escribo 1. Escribo mi código: 01100101. Retorno a (3).
10. (3) dice: Retorno a (6).
11. (6) dice: Retorno a (9).
12. (9) dice: Ahora llamo a hoja ~(3).
13. ~(3) dice: Soy hoja, escribo 1. Escribo mi código: 00100000. Retorno a (9).
14. (9) dice: Retorno a (15).
15. (15) dice: Ahora llamo a hoja m(6).
16. m(6) dice: Soy hoja, escribo 1. Escribo mi código: 01101101. Retorno a (15).
17. (15) dice: Terminamos (retorno a quien sea que haya preguntado el código del árbol).

Árbol:

(15)
/     \
(9)    m(6)
/    \
(6)  ~(3)
/    \
a(3)    (3)
/    \
i(2)  e(1)

Tamaño de la descripción del árbol.

El código que se acaba de generar sería el siguiente:

0001011000010101101001101100101100100000101101101 (49 bits).

Éste código debe ir antes que la secuencia de bits del archivo para que el descompresor pueda armar el árbol antes de leer la secuencia de bits. En total el archivo generado tendrá 82 bits. Esto equivale a 10,25 bytes. Pero como no podemos guardar medio byte, tendremos que redondear a 11 bytes. Así un archivo de 15 bytes quedó reducido a 11 bytes.

Note el lector que casi el 60% del archivo comprimido está ocupado por la descripción del árbol. Ya que una descripción de árbol varía entre los 0 bits, en caso de un archivo vacío, y los 2559 bits (320 bytes), en caso de que un caracter se repita más que todos los otros juntos, y que el siguiente que más se repite se repita más que todos los otros que se repiten menos que él juntos y así sucesivamente, vemos que la descripción del árbol ocupará a lo sumo 320 bytes.

Esto es prácticamente insignificante para archivos de varios KB, por lo tanto el porcentaje de compresión va a ser mayor que para este ejemplo ya que aquí más del 59,75% del archivo es la pura descripción del árbol, (en este caso es muy significante).

Leyendo la descripción del árbol.

Para descomprimir el archivo basta armar el árbol a medida que vamos leyendo su descripción. Dejémoslo como tarea para el lector… Está bien, hagámoslo juntos. En la descripción leemos:
0: Dibujamos un nodo.
( )
/    \

0: Dibujamos otro nodo.
( )
/    \
( )
/    \

0: Dibujamos otro nodo.
( )
/    \
( )
/    \
( )
/    \

1: Dibujamos una hoja y leemos los 8 bits de su código (01100001=a).
( )
/    \
( )
/    \
( )
/    \
a( )

Nos movemos al próximo lugar vacío y leemos: 0: dibujamos un nodo.
( )
/    \
( )
/    \
( )
/    \
a( )    ( )

1: Dibujamos una hoja y leemos los 8 bits de su código (01101001=i).
( )
/    \
( )
/    \
( )
/    \
a( )    ( )
/    \
i( )

1: Dibujamos una hoja y leemos los 8 bits de su código (01100101=e).
( )
/    \
( )
/    \
( )
/    \
a( )    ( )
/    \
i( )  e( )

1: Dibujamos una hoja y leemos los 8 bits de su código (00100000=~).
( )
/    \
( )
/    \
( ) ~( )
/    \
a( )    ( )
/    \
i( )  e( )

1: Dibujamos una hoja y leemos los 8 bits de su código (01101101=m).
( )
/    \
( ) m( )
/    \
( ) ~( )
/    \
a( )    ( )
/    \
i( )  e( )

El nodo principal devuelve el control al que lo llamó. Y podemos ver que esto ocurre justamente cuando se terminan los bits. No hay ambigüedades.

Esto es todo.

Bueno, con esta información ya somos capaces de comprimir y descomprimir archivos mediante el algoritmo de Huffman. Ahora veremos como implementar el algoritmo de huffman en c++.