From f836929caa77e33c82ae1a887c1d7269c651fcd7 Mon Sep 17 00:00:00 2001 From: Alan Kennedy Date: Mon, 28 Jun 2004 00:23:28 +0000 Subject: [PATCH] =?utf8?q?Avanzo=20un=20poco=20m=C3=A1s=20del=20informe?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- doc/InformeTP3.lyx | 99 ++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 96 insertions(+), 3 deletions(-) diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx index a486f6d..28be27f 100644 --- a/doc/InformeTP3.lyx +++ b/doc/InformeTP3.lyx @@ -195,6 +195,11 @@ volsize \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 @@ -282,15 +287,103 @@ Move to Front Huffman Estático \layout Section -Features Especiales +Features y Optimizaciones \begin_inset LatexCommand \label{sec:Features-Especiales} \end_inset -\layout Section +\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 -Optimización para compresión de textos +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 -- 2.43.0