Avanzo un poco más del informe

[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
\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 al compresor
\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 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.
\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 
\series bold 
sección 
\begin_inset LatexCommand \ref{sec:Features-Especiales}

\end_inset 


\series default 
, los cuales a saberse son:
\layout Itemize

Persistencia del Modelo Orden-0 de Huffman (AKA: Huffman Canónico)
\layout Itemize

ZeroGroupping (Abreviación de ceros a la salida del MTF)
\layout Itemize

Word-Scaping (Optimización para textos detallada posteriormente)
\layout Section

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 
.
\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.
\layout Subsection

Invocación standard
\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.
 Antes de pasar a su descripción, notamos la invocación general para comprimir
 y descomprimir un archivo.
\layout Paragraph


\series medium 
Sea 
\series default 
jacu
\series medium 
 el archivo ejecutable correspondiente al compresor, tendremos la siguientes
 formas básicas de invocación:
\layout Paragraph

Compresión: 
\series medium 
./jacu -c [-t volsize] sourcefile targetfile
\newline 
Siendo 
\noun on 
sourcefile
\noun default 
 el nombre del archivo a comprimir y 
\noun on 
targetfile
\noun default 
 el nombre del archivo comprimido.
\layout Paragraph

Descompresión: 
\series medium 
./jacu -d sourcefile targetfile
\newline 
Siendo 
\noun on 
sourcefile
\noun default 
 el nombre del archivo a descomprimir y 
\noun on 
targetfile
\noun default 
 el nombre del archivo descomprimido.
\layout Quote


\series bold 
Nota:
\series default 
 El flag 
\series bold 
-t
\series default 
 es un flag opcional que permite generar un archivo comprimido multivolumen,
 donde 
\series bold 
volsize
\series default 
 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 


\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

-c Indica que se desea comprimir un archivo
\layout List
\labelwidthstring 00.00.0000

-d Indica que se desea descomprimir un archivo
\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
 los volúmenes.
\layout List
\labelwidthstring 00.00.0000

-z Puede ser utilizado unicamente en una compresión y activa el feature
 de ZeroGroupping
\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 .
\series bold 
ftb
\series 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.
 Deberá ser sucedido por el nombre del archivo que posee el modelo.
\layout Subsection

Ejemplos
\layout Standard

Damos a continuación unos breves ejemplos de invocación utilizando los flags
 opcionales:
\layout Itemize

Compresión multivolumen (de 1024 kbytes each): 
\series bold 
./jacu -c -t 1024 libro.txt libro.z
\layout Itemize

Compresión con ZeroGroupping: 
\series bold 
./jacu -cz libro.txt libro.z
\layout Itemize

Compresión grabando modelo de huffman: 
\series bold 
./jacu -cs libro.txt libro.z
\layout Itemize

Compresión con huffman canónico (carga de modelo): 
\series bold 
./jacu -c libro.txt libro.z -m modelfile
\layout Chapter

Implementación
\layout Section

Especificaciones
\layout Subsection

Block Sorting
\layout Subsection

Move to Front
\layout Subsection

Huffman Estático
\layout Section

Features y Optimizaciones
\begin_inset LatexCommand \label{sec:Features-Especiales}

\end_inset 


\layout Standard

Como fue anticipado al inicio de este documento, nuestro compresor cuenta
 con funcionalidad extra que permite en ciertos casos obtener mejores ratios
 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 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.
\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 
\series bold 
sección 
\begin_inset LatexCommand \ref{sub:Execution-Flags}

\end_inset 


\series default 
.
\layout Subsection

Zero Groupping
\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.
\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.
\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 esa opción en la invocación del compresor.
\layout Subsection

Word Escaping
\layout Standard

Esta optimización se ha realizado especificamente 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.
\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][
\backslash 
0x00] de [escapechar] [
\backslash 
0x03] es el hombre araña¨.
\layout Standard

Para la confección de un buen diccionario, hemos desarollado 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 Chapter

Benchmarks
\layout Section

Prueba Calgary
\layout Section

Archivos de Texto
\layout Section

Archivos Binarios
\the_end