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

Codigo completo del compresor en c++:

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;
}