X-Git-Url: https://git.llucax.com/z.facultad/75.06/jacu.git/blobdiff_plain/f8b9eb5ec2722be52af3b5cbd58ad4cd6b0893dc..7e0696972e32e6cab306020b0fca853810087211:/doc/InformeTP3.lyx diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx index a486f6d..b6c4dac 100644 --- a/doc/InformeTP3.lyx +++ b/doc/InformeTP3.lyx @@ -28,7 +28,7 @@ Organización de Datos (75.06) \newline -Trabajo Práctico +Trabajo Práctico 3 \newline JACU \layout Author @@ -59,7 +59,7 @@ Primera Entrega, 28 de Junio del 2004 \layout Chapter -Introducción al compresor +Introducción \layout Section Método de compresión utilizado @@ -73,18 +73,34 @@ Block Sorting + Move to front + Huffman Est \layout Standard -Si bien un compresor estadístico final más robusto como el PPMC o bien un - Huffman Dinámico podrían producir ratios de compresión un tanto mejores, - a fines de resguardar la confección de un compresor estable y poseer tiempo - suficiente para realizar pruebas y optimizaciones, se optó por el Huffman - Estático, al cual se lo contrapuso con una implementación Third Party de - uno dinámico, y las diferencias fueron mínimas tanto en tiempo como en - compresión, descartando así la posibilidad de extender el estático al dinámico. +Si bien un compresor estadístico final más robusto como el +\series bold +PPMC +\series default + o bien un +\series bold +Huffman Dinámico +\series default + podrían producir niveles de compresión un tanto mejores, a fines de resguardar + la confección de un compresor estable y poseer tiempo suficiente para realizar + pruebas y optimizaciones, se optó por el +\series bold +Huffman Estático +\series default +. + No obstante, se comparó con una implementación de +\series bold +Huffman Dinámico +\series default + de ejemplo obtenida de Internet y se observaron que los resultados eran + muy similares, a veces obteniendo un mejor nivel de compresión y a veces + obteniendo uno peor, descartando luego de estas pruebas la posibilidad + de extender el estático al dinámico. \layout Standard Además de la capacidad natural de todo compresor (esto es, de comprimir/descompr -imir), la implementación que describiremos a continuación cuenta con features - especiales que se verán detallados en la +imir), la implementación que describiremos a continuación cuenta con característ +icas especiales que se verán detallados en la \series bold sección \begin_inset LatexCommand \ref{sec:Features-Especiales} @@ -93,108 +109,136 @@ secci \series default -, los cuales a saberse son: +. + Dichas características se resumen a: \layout Itemize -Persistencia del Modelo Orden-0 de Huffman (AKA: Huffman Canónico) +Persistencia del Modelo Orden-0 de +\series bold +Huffman Estático +\series default + ( +\series bold +Huffman Canónico +\series default +) \layout Itemize -ZeroGroupping (Abreviación de ceros a la salida del MTF) -\layout Itemize -Word-Scaping (Optimización para textos detallada posteriormente) -\layout Section +\series bold +Zero Grouping +\series default + (Agrupación de Ceros, aplicado a la salida del +\series bold +MTF +\series default +) +\layout Itemize -Documentación -\layout Standard -Para obtener una documentación de la API, se incluye en formato HTML en - el CD-ROM la documentación generada con Doxygen para los distintos componentes - del compresor. - Esta documentación se encuentra en el directorio -\family typewriter -doc/api/html -\family default -. +\series bold +Word-Scaping +\series default + (Optimización para textos detallada posteriormente) \layout Section Modo de uso \layout Standard Antes de pasar a la descripción de la implementación de nuestro compresor, - detallaremos a continuación las instrucciones pertinentes para la correcta - y óptima utilización de nuestro compresor. + detallaremos el modo de uso. \layout Subsection -Invocación standard +Invocación simple \layout Paragraph \series medium Como hemos ancitipado anteriormente, el compresor cuenta con features especiales - que pueden ser utilizados a través de flags en la invocación del programa. + que pueden ser utilizados a través de opciones en la invocación del programa. Antes de pasar a su descripción, notamos la invocación general para comprimir - y descomprimir un archivo. -\layout Paragraph + y descomprimir un archivo como se pidió en el enunciado +\begin_inset Foot +collapsed true +\layout Standard -\series medium -Sea -\series default +Nótese que +\family typewriter +grupo11 +\family default + es un enlace simbólico a +\family typewriter jacu +\family default +, nombre real del ejecutable. +\end_inset + +. +\layout Paragraph* + +Compresión: +\layout Standard + + +\family typewriter \series medium - el archivo ejecutable correspondiente al compresor, tendremos la siguientes - formas básicas de invocación: -\layout Paragraph +./grupo11 -c [-t volsize] sourcefile targetfile +\layout Standard + -Compresión: \series medium -./jacu -c [-t volsize] sourcefile targetfile -\newline Siendo -\noun on +\family typewriter sourcefile -\noun default +\family default el nombre del archivo a comprimir y -\noun on +\family typewriter targetfile -\noun default +\family default el nombre del archivo comprimido. -\layout Paragraph +\layout Paragraph* + +Descompresión: +\layout Standard + + +\family typewriter +\series medium +./grupo11 -d sourcefile targetfile +\layout Standard + -Descompresión: \series medium -./jacu -d sourcefile targetfile -\newline Siendo -\noun on +\family typewriter sourcefile -\noun default +\family default el nombre del archivo a descomprimir y -\noun on +\family typewriter targetfile -\noun default +\family default el nombre del archivo descomprimido. -\layout Quote - +\layout Paragraph* -\series bold Nota: -\series default - El flag -\series bold +\layout Standard + +La opción +\family typewriter -t -\series default - es un flag opcional que permite generar un archivo comprimido multivolumen, - donde -\series bold -volsize -\series default +\family default + pcional que permite generar un archivo comprimido multivolumen, donde volsize será el tamaño en kbytes de cada volúmen, excepto el último que podrá ser menor. \layout Subsection -Execution Flags + +\begin_inset LatexCommand \label{sub:Execution-Flags} + +\end_inset + +Opciones adicionales \layout Standard Ademas de los flags standards que hemos visto recién, nuestro compresor @@ -205,66 +249,159 @@ Ademas de los flags standards que hemos visto reci \layout List \labelwidthstring 00.00.0000 --c Indica que se desea comprimir un archivo + +\family typewriter +-c +\family default + Indica que se desea comprimir un archivo (mutualmente exclusivo con +\family typewriter +-d +\family default +, al menos uno debe estar presente). \layout List \labelwidthstring 00.00.0000 --d Indica que se desea descomprimir un archivo + +\family typewriter +-d +\family default + Indica que se desea descomprimir un archivo (mutualmente exclusivo con + +\family typewriter +-c +\family default +, al menos uno debe estar presente). \layout List \labelwidthstring 00.00.0000 --t Indica que se desea un archivo comprimido en multivolumenes. - Seguido a dicho flag se debe indicar el tamaño en kbytes que se desea para + +\family typewriter +-t +\family default + Indica que se desea un archivo comprimido en multivolumenes. + Seguido a dicho flag se debe indicar el tamaño en KBytes que se desea para los volúmenes. \layout List \labelwidthstring 00.00.0000 --z Puede ser utilizado unicamente en una compresión y activa el feature - de ZeroGroupping + +\family typewriter +-z +\family default + Puede ser utilizado únicamente en una compresión y activa el feature de + +\series bold +Zero Grouping +\series default +. \layout List \labelwidthstring 00.00.0000 --s Puede ser utilizado unicamente en una compresión y graba el modelo de - orden-0 de huffman generado durante la compresión del archivo (en un archivo - de extensión . + +\family typewriter +-s +\family default + Puede ser utilizado únicamente en una compresión y graba el modelo de orden-0 + de \series bold -ftb +Huffman +\series default + generado durante la compresión del archivo (en un archivo de extensión + +\family typewriter +\series bold +. \series default +ftb +\family default ), para que luego pueda ser reutilizado en otra compresión. \layout List \labelwidthstring 00.00.0000 --m Puede ser utilizado únicamente en una compresión y carga un modelo de - orden-0 de huffman para ser utilizado en la compresión del archivo especificado -, evitando el escaneado del archivo a comprimir. + +\family typewriter +-m +\family default + Puede ser utilizado únicamente en una compresión y carga un modelo de orden-0 + de +\series bold +Huffman +\series default + para ser utilizado en la compresión del archivo especificado, evitando + el escaneado del archivo a comprimir. Deberá ser sucedido por el nombre del archivo que posee el modelo. -\layout Subsection +\layout List +\labelwidthstring 00.00.0000 + + +\family typewriter +-q +\family default + Especifica la calidad (nivel) de compresión. + Puede ser un valor entre 0 y 9, siendo 0 el menor nivel de compresión (más + rápido) y 9 el máximo (más lento). + Por omisión se utiliza un nivel de compresión 5. +\layout Subsubsection* Ejemplos \layout Standard -Damos a continuación unos breves ejemplos de invocación utilizando los flags - opcionales: +Damos a continuación unos breves ejemplos de invocación utilizando diferentes + opciones: \layout Itemize -Compresión multivolumen (de 1024 kbytes each): -\series bold -./jacu -c -t 1024 libro.txt libro.z +Compresión multivolumen (de 1024KB, cada uno): +\family typewriter + +\newline +./grupo11 -c -t 1024 libro.txt libro.j \layout Itemize -Compresión con ZeroGroupping: +Compresión con \series bold -./jacu -cz libro.txt libro.z +Zero Grouping +\series default +: +\newline + +\family typewriter +./grupo11 -cz libro.txt libro.j \layout Itemize -Compresión grabando modelo de huffman: +Compresión grabando modelo de \series bold -./jacu -cs libro.txt libro.z +Huffman Canónico +\series default +: +\newline + +\family typewriter +./grupo11 -cs libro.txt libro.j \layout Itemize -Compresión con huffman canónico (carga de modelo): +Compresión con carga de \series bold -./jacu -c libro.txt libro.z -m modelfile +Huffman Canónico +\series default +: +\newline + +\family typewriter +./grupo11 -c libro.txt libro.j -m modelo.ftb +\layout Itemize + +Compresión de máxima calidad y volúmenes de 100KB: +\newline + +\family typewriter +./grupo11 -czt100 -q9 libro.txt libro.j +\layout Itemize + +Descompresión de cualquiera de los anteriores: +\newline + +\family typewriter +./grupo11 -d libro.j libro_descomprimido.txt \layout Chapter Implementación @@ -277,30 +414,434 @@ Block Sorting \layout Subsection Move to Front +\layout Standard + +La idea básica del move to front es mantener una lista que represente los + símbolos del archivo o bloque a procesar, y a su vez coloca los símbolos + mas frecuentes al frente de esta lista. +\layout Standard + +Un símbolo es codificado como el índice (ó posición) en la lista de símbolos + inicial (la cual contiene a todos los símbolos diferentes del archivo o + bloque de datos). + Al comenzar el proceso, se leen uno por uno los símbolos del archivo o + bloque original y este mismo símbolo es promovido hacia el frente de la + lista, de esta los símbolos mas frecuentes tienden a posicionarse al frente + de la lista. \layout Subsection Huffman Estático +\layout Standard + +Si bien no ahondaremos en detalles de implementación que pueden observarse + en la documentación generada por doxygen que acompaña este informe, pasamos + a presentar la interfaz a través de la cual el usuario podrá utilizar este + compresor. + Antes, es necesario comentar que el estado del compresor, se mantiene a + través de una estructura definida como +\series bold +HUFF_STATE +\series default +, en la cual se especificarán cosas tales como si el compresor actua sobre + archivos o chunks de datos, si es un huffman canonico o standard, archivo + a comprimir, archivo destino, etc. +\layout Paragraph + + +\series medium +El compresor y/o descompresor Huffman Estático, será inicializado y desinicializ +ado utilizando las rutinas: +\layout Itemize + + +\family typewriter +\noun on +HUFF_STATE *shuff_init_encoder_byfile(char *inputfile, char *outputfile, + long volsize); +\layout Itemize + + +\family typewriter +\noun on +HUFF_STATE *shuff_init_encoder_bychunk(char *outputfile, long volsize); +\layout Itemize + + +\family typewriter +\noun on +HUFF_STATE *shuff_init_decoder(char *inputfile, char *outputfile); +\layout Itemize + + +\family typewriter +\noun on +void shuff_deinit_encoder(HUFF_STATE *shuff); +\layout Itemize + + +\family typewriter +\noun on +void shuff_deinit_decoder(HUFF_STATE *shuff); +\layout Standard + +Para llevar a cabo la compresión efectiva de un archivo o chunks de datos, + se cuentan con las siguientes rutinas: +\layout Itemize + + +\family typewriter +int shuff_encode_file(HUFF_STATE *shuff); +\layout Itemize + + +\family typewriter +int shuff_decode_file(HUFF_STATE *shuff); +\layout Itemize + + +\family typewriter +int shuff_scanfreq_chunk(HUFF_STATE *shuff, char* chunk, int chunksize); +\layout Itemize + + +\family typewriter +int shuff_decode_chunk(HUFF_STATE *shuff, char *chunk, int chunksize, int + *decodedbytes); +\layout Paragraph + +Operación sobre archivos o chunks +\layout Paragraph + + +\series medium +Dado que se requería la utilización de este compresor en la etapa final + de un BS+MTF, el mismo proporciona funcionalidad para comprimir directamente + un archivo especificado, o bien para realizar la compresión de chunks de + datos, que en nuestro caso serán las salidas del Move to Front. +\layout Paragraph + +Persistencia del Modelo Estadístico de Orden 0 +\layout Paragraph + + +\series medium +A fines de poder grabar o cargar un modelo de orden-0 el cual simplemente + consiste en una tabla de frecuencias/probabilidades de los 255 symbolos + posibles en un archivo, dando lugar al Huffman Canónico que será explicado + posteriormente, se cuenta con dos funciones: +\family typewriter +shuff_save_model() +\family default +, y +\family typewriter +shuff_load_model() \layout Section -Features Especiales + \begin_inset LatexCommand \label{sec:Features-Especiales} \end_inset +Optimizaciones y Características adicionales +\layout Standard + +Como fue anticipado al inicio de este documento, nuestro compresor cuenta + con funcionalidad extra que permite en ciertos casos obtener mejores niveles + de compresión. + Pasamos a describir las mismas una por una, terminando por último con una + optimización específica para textos. +\layout Subsection + +Huffman Canónico +\layout Standard + +Dada la naturaleza del Huffman Estático que hemos implementado como el compresor + estadístico final de la cadena +\series bold +BS+MTF+Compresor +\series default +, el mismo se vale de un modelo estadístico de orden-0, el cual es obtenido + realizando una pasada inicial al archivo a comprimir, en la cual obtiene + una tabla de frecuencias/probabilidades, y la cual es utilizada para generar + el árbol de Huffman, que a su vez da origen a una tabla de códigos prefijos + que finalmente es utilizada en el compresor, para codificar los símbolos + o caracteres del archivo original. +\layout Standard + +Dicho esto, destacamos la extensión que hemos realizado a nuestro compresor + de Huffman para que pueda guardar y/o cargar un modelo estadístico de orden-0 + y el usuario pueda por ejemplo utilizar para comprimir cualquier archivo + de texto, un modelo que él crea óptimo para la compresión de dichos archivos, + en vez de generar un modelo diferente para cada archivo que comprime. +\layout Standard + +Esta capacidad de un compresor de Huffman, se la conoce como Huffman Canónico, + y se encuentra presente en nuestro compresor. + Para saber más sobre su modo de uso, dirigirse a la sección +\series bold + +\begin_inset LatexCommand \ref{sub:Execution-Flags} + +\end_inset + + +\series default +. +\layout Subsection + +Zero Grouping +\layout Standard +Este algoritmo se aplica a la salida del +\series bold +MTF +\series default + que, gracias al +\series bold +BS +\series default + que aumenta la localidad, genera estadísticamente muchas secuencias de + ceros repetidos. + Como el Huffman Estático no aprovecha esta característica (comprime igual + +\family typewriter +000001234 +\family default + que +\family typewriter +010203040 +\family default +), se buscó un método que sí la explote para optimizar el compresor y se + llegó a un algoritmo muy simple que bautizamos +\series bold +Zero Grouping +\series default +. +\layout Standard + +Cada secuencia de ceros se codifica con 2 bytes, el primero es siempre 0 + ( +\family typewriter +0x00 +\family default +) y el segundo indica la cantidad de ceros que le siguen. + En el caso de haber un byte de valor cero aislado, también se codifica + con 2 bytes ( +\family typewriter +0x00 0x00 +\family default +, que indica que viene un cero y luego de ese cero no viene ningún cero + más), expandiendo la salida, pero estos son casos aislados que estadísticamente + se ven superados por la cantidad de secuencias largas de ceros que son + comprimidas a sólo 2 bytes. + Además, la salida del +\series bold +ZG +\series default + (Zero Grouping) es comprimida con Huffman por lo que en casos extremos + la expansión no se manifiesta en forma notoria. +\layout Standard + +Como la cantidad de ceros que le siguen al primero en una secuencia es expresada + con un byte, sólo se pueden comprimir a 2 bytes secuencias de hasta 256 + ceros (el primer cero más los 0-255 siguientes). + De haber secuencias con mayor cantidad de ceros, simplemente se generan + +\family typewriter +N +\family default + +\emph on +grupos +\emph default + (siendo +\family typewriter +N +\family default + la cantidad de ceros en la secuencia dividido 256, redondeando hacia arriba) + de 2 bytes cada uno. + Por ejemplo, una secuencia de 257 ceros será expresada como +\family typewriter +0x00 0xFF 0x00 0x00 +\family default + (2 grupos) y una de 525 como +\family typewriter +0x00 0xFF 0x00 0xFF 0x00 0x0B +\family default + (3 grupos). + Nuevamente, se comprobó estadísticamente que las secuencias de ceros rara + vez superan los 50 ceros seguidos, por lo que de utilizar más de un byte + para expresar la cantidad de ceros que siguen al primero se obtendrían + peores resultados. +\layout Subsubsection* + +Ejemplo: +\layout LyX-Code + + +\size scriptsize +Salida de MTF: 0 0 0 0 0 0 1 5 3 0 0 0 0 12 0 1 0 0 0 0 0 0 0 0 0 1 1 + 4 0 0 1 0 2 +\layout LyX-Code + + +\size scriptsize +Salida de ZG: 0 5 1 5 3 0 3 12 0 0 1 0 8 1 1 + 4 0 1 1 0 0 2 +\layout LyX-Code + + +\size scriptsize + | + | +\layout LyX-Code + + +\size scriptsize + expandió + expandió +\layout Standard + +Como se puede ver, la salida del MTF es de 33 bytes, mientras que la del + +\series bold +ZG +\series default + es de 22 (incluso cuando hubieron expansiones). + Como se podrá ver en las pruebas del capítulo +\begin_inset LatexCommand \vref{cha:Benchmarks} + +\end_inset + +, en la mayoría de los casos se logra una mejora introduciendo este algoritmo, + y en casos extremos esta mejora llega obtener resultados con la mitad de + bpb (bits por byte) que la salida original del +\series bold +MTF +\series default +. +\layout Subsection + +Word-Scaping +\layout Standard + +Esta optimización se ha realizado específicamente para mejorar la compresión + de archivos de texto. + La base de esta técnica es la previa confección de un diccionario de palabras + (en nuestro caso 255 palabras máximo), a través del cual aplicando un pre-proce +samiento al archivo a comprimir, reemplazamos las palabras de ese diccionario + que se encuentren en el archivo, por un código de escape sucedido por el + índice en el diccionario de la palabra que se abrevia. +\layout Standard + +Es decir, si tenemos el siguiente diccionario de 4 palabras: +\family typewriter +padre +\family default +, +\family typewriter +él +\family default +, +\family typewriter +nos +\family default +, +\family typewriter +superman +\family default +; y poseemos el texto: +\emph on + +\begin_inset Quotes eld +\end_inset + +El +\family typewriter +padre +\family default + de +\family typewriter +superman +\family default + es el hombre araña +\begin_inset Quotes erd +\end_inset + + +\emph default +, luego del pre-procesamiento tendremos: +\emph on + +\begin_inset Quotes eld +\end_inset + +El +\family typewriter +[escape][ +\backslash +0x00] +\family default + de +\family typewriter +[escape][ +\backslash +0x03] +\family default + es el hombre araña +\begin_inset Quotes erd +\end_inset + + +\emph default +. +\layout Standard + +Para la confección de un buen diccionario, hemos desarrollado una utilidad + que contabiliza las 255 palabras que más aparecen dentro de una fuente + especificada, y luego del análisis de varios textos en castellano de toda + índole (informáticos, novelas, noticias), se obtiene el diccionario que + será entregado con el software. \layout Section -Optimización para compresión de textos +Documentación de la API +\layout Standard + +Para obtener una documentación de la API, se incluye en formato HTML en + el CD-ROM la documentación generada con Doxygen para los distintos componentes + del compresor. + Esta documentación se encuentra en el directorio +\family typewriter +doc/api/html +\family default +. \layout Chapter + +\begin_inset LatexCommand \label{cha:Benchmarks} + +\end_inset + Benchmarks \layout Section -Prueba Calgary -\layout Section +Prueba Calgary Corpus +\layout Standard -Archivos de Texto -\layout Section +El set de prueba Calgary Corpus Test es utilizado internacionalmente para + la prueba y comparación de compresores, contando con archivos diseñados + especificamente para estos fines. + Es por ello que hemos utilizado dicho set y a continuación exponemos los + resultados: +\layout Paragraph + +Bench 1) JACU vs GZIP vs BZIP2 +\layout Standard + +Se prueba el set de Calgary utilizando nuestro compresor, y enfrentandolo + al GZIP y BZIP2 en términos de tiempo utilizado para la compresion y nivel + de compresión (Bits per Byte). + Los resultados a continuación: +\layout Standard -Archivos Binarios \the_end