.
Metodología de Trabajo
La implementación del algoritmo puede resultar verdaderamente compleja. Excede por mucho el alcance definido para una materia como "Programación I" o "Algoritmos Y Estructuras de Datos I".
Sin embargo, considero que el alumno puede ser capáz de programar pequeñas funciones y procedimientos con un nivel creciente de complejidad de forma tal que las funciones más simples faciliten el desarrollo del código de las funciones más complejas, y así hasta lograr un programa principal simple, claro y prolijo.
Por esto, el trabajo práctico consiste en desarrollar una serie de funciones con las cuales se podrá compilar el programa principal que se provee como parte del enunciado.
Archivos que se Adjuntan (descargar)
- szzip.pas - Programa principal del compresor
- untSzzip.pas - Librería de funciones del compresor
- szunzip.pas - Programa principal del descompresor
- untSzunzip.pas - Librería de funciones del descompresor
- untSz.pas - Librería de funciones y tipos de datos comunes
- testUntSz.pas - Programa para testear la unit untSz.pas
Análisis del Compactador
El siguiente código corresponde al programa principal del compactador.
szzip.pas
1:
2:uses untSz,untSzzip;
3:
4:var
5: arch:FByte;
6: p:PNodo;
7: arr:TArray;
8: cod:T16b;
9: nCod:integer;
10: i:integer;
11: nomArch:string;
12: nSize:comp;
13:
14:begin
15: if( paramCount()>0 ) then begin
16: nomArch:=paramStr(1);
17: end else begin
18: write('ERROR: Debe especificar el archivo ');
19: writeln('a comprimir');
20: writeln('USAGE: szzip nombreArchivo');
21: exit;
22: end;
23:
24: // abro el archivo que vamos a comprimir
25: assign(arch,nomArch);
26: reset(arch);
27:
28: // inicializo el array
29: inicializarArray(arr);
30:
31: // cuento las ocurrencias
32: nSize:=contarOcurrencias(arch,arr);
33:
34: // grabo el archivo len
35: grabarArchivoLen(arr,nomArch+EXTENSION_LEN);
36:
37: // creo la lista ordenada
38: p:=crearLista(arr);
39: //mostrarLista(p);
40: // crea el arbol a partir de la lista
41: listaToArbol(p);
42:
43: // recorre el arbol generando los
44: // codigos a asignar a cada caracter
45: setCeros(cod);
46: nCod:=0;
47: generarCodigos(arr, p, cod, nCod);
48:
49: // graba el archivo de codigos, es el array
50: // en un archivo...
51: grabarArchivoCod(arr,nomArch+EXTENSION_COD);
52:
53: // reseteo el archivo para volver a leerlo
54: reset(arch);
55: grabarArchivoDat(arr,arch,nomArch+EXTENSION_DAT);
56:
57: close(arch);
58:end.
59:
Lo primero que hacemos (línea 15) es verificar si nos están pasando como argumento en línea de comandos el nombre del archivo que tenemos que comprimir. Si no nos pasan este valor entonces mostramos un mensaje de error y una sugerencia sobre como se debe utilizar el programa.
En línea de comandos nos pasan el nombre del archivo a comprimir. Recordemos que tenemos que recorrerlo una vez para contar la cantidad de ocurrencias de cada caracter y luego recorrerlo por segunda vez para reemplazar cada caracter por su códificación Huffman correspondiente.
Tenemos un array (arr) de registros RArray en el que vamos a contar las ocurrencias de los diferentes caracteres del archivo. El array es de 0 a 255 posiciones y utilizaremos el mismo código ASCII del caracter como índice de acceso al array. En la línea 29 invocamos a la función inicializarArray para asignar cero al campo n de cada RArray y setear ceros en el campo cod (recordemos que es de tipo T16b).
La función contarOcurrencias (línea 32) recorre el archivo para contar cuantas veces aparece cada caracter, incrementa el campo n de los registros del array y retorna la cantidad total de caracteres leidos. Es decir: retorna el size (en bytes) del archivo que estamos procesando.
El objetivo de este trabajo práctico es entender e implementar una solución que permita comprimir y descomprimir archivos en base a la codificación Huffman. Para evitar que el alumno tenga que entrar en cuestiones y detalles ajenos a esto optamos por generar tres archivos de salida que contendrán la tabla de ocurrencias, los códigos Huffman y la información (codificada) contenida en el archivo original.
Por ejemplo: si el archivo que vamos a comprimir es dibujo.bmp entonces, luego de correr el compresor (szzip.exe) tendremos los siguientes archivos:
- dibujo.bmp.szlen - Contiene registros RLen con la cantidad de ocurrencias de cada caracter.
- dibujo.bmp.szcod - Contiene la codificación Huffman asignada a cada caracter.
- dibujo.bmp.szzip - Contiene la información de dibujo.bmp codificada.
En la línea 35 invocamos al procedimiento grabarArchivoLen que recibe el array y el nombre del archivo que va a generar. Recordemos que en nomArch tenemos el nombre del archivo original (en nuestro ejemplo es "dibujo.bmp") entonces la expresión:
nomArch+EXTENSION_LEN
será la concatenación de "dibujo.bmp" más ".szlen" (veremos más adelante que EXTENSION_LEN es una constante definida en untSz.pas que contiene el string ".szlen").
El procedimiento grabarArchivoLen recibe el array y el nombre del archivo a generar. Simplemente debe recorrer el array y para cada caracter que tenga al menos una ocurrencia en el archivo generamos un registro RLen y lo grabamos en el archivo de salida.
El archivo .szlen contendrá la cantidad de ocurrencias de cada caracter contenido en el archivo original.
En la línea 38 invocamos a la función crearLista que recibe el array y retorna un puntero al primer nodo de una lista enlazada cuyos nodos serán del tipo Nodo. La lista resultante estará ordenada ascendentemente por cantidad de ocurrencias y por código ASCII del caracter.
En la línea 41, el procedimiento listaToArbol "convierte" la lista en un árbol según se explicó anteriormente de forma tal que (ahora) p apunta a la raíz del árbol Huffman.
En la línea 47 el procedimiento generarCodigos (se provee con el enunciado en untSzzip.pas) recorre el árbol apuntado por p y asigna en los campos cod del array los códigos Huffman correspondientes.
Con los códigos Huffman generados solo queda grabarlos en un archivo con extensión .szcod (línea 51) y luego codificar y la información y grabarla codificada en un archivo con extensión .szzip (línea 55).
Todas las funciones y procedimientos que utilizamos en szzip.pas están definidas e implementadas en la unit untSzzip.pas que analizaremos a continuación.
untSzzip.pas
1:
2:unit untSzzip;
3:
4:
5:interface
6: uses math, untSz;
7:
8: // -----------------------
9: // DEFINICION DE FUNCIONES
10: // -----------------------
11:
12: // asigna cero a cada elemento del array
13: procedure inicializarArray(var arr:TArray);
14:
15: // recorre el archivo byte por byte, utilizando
16: // el byte leido para acceder directo a la
17: // posicion que corresponda en el array e
18: // incrementar el contador (ubicado en dicha
19: // posicion)
20: // retorna la cantidad de bytes leidos del archivo
21: function contarOcurrencias(var arch:FByte
22: ;var arr:TArray):comp;
23:
24: // graba un archivo de tipo FLen que contiene un
25: // registro RLen por cada caracter contenido en
26: // el array cuyo n sea mayor que cero
27: procedure grabarArchivoLen(arr:TArray
28: ;nomArchLen:string);
29:
30: // inserta un nodo en una lista respetando un
31: // orden ascendente por el campo n y (si hay
32: // nodos con igual n) por codigo ASCII
33: procedure insertarOrdEnLista(var lst, ndo: PNodo);
34:
35: // recorre el array y para cada posicion con n
36: // mayor que cero crea un nodo asignando en su
37: // campo c el valor del byte representado por la
38: // posicion del array y en su campo n el valor
39: // contenido en el array en dicha posicion.
40: // Crea una lista de nodos ordenada por el campo
41: // n de menor a mayor y retorna un puntero al
42: // primer nodo de la lista
43: // (utilizar el procedimiento insertarOrdEnLista)
44: function crearLista(arr:TArray):PNodo;
45:
46: // retorna un puntero al (hasta ahora) primer
47: // nodo de la lista e incrementa el puntero lst
48: // haciendo que apunte al segundo nodo.
49: // si la lista tiene un unico nodo entonces
50: // retorna un puntero a este
51: // nodo y hace que lst apunte a NIL
52: function sacarPrimerNodo(var lst:PNodo):PNodo;
53:
54: // recorre la lista (que esta ordenada de menor a
55: // mayor por el campo n) toma los dos primeros
56: // nodos, y crea un nuevo nodo
57: // con n = n1^.1+n2^.n y c = 255. Como hijo der.
58: // del nuevo nodo asigna a n1 y como hijo izq
59: // asigna a n2. Luego inserta ordenado el nuevo
60: // nodo en la lista.
61: // (utiliza la funcion sacarPrimerNodo y el
62: // procedimiento insertarOrdEnLista)
63: procedure listaToArbol(var p:PNodo);
64:
65: // recorre el arbol generando el codigo que le
66: // corresponde a cada hoja y cuando llega a una
67: //hoja asigna el codigo y su longitud en el array
68: // este procedimiento se provee completo, no es
69: // necesario desarrollarlo
70: procedure generarCodigos(var arr:TArray
71: ;var p:PNodo
72: ;var cod:T16b; nCod:byte);
73:
74: // genera un archivo FByte con la informacion
75: // contenida en el array,de la siguiente manera:
76: // por cada posicion del array con n>0 graba en
77: // el archivo: 1 byte con el codigo ASCII del
78: // caracter 1 byte con el nCod del caracter
79: // n bytes con los primeros bytes significativos
80: // del cod por ejemplo: si el nCod es de 5
81: // entonces el cod tiene un unico byte
82: // significativo, pero si nCod es 12 entonces cod
83: // tiene 2 bytes significativos
84: procedure grabarArchivoCod(arr:TArray
85: ;nomArchCod:string);
86:
87: // este procedimiento se provee completo, no es
88: // necesario desarrollarlo
89: procedure grabarBits(var archDat:FByte; cod:T16b
90: ;nCod:byte; var buffer:byte
91: ;var tamBuff:byte);
92:
93: // recorre el archivo arch (que ya viene
94: // reseteado), abre el archivo cuyo nombre es
95: // nomArchDat de tipo FByte y recorrer arch.
96: // Por cada caracter leido busca en el array su
97: // cod y e invoca al procedimiento grabarBits
98: // para que se ocupe de grabar el codigo
99: // bufferizando
100: // (utiliza el procedimiento grabarBits)
101: procedure grabarArchivoDat(arr: TArray
102: ;var arch:FByte
103: ;nomArchDat:string);
104:
105:
106:implementation
107:
108:// :
109:// :
110:// :
111:
112:end.
113:
El procedimiento inicializarArray (línea 13) simplemente debe recorrer el array arr y asignar cero al campo n ya que luego, cuando contemos las ocurrencias de los caracteres, solo consideraremos aquellas posiciones del array cuyo campo n sea mayor que cero.
La función contarOcurrencias (línea 21) debe recorrer el archivo arch y por cada byte leido acceder al array arr para incrementar su campo n. Esta función debe retornar la cantidad de bytes leidos del archivo que, como leerá el archivo completo, coincide con el tamaño del archivo expresado en bytes.
Como ya mencionamos, para realizar la codificación y (sobre todo) para poderla decodificar será necesario almacenar además la cantidad de ocurrencias de cada caracter. Esto lo haremos en un archivo separado cuya extensión será ".szlen" (se definió arbitrareamente).
El archivo .szlen debe ser un archivo de registros RLen y debe contener un registro por cada caracter diferente contenido en el archivo que estamos procesando (o comprimiendo). Según lo analizado más arriba esto lo podemos distinguir facilmente porque serán aquellos caracteres cuyo campo n en el array arr será igual a cero. Este trabajo lo realiza el procedimiento grabarArchivoLen (línea 27).
En las líneas 33 y 44 definimos los procedimientos insertarOrdenadoEnLista y crearLista con los cuales crearemos una lista enlazada de nodos tipo Nodo con la información contenida en el array arr. La idea es: en crearLista recorrer el array arr y por cada caracter cuyo n sea mayor que cero invocar a insertarOrdenadoEnLista para que inserte en la lista un nodo en representación de ese caracter.
En la línea 52 la función sacarPrimerNodo "desenlaza" y retorna un puntero al primer nodo de la lista que, como es una lista ordenada ascendentemente por cantidad de ocurrencias y por código ASCII, será el nodo correspondiente al caracter menos ocurrente. La función desenlaza el nodo pero no lo libera (no le hace dispose) ya que ese mismo nodo pasará a ser una hoja del árbol Huffman que crearemos con el siguiente procedimiento.
El procedimiento listaToArbol (línea 63) debe recorrer la lista mientras p (primer nodo de la lista) no tenga siguiente elemento. Por cada iteración sacamos el primer nodo de la lista, y luego volvemos a sacar el primer nodo de la lista (tenemos los dos menos ocurrentes). Creamos un nuevo nodo con n = a la suma de los n de los dos nodos que sacamos, asignamos cualquier valor a c y colocamos los dos nodos que sacamos de la lista como hijos derecho y izquierdo. Luego invocamos al procedimiento insertarOrdenado para que inserte el nuevo nodo (que ya es un pequeño árbol binario) en la lista.
En la línea 70 se define el procedimiento generarCodigos. Este procedimiento se provee completo y, dada su complejidad, no se espera que lo desarrolle el alumno.
Basicamente se trata de un recorrido en orden inverso sobre el árbol "acumulando" unos o ceros en cada llamada recursiva, según se esté accediendo al hijo derecho o izquierdo respectivamente.
En la línea 84 se define el procedimiento generarArchivoCod. Este procedimiento debe generar el archivo que contiene los códigos Huffman que (a través del árbol) asignamos a cada caracter. El archivo tendrá extensión ".szcod" y será un archivo de bytes (tipo FByte) con la siguiente estructura: por cada caracter con n mayor que cero grabaremos 1 byte con el caracter, 1 byte con su nCod y m bytes para grabar el código Huffman asociado al caracter. Recordemos que este código puede tener (en el peor de los casos) hasta 16 bytes. El valor m lo calculamos dividiendo el nCod del código del caracter por 8.
m = nCod div 8 + 1
Es decir: si nCod es 6 (seis bits) entonces nCod div 8 será cero, más 1 será 1: utilizamos solo un byte para almacenar ese cod. Pero si nCod es 14 entonces nCod div 8 será 1, más 1 es 2. Para almacenar un código de longitud 14 necesitaremos utilizar 2 bytes.
............................................. 
.
