X-Git-Url: https://git.llucax.com/z.facultad/75.06/jacu.git/blobdiff_plain/5aecfd5dac0f0f1b38e38ac4b39df5c232ca959e..4398b0b79b3ead867b309b4bd492dd4ed980b9f9:/doc/InformeTP3.lyx diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx index f7f5d1d..b5ec748 100644 --- a/doc/InformeTP3.lyx +++ b/doc/InformeTP3.lyx @@ -228,9 +228,9 @@ La opci \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. + opcional 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 @@ -413,7 +413,63 @@ Especificaciones Block Sorting \layout Subsection -Move to Front +Move to Front (MTF) +\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 + +Ejemplo: +\layout LyX-Code + +Entrada: +\begin_inset Quotes eld +\end_inset + +aaaabbabbbaaaaaccccbbccbbbbdddddbbbb +\begin_inset Quotes erd +\end_inset + + +\layout LyX-Code + +Lista de símbolos: +\begin_inset Quotes eld +\end_inset + +abcd +\begin_inset Quotes erd +\end_inset + + +\layout LyX-Code + +Salida: 0 0 0 0 1 0 1 1 0 0 1 0 0 0 2 0 0 0 2 0 1 0 1 0 0 0 3 0 0 0 1 0 + 0 0 4 +\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 Standard + +Como este esquema es aplicado luego de ser procesado por el +\emph on +block sorting +\emph default + tenemos la seguridad que existirá una fuerte localidad de símbolos en el + bloque de datos recibido, esto provocará que la salida del +\emph on +move to front +\emph default +posea una gran cantidad de cadenas de ceros consecutivos, que luego pueden + ser codificados nuevamente, lo que favorece la compresión final. \layout Subsection Huffman Estático @@ -428,7 +484,7 @@ Si bien no ahondaremos en detalles de implementaci \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 @@ -441,33 +497,86 @@ ado utilizando las rutinas: \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 @@ -646,7 +755,7 @@ ZG \end_inset -, en la mayoría de los casos se logra una mejora introduciendo este algoritmos, +, 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 @@ -758,11 +867,1377 @@ doc/api/html Benchmarks \layout Section -Prueba Calgary -\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: + +\begin_inset Float table +placement H +wide false +collapsed false + +\layout Caption + +Comparación de compresores JACU, GZIP y BZIP2 con Test de Calgary Corpus +\layout Standard +\align center + +\begin_inset Tabular + + + + + + + + + + + +\begin_inset Text + +\layout Standard + + +\series bold +Filename +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +JACU (c) +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +GZIP (c) +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +BZIP2 (c) +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +JACU (t) +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +GZIP (t) +\end_inset + + +\begin_inset Text + +\layout Standard + + +\series bold +BZIP2 (t) +\end_inset + + + + +\begin_inset Text + +\layout Standard + +bib +\end_inset + + +\begin_inset Text + +\layout Standard + +2.8618 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.5211 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +1.975 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.834 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.052 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.079 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +book1 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.3535 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.4531 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.420 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +5.330 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.205 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.508 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +book2 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.9374 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7068 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.062 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +4.435 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.140 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.387 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +geo +\end_inset + + +\begin_inset Text + +\layout Standard + +5.7057 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +5.3510 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +4.447 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.809 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.066 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.082 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +news +\end_inset + + +\begin_inset Text + +\layout Standard + +3.3889 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0726 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.516 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +3.961 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.080 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.228 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +obj1 +\end_inset + + +\begin_inset Text + +\layout Standard + +4.7653 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +3.8404 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +4.013 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.668 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.004 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.046 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +obj2 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0978 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.6459 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.478 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.172 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.060 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.143 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +paper1 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0767 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7955 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.492 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.422 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.010 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.030 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +paper2 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0966 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.8957 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.437 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.629 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.015 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.062 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +paper3 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.3064 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +3.1117 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.723 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.364 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.040 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.047 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +paper4 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.8952 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +3.3334 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +3.124 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.116 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.003 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.038 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +paper5 +\end_inset + + +\begin_inset Text + +\layout Standard + +4.0455 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +3.3428 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +3.237 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.102 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.003 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.048 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +paper6 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.1024 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7780 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.581 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.298 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.006 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.070 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +progc +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0749 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.6810 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +2.533 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.321 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.006 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.069 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +progl +\end_inset + + +\begin_inset Text + +\layout Standard + +2.3097 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +1.8170 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +1.740 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.899 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.010 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.054 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +progp +\end_inset + + +\begin_inset Text + +\layout Standard + +2.3435 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +1.8219 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +1.735 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.628 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.006 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.048 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +trans +\end_inset + + +\begin_inset Text + +\layout Standard + +2.3263 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +16210 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +1.528 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +1.042 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.010 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.053 +\size footnotesize +s +\end_inset + + + + +\begin_inset Text + +\layout Standard + +pic +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +0.8798 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +0.776 +\size footnotesize +bpb +\end_inset + + +\begin_inset Text + +\layout Standard + +\end_inset + + +\begin_inset Text + +\layout Standard + +0.090 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.093 +\size footnotesize +s +\end_inset + + + + +\end_inset + + +\end_inset -Archivos de Texto -\layout Section -Archivos Binarios \the_end