Organización de Datos (75.06)
\newline
-Trabajo Práctico
+Trabajo Práctico 3
\newline
JACU
\layout Author
\layout Chapter
-Introducción al compresor
+Introducción
\layout Section
Método de compresión utilizado
\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}
\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
\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
\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
projects / z.facultad / 75.06 / jacu.git / blobdiff