.
Implementación Del Algoritmo
Entrategia
La estrategia que proponemos para implementar un compresor (y luego un descompresor) de archivos basado en el algoritmo de Huffman es la siguiente.
1 - Recorrer el archivo que vamos a comprimir y contar cuantas veces aparece cada caracter. Utilizaremos un array de 0 a 255 posiciones ya que cada caracter (o mejor dicho cada byte) que leamos seguro estará dentro de ese rango.
2 - Crearemos (a partir del array del paso 1) una lista enlazada, ordenada por la cantidad de ocurrencias y (si es necesario) por el código ASCII del caracter (en caso de que existan caracteres con la misma probabilidad de ocurrencia).
3 - Procesaremos la lista para obtener el árbol Hufman.
4 - Procesamos el árbol para obtener los códigos Hufman y los nCod de los caracteres que componen el archivo que queremos comprimir. Los asignamos en el array.
5 - Volvemos a recorrer el archivo y escribimos en un nuevo archivo el código Hufman que reemplaza a cada caracter leido.
En si, la estrategia parece simple. De hecho es bastante lógica, pero lamentablemente nos encontraremos con algunas dificultades que le darán condimento a la resolución de este trabajo práctico.
Estructuras de Datos y Sección type
1:
2: // array de 16 bytes, lo usaremos para
3: // almacenar un codigo huffman de hasta 128 bits
4: T16b = array[0..15] of byte;
5:
6: RArray = record
7: n: comp; // cantidad de ocurrencias
8: cod: T16b; // codigo huffman (max 128 bits)
9: nCod: byte; // longitud del codigo (max 128)
10: end;
11:
12: // tipo para el array
13: TArray = array[0..255] of RArray;
14:
En este fragmento de la sección type vemos el registro RArray y el tipo TArray. Este es el tipo que define el array que utilizaremos como tabla para contar las ocurrencias de cada caracter y (luego) asignar el código Huffman y su longitud asociado a cada caracter.
Notemos que no necesitamos un campo para almacenar el caracter en si ya que utilizaremos la posición del array como código ASCII del caracter. Es decir: si tenemos que codificar una "A" utilizaremos la posición 65 del array. Si tenemos que codificar una "C" utilizaremos la posición 67, y así.
Aquí aparece el primer problema:
El árbol Huffman puede tener a lo sumo: (n+1)/2 niveles siendo n la cantidad de símbolos que pueden aparecer en el archivo. Como estamos considerando todos los caracteres (desde 0 hasta 255) resulta que (en el peor de los casos) el árbol Huffman podrá llegar a tener 128 niveles. Es decir: podremos llegar a tener un código de hasta 128 bits (o 16 bytes).
Si el código más largo fuese de (por ejemplo) 8 bits entonces podríamos utilizar un tipo de datos byte para almacenarlo. Si fuese de 16 bits podríamos utilizar un tipo word. Pero no existe ningún tipo entero de 16 bytes así que lo tendremos que "inventar". Lo llamamos T16b (tipo de 16 bytes) y lo implementamos sobre un array de 16 bytes (numerados de 0 a 15).
Veamos ahora el tipo para definir el nodo con el que implementaremos la lista enlazada y luego el árbol de Huffman.
1:
2: // puntero a nodo
3: PNodo = ^Nodo;
4:
5: // nodo con el que implementaremos la lista
6: // enlazada y (luego) el arbol huffman
7: Nodo = record
8: c: byte; // caracter
9: n: comp; // cantidad de ocurrencias
10: izq: PNodo; // hijo izquierdo del nodo
11: der: PNodo; // hijo derecho del nodo
12: sig: PNodo; // puntero al siguiente
13: end;
14:
Como vemos el mismo nodo nos servirá para las dos estructuras. Por eso tiene los campos izq y der (para implementar el árbol binario) y el campo sig (para implementar la lista enlazada).
Notemos que el campo n lo definimos de tipo comp. Esto se debe a que (como ya vimos) el nodo raíz del árbol tendrá una probabilidad de ocurrencia igual a la cantidad de caracteres del archivo que estemos procesando por lo tanto, si el archivo fuese muy grande (por ejemplo 100 MB) el campo n deberá soportar un valor de 1*1024*1024*100 = 1024 a la 2 por 100 = 104.857.600.
Solo queda por definir los tipos para los archivos que utilizaremos:
1:
2: // registro para el archivo len (lo analizaremos
3: // mas adelante)
4: RLen = record
5: c:byte;
6: n:comp;
7: end;
8:
9: // tipo para el archivo len
10: FLen = file of RLen;
11:
12: // tipo para el archivo a comprimir y para el
13: // archivo comprimido: simplemente un archivo
14: // de bytes
15: FByte = file of byte;
16:
Los tipos RLen y FLen los analizaremos más adelante, cuando sea necesario. El tipo FByte representa un archivo de bytes y nos permitirá leer cualquier tipo de archivo ya que, en definitiva, cualquier archivo no es más que una sucesión de bytes.
.........................,................... 
.
