Agrego el Mitico y Enigmatico Word Scaping al block sorting. Para usarlo usar parame...

[z.facultad/75.06/jacu.git] / doc / InformeTP3.lyx

#LyX 1.3 created this file. For more info see http://www.lyx.org/
\lyxformat 221
\textclass book
\language spanish
\inputencoding auto
\fontscheme palatino
\graphics default
\paperfontsize default
\spacing single 
\papersize a4paper
\paperpackage widemarginsa4
\use_geometry 0
\use_amsmath 0
\use_natbib 0
\use_numerical_citations 0
\paperorientation portrait
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\defskip medskip
\quotes_language english
\quotes_times 2
\papercolumns 1
\papersides 1
\paperpagestyle default

\layout Title

Organización de Datos (75.06)
\newline 
Trabajo Práctico 3
\newline 
JACU
\layout Author


\series bold 
Grupo 11
\series default 

\newline 
Nicolás Dimov (77624)
\newline 
Alan Kennedy (78907)
\newline 
Leandro Lucarella (77891)
\newline 
Ricardo Markiewicz (78226)
\layout Date

Primera Entrega, 28 de Junio del 2004
\layout Standard


\begin_inset LatexCommand \tableofcontents{}

\end_inset 


\layout Chapter

Introducción
\layout Section

Método de compresión utilizado
\layout Standard

Dada la asignación de confeccionar un compresor de archivos de cualquier
 índole, con alguna optimización particular para archivos de texto, hemos
 optado por la implementación del esquema: 
\series bold 
Block Sorting + Move to front + Huffman Estático.
 
\layout Standard

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 característ
icas especiales que se verán detallados en la 
\series bold 
sección 
\begin_inset LatexCommand \ref{sec:Features-Especiales}

\end_inset 


\series default 
.
 Dichas características se resumen a:
\layout Itemize

Persistencia del Modelo Orden-0 de 
\series bold 
Huffman Estático
\series default 
 (
\series bold 
Huffman Canónico
\series default 
)
\layout Itemize


\series bold 
Zero Grouping
\series default 
 (Agrupación de Ceros, aplicado a la salida del 
\series bold 
MTF
\series default 
)
\layout Itemize


\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 el modo de uso.
\layout Subsection

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 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 como se pidió en el enunciado
\begin_inset Foot
collapsed true

\layout Standard

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 
./grupo11 -c [-t volsize] sourcefile targetfile
\layout Standard


\series medium 
Siendo 
\family typewriter 
sourcefile
\family default 
 el nombre del archivo a comprimir y 
\family typewriter 
targetfile
\family default 
 el nombre del archivo comprimido.
\layout Paragraph*

Descompresión:
\layout Standard


\family typewriter 
\series medium 
./grupo11 -d sourcefile targetfile
\layout Standard


\series medium 
Siendo 
\family typewriter 
sourcefile
\family default 
 el nombre del archivo a descomprimir y 
\family typewriter 
targetfile
\family default 
 el nombre del archivo descomprimido.
\layout Paragraph*

Nota:
\layout Standard

La opción 
\family typewriter 
-t
\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


\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
 cuenta con otra serie de ellos para la utilización de los features especiales
 que veremos más adelante.
 A fines de documentar la totalidad de los flags de ejecución, detallamos
 los anteriores y los adicionales a continuación:
\layout List
\labelwidthstring 00.00.0000


\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


\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


\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


\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


\family typewriter 
-s
\family default 
 Puede ser utilizado únicamente en una compresión y graba el modelo de orden-0
 de 
\series bold 
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


\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 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 diferentes
 opciones:
\layout Itemize

Compresión multivolumen (de 1024KB, cada uno):
\family typewriter 

\newline 
./grupo11 -c -t 1024 libro.txt libro.j
\layout Itemize

Compresión con 
\series bold 
Zero Grouping
\series default 
: 
\newline 

\family typewriter 
./grupo11 -cz libro.txt libro.j
\layout Itemize

Compresión grabando modelo de 
\series bold 
Huffman Canónico
\series default 
: 
\newline 

\family typewriter 
./grupo11 -cs libro.txt libro.j
\layout Itemize

Compresión con carga de 
\series bold 
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 Section

Especificaciones
\layout Subsection

Block Sorting
\layout Subsection

Move to Front
\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


\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

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 Corpus
\layout Standard

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

\the_end