Ficha de clase número: 08 Fecha: Semana del 27/04 al 01/05 de 2009
descargar 63.2 Kb.
|
UTN Córdoba Ingenieria en Sistemas de Información Cátedra: Diseño de Lenguajes de Consulta Ficha de clase número: 08Fecha: Semana del 27/04 al 01/05 de 2009Docente: Ing. Valerio Frittelli Tema Principal: Desarrollo de un compresor de datos. Temas Particulares: Estructura básica de un compresor basado en el algoritmo de Huffman. Diagrama de clases. Algoritmos esenciales del compresor. 1.)Consideraciones iniciales. (Referencia: DLC09-Compresor)Luego de haber visto las ideas detrás del algoritmo de Huffman para sustituir un sistema de codificación binaria de longitud fija por otro de longitud variable; y luego de haber visto detalles de gestión de bits, podemos intentar el desarrollo de un prototipo de programa que permita la compresión efectiva de un archivo. Ese prototipo se brinda en el modelo DLC09-Compresor que acompaña a estas notas. El modelo brinda una clase Compresor, la cual provee los métodos comprimir() y descomprimir() que llevan a cabo las tareas indicadas sobre un archivo cuyo nombre toman como parámetro. El resto de las clases del modelo se presentaron ya, en ocasión del análisis del Algoritmo de Huffman. La primera (y quizás única) gran cuestión detrás del desarrollo del compresor, es que el programa debería ser capaz de procesar archivos de cualquier contenido: no debería comprimir sólo archivos de texto, sino archivos de cualquier origen: el archivo podría contener registros de datos (o sea, una mezcla de datos numéricos, de texto y boolean) o podría ser un archivo que contenga una imagen digitalizada en algún formato (bmp, jpg, etc.) o podría ser una planilla de cálculo o un archivo exe. Y con mayor o menor eficiencia el programa debería poder efectuar sobre él el proceso de compresión. Se podría pensar que esto realmente es un gran problema: al fin y al cabo, el algoritmo de Huffman está pensado para proveer codificación binaria de longitud variable en reemplazo de ASCII u otra de longitud fija, pero partiendo de la base de saber la frecuencia de aparición de cada caracter en el mensaje o archivo a comprimir. Y si se habla de caracteres, se está presuponiendo un archivo de texto... Sin embargo, el proceso puede generalizarse tranquila y transparentemente, simplemente pensando en bytes en lugar de pensar en caracteres... Todo archivo finalmente es una secuencia de bytes almacenada en disco, sin importar el sentido original que el creador del archivo dió a esos bytes. Si pensamos que en última instancia cada caracter se representa con un byte, y que un caracter no es otra cosa que un valor numérico entre 0 y 255, entonces no hay ningún problema en abrir un archivo cualquiera, leerlo byte por byte, y contar cuantas veces aparece ese byte en el archivo (tomando a cada byte que venga como si originalmente se hubiera grabado un caracter). Así, supongamos que alguien ha creado un archivo de datos y ha grabado en él las edades (supongamos valores short) de los alumnos de un curso. Por lo tanto, lo que se grabó fue una secuencia de pares de bytes (formato short). Si en el archivo se grabaron las siguientes edades {33, 35, 40, 65, 36} entonces quedó así:  Si ahora se quiere aplicar sobre ese archivo un proceso de compresión basado en Huffman, no hay problema: se debe contar cuántas veces aparece cada byte. Podemos ver que si miramos los bytes (y tomamos sus valores en base 10) tenemos que el valor 0 aparece cinco veces, el 33 aparece una vez, el 35 aparece dos veces, el 40 aparece una vez, el 65 aparece una vez y el 36 una vez. Podemos (si queremos) considerar que el 0, el 33, el 35, el 40, el 65 y el 36 son los caracteres 0, 33, 35, 40, 65 y 36 respectivamente de la tabla ASCII (o la que sea que se esté usando) pero no es estrictamente necesario hacerlo. Sólo necesitamos la distribución de frecuencias de cada byte tomado por su valor numérico:  2.)Estructura básica de un compresor basado en el algoritmo de Huffman.La clase Compresor presentada en el modelo DLC09-Compresor, contiene los siguientes atributos: public class Compresor { private ArbolHuffman ht; private RandomAccessFile fuente; private RandomAccessFile comprimido; private RandomAccessFile nuevo; private String errorCode; private int cantSignos; public Compresor() { cantSignos = 0; errorCode = "Compresor preparado"; } public String getErrorCorde() { return errorCode; } // resto de los métodos aquí... } El atributo ht es de la clase ArbolHuffman (según se presentó en la Ficha 06) y se usará para crear el árbol de Huffman que proporcione la codificación binaria de Huffman para cada byte del archivo. Los atributos fuente y comprimido son objetos de la clase RandomAccessFile, y se usarán para manejar el acceso al archivo original (fuente) y al archivo producido por el proceso de compresión (comprimido). Una función similar cumple el atributo nuevo (de la clase RandomAccessFile): al descomprimir, comprimido manejará el acceso al archivo que se quiere descomprimir y nuevo será el archivo a crear por la descompresión. El atributo errorCode tiene poco uso en este prototipo: es una cadena de caracteres mediante la cual se pretende en todo momento poder indicar en qué estado está el compresor (el único estado por ahora previsto es el de "Compresor preparado" asignado por el único constructor de la clase). El valor de ese atributo se obtiene por el método getErrorCode(). Y finalmente, el atributo cantSignos indica cuántos signos o caracteres (o sea, bytes) diferentes hay en el archivo a comprimir (recuerde que ese valor indica también cuántas hojas tendrá el árbol de Huffman). El único constructor provisto asigna un cero en ese atributo. La creación del árbol de Huffman se hace en particular cuando se comienza con el proceso de compresión de un archivo, y por eso no es el constructor quien hace la tarea: suponemos que el mismo compresor puede comprimir distintos archivos (con distintos árboles de Huffman) en distintos momentos. La clase provee entonces dos métodos esenciales: comprimir() y descomprimir(). El primero de ellos realiza los siguentes pasos:
El proceso de conteo de frecuencias de cada byte, se hace con el ya conocido algoritmo basado en un arreglo de contadores y acceso directo. Al final se recorre el arreglo para saber cuántos bytes realmente aparecieron en el archivo, y saber así el valor final del atributo cantSignos: int c[ ] = new int [ 256 ]; for(i=0; i<256; i++) { c[ i ] = 0; } while( fuente.getFilePointer() < fuente.length() ) { car = fuente.readByte(); short sc = (short) (car & 0x00FF); c[ sc ]++; } cantSignos = 0; for(i = 0; i < 256; i++) { if( c[ i ] != 0 ) { cantSignos++; } } Una vez creada la tabla de distribución de frecuencias, la creación del árbol se lleva delante de la siguiente forma: ht = new ArbolHuffman(cantSignos); // inicializamos el arbol de Huffman con los signos y sus frecuencias int ind = 0; for(i = 0; i < 256; i++) { if( c[i] != 0 ) { ht.setNodo((byte)i , c[i], ind); ind++; } } // armamos el árbol y obtenenos el código Huffman de cada signo ht.codificar(); El método setNodo() de la clase ArbolHuffman asigna los caracteres (bytes) en el arreglo que representa al árbol, y junto con esos caracteres almacena la frecuencia de cada uno. Con la frecuencia y el índice que cada caracter tiene en el arreglo que representa al árbol, va creando también la cola de prioridades para poder recuperar rápidamente los dos caracteres de menos frecuencia. El método codificar() de la clase ArbolHuffman es el que finalmente crea el árbol completo, tomando los dos de menor frecuencia, asignando a ellos un nodo unión, y repitiendo el proceso hasta llegar a la raiz. Al terminar de armarlo, obtiene la codificación Huffman de cada byte recorriendo hacia arriba el árbol y almacenando esos códigos en el arreglo de objetos CodigoHuffman (contenido en la clase ArbolHuffman – ver Ficha de Clase número 06) Un problema no menor que debe estudiarse es el siguiente: una vez comprimido el archivo, en algún momento se querrá lanzar el proceso de descompresión. Pero el descompresor deberá conocer el árbol de Huffman exacto que se usó para comprimir: no bastaría con que el descompresor tenga la tabla de frecuencias, pues sabemos que el árbol de Huffman no es necesariamente único para una tabla de frecuencias dada. Por lo tanto, el árbol usado en el proceso de compresión deberá almacenarse en el archivo comprimido, al inicio del mismo a modo de información de cabecera o metadatos. Esto implica que además de los propios datos comprimidos, el archivo tendrá información adicional sin la cual el descompresor no podría cumplir su trabajo. Pero esa información adicional agrega bytes al archivo, y podría darse entonces que al finalizar el proceso no se gane mucho en la compresión, o incluso que se pierda: si el archivo original es pequeño podría ocurrir que el archivo comprimido sea más grande que el original... Obviamente, en casos así la compresión no tiene sentido y debe usarse simplemente el archivo original. El método comprimir() almacena de la siguiente manera el árbol (y otra información valiosa, como el tamaño y el nombre del archivo original) en el archivo comprimido: // cantidad de bytes del archivo fuente long tArch = fuente.length(); // guardo en el archivo comprimido información para el descompresor... // ...empiezo guardando el nombre y la extensión del original... comprimido.writeUTF(fileName); // ... luego guardo la longitud en bytes del archivo original... comprimido.writeLong(tArch); // ... la cantidad de símbolos (o sea, la cantidad de hojas del árbol)... comprimido.writeInt(cantSignos); // ... ahora la tabla de símbolos tal como está en el arbol... for(i = 0; i < cantSignos; i++) { byte signo = ht.getSigno(i); comprimido.writeByte(signo); } // ... ahora el vector que representa al árbol... NodoHuffman a[ ] = ht.getArbol(); int n = cantSignos * 2 - 1; // cantidad total de nodos del árbol for(i = 0; i < n; i++) { // ...por cada nodo, guardar todos sus datos... comprimido.writeInt( a[i].getFrecuencia() ); comprimido.writeInt( a[i].getPadre() ); comprimido.writeBoolean( a[i].isLeft() ); comprimido.writeInt( a[i].getIzquierdo()); comprimido.writeInt( a[i].getDerecho()); } Note que posiblemente no sea necesario almacenar todos estos valores en el archivo: por ejemplo, al guardar el arreglo que representa al árbol no seria necesario guardar el valor del índice de los hijos izquierdo y derecho de cada hoja, pues sabemos que esos índices son –1. Simplemente, para las primeras cantSignos vueltas del ciclo no harían falta los dos últimos writeInt() que se ven en el ciclo... Este y otros detalles que permiten afinar la implementación, quedarán como tarea del alumno al desarrollar el Trabajo Práctico 2. Finalmente, luego de todo lo anterior, el método comprimir() lanza el proceso de compresión propiamente dicho. Para eso, se posiciona el file pointer al inicio del archivo original (había sido abierto y leido hasta el final para contar la frecuencia de cada byte), y se leen uno por uno, nuevamente, todos los bytes. Por cada byte, se recupera del árbol de Huffman su respectivo código binario Huffman. Al mismo tiempo, se cuenta con una variable salida de tipo con valor inicial 0x00 ( o sea, 0000 0000 ). Esa variable se declara de tipo short, aunque en realidad se usará sólo su segundo byte (el menos significativo): esto es así para evitar problemas de desbode, como se dijo en la Ficha 07. Usando operadores a nivel de bits de Java, cambiamos los bits que correspondan en la variable salida para que esta almacene la secuencia de Huffman del byte leido desde el archivo, llevando la cuenta de cuántos bits se cambiaron ya. Cuando esa cuenta llega a 8, el byte de salida se graba en el archivo comprimido y se vuelve a cero el valor de la variable salida para recomenzar el proceso. La secuencia de operaciones es la siguiente: // comienza fase de compresión (por fin...) short mascara = 0x0080; // el valor 0000 0000 1000 0000 short salida = 0x0000; // el valor 0000 0000 0000 0000 int bit = 0; // ¿en qué bit vamos? fuente.seek(0); // vuelvo el fp al principio while( fuente.getFilePointer() < fuente.length() ) { car = fuente.readByte(); // codigo Huffman del caracter tomado CodigoHuffman hc = ht.getCodigo(car); byte [ ]v = hc.getCodigo(); // el vector de códigos Huffman, tal como está en el árbol int ini = hc.getStartPos(); // posición inicial del código en el vector for(i = ini; i < CodigoHuffman.MAXBITS; i++) { if( v [ i ] == 1) { // si era 1, lo bajamos al byte de salida (si era cero, ni modo...) salida = (short)(salida | mascara); } mascara = (short) (mascara >>> 1); // corremos el uno a la derecha, rellenando con ceros. bit++; if (bit == 8) { //se llenó el byte de salida... comprimido.writeByte( (byte)salida ); // graba el menos significativo!!! bit = 0; mascara = 0x0080; salida = 0x0000; } } } if (bit != 0) { // grabar el último byte que estaba incompleto comprimido.writeByte( (byte)salida ); // graba el menos significativo!!! } comprimido.close(); fuente.close(); 3.)El proceso de descompresión.El método descomprimir() realiza el proceso inverso:
La recuperación de los datos del archivo original más la creación del árbol a partir de los datos recuperados desde el archivo comprimido es directa: // recupero el nombre del archivo original String original = comprimido.readUTF(); // creo el archivo con el nombre del original File f2 = new File(original); if( f2.exists() ) { f2.delete(); } nuevo = new RandomAccessFile(f2, "rw"); // y ahora, recupero todos los datos que el compresor dejó adelante... // ... empezando por el tamaño del archivo original... long tArch = comprimido.readLong(); // ... la cantidad de signos de la tabla (o sea, la cantidad de hojas)... cantSignos = comprimido.readInt(); // ...creo de nuevo el árbol en memoria... ht = new ArbolHuffman(cantSignos); // ... y recupero uno a uno los signos originales, guardándolos de nuevo en el árbol... int i; for(i = 0; i < cantSignos; i++) { byte signo = comprimido.readByte(); ht.setSigno(signo, i); } // ...ahora le toca al vector del árbol... int n = cantSignos * 2 - 1; // cantidad total de nodos del árbol for(i = 0; i < n; i++) { // ...por cada nodo, recuperar todos sus datos y volver a armar el árbol... int f = comprimido.readInt(); // frecuencia int padre = comprimido.readInt(); // padre boolean left = comprimido.readBoolean(); // es izquierdo? int hi = comprimido.readInt(); // hijo izquierdo int hd = comprimido.readInt(); // hijo derecho NodoHuffman nh = new NodoHuffman( f, padre, left, hi, hd ); ht.setNodo( nh, i ); } // habiendo llegado acá, el descompresor vuelve a pedir que se creen los códigos de Huffman ht.obtenerCodigos(); Y luego se lanza el proceso de descompresión propiamente dicho. Se lee cada byte del archivo comprimido, y se analizan uno por unos sus bits (usando máscaras y operadores a nivel de bits según se hizo en la Ficha 07). Cada vez que se detecta un 1 en el byte leido, se baja en el árbol por una rama derecha, o se baja por una izquierda si el bit analizado era un cero. Si se llega a una hoja del árbol al descender, se recupera el caracter (byte) que corresponde a esa hoja y se graba en el archivo de salida (que es el que se quiere regenerar...) El proceso se detiene cuando el número de bytes grabados coincide con la cantidad de bytes que tenía el archivo original: // de acá saco el vector que representa al árbol y el índice de la raiz... NodoHuffman [ ]v2 = ht.getArbol(); int raiz = v2.length - 1; // la raiz está en la última casilla del vector!!!! // comienza la fase de descompresión short aux; // auxiliar para desenmascarar short mascara; int bit, nodo = raiz; // comenzamos desde la raiz y vamos bajando long cantBytes = 0; // ¿cuántos bytes llevo grabados? // leo byte por byte el archivo comprimido while( comprimido.getFilePointer() < comprimido.length() ) { byte car = comprimido.readByte(); short sCar = (short) (car & 0x00FF); // para evitar desborde mascara = 0x0080; for(bit = 0; bit < 8 && cantBytes != tArch; bit++) { aux = (short)(sCar & mascara); if(aux == mascara) { // el bit en la posición "bit" era un uno... nodo = v2[nodo].getDerecho(); } else { // era un cero... nodo = v2[nodo].getIzquierdo(); } mascara = (short)(mascara >>> 1); // corremos el 1 a la derecha y rellenamos con ceros. if (v2[nodo].getIzquierdo() == -1 && v2[nodo].getDerecho() == -1) { // llegamos a una hoja... grabar el signo que está en ella byte sal = ht.getSigno(nodo); nuevo.writeByte(sal); cantBytes++; // volver a la raiz nodo = raiz; } } } nuevo.close(); comprimido.close();
Bibliografía: Si bien los profesores de la cátedra preparan una serie de fichas de consulta y guía para los temas de la asignatura, debe entenderse que para un dominio completo de estos temas y para el desarrollo óptimo de las tareas y ejercicios que se piden es fuertemente recomendable que los alumnos estudien e investiguen a fondo en otras fuentes. Va para ello la siguiente bibliografía de consulta y ampliación de temas:
|
