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
\series bold
HUFF_STATE
\series default
-, en la cual se especificara cosas tales como si el compresor actua sobre
+, 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
\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
-Las restantes rutinas que son utilizadas para efectuar la compresión o compresió
-n concreta, se detallan en la documentación extendida en doxygen, no obstante
- vamos a detallar la mínima interfaz para poder operar con el compresor:
+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 y Optimizaciones
+
\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 ratios
+ 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 Standard
Dada la naturaleza del Huffman Estático que hemos implementado como el compresor
- estadístico final de la cadena BS+MTF+Compresor, 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/pro
-babilidades, y la cual es utilizada para generar el árbol de huffman, que
- a su vez da órigen a una tabla de códigos prefijos que finalmente es utilizada
- en el compresor, para encodear los símbolos o caractéres del archivo original.
+ 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
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
+ Para saber más sobre su modo de uso, dirigirse a la sección
\series bold
-sección
+
\begin_inset LatexCommand \ref{sub:Execution-Flags}
\end_inset
.
\layout Subsection
-Zero Groupping
+Zero Grouping
\layout Standard
-Siendo el producto del BlockSorting + Move to front, secuencias de valores
- de 0 a 255, en donde gracias al Block Sorting que aumenta la localidad
- de los bloques de datos del archivo original que se van procesando, se
- tendrá una gran aparición de 0 (ceros) en la salida del Move to front.
+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
-Aprovechando este factor, hemos implementando este método de Zero Groupping,
- en donde abreviaremos las series de ceros que se presenten en forma consecutiva
- en la salida de un MTF, por un byte con valor hexa 00, y un factor de repetició
-n a continuación del byte anterior (el mayor valor de repetición sera 255
- para poder albergarlo en un byte).
- De poseer una secuencia de ceros superior en longitud a 255, se abreviarán
- esos 255, y luego se continuará con una nueva abreviación de los restantes.
+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
-En base a las pruebas realizadas, en la mayoría de los casos tanto en archivos
- de texto como en binarios, se observa una leve mejora en los niveles de
- compresión (bpb), utilizando esta opción en la invocación del compresor.
+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 Escaping
+Word-Scaping
\layout Standard
-Esta optimización se ha realizado especificamente para mejorar la compresión
+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
- indice en el diccionario de la palabra que se abrevia.
+ índice en el diccionario de la palabra que se abrevia.
\layout Standard
-Es decir, si tenemos el siguiente diccionario de 4 palabras: ¨padre¨, ¨él¨,
- ¨nos¨, ¨superman¨, y poseemos el texto: ¨El padre de superman es el hombre
- araña¨, luego del preprocesamiento tendremos: ¨El [escape char][
+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] de [escapechar] [
+0x00]
+\family default
+ de
+\family typewriter
+[escape][
\backslash
-0x03] es el hombre araña¨.
+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 desarollado una utilidad
+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
+
+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