X-Git-Url: https://git.llucax.com/z.facultad/75.06/jacu.git/blobdiff_plain/226fa4a049563f9e9b8c4a6632cf65971398ecc1..515ea1a547a4ca71f1e2ddecc84e72a54cf53958:/doc/InformeTP3.lyx?ds=sidebyside diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx index 11b10a5..5c5a3c8 100644 --- a/doc/InformeTP3.lyx +++ b/doc/InformeTP3.lyx @@ -159,7 +159,7 @@ Como hemos ancitipado anteriormente, el compresor cuenta con features especiales 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 +collapsed false \layout Standard @@ -229,7 +229,7 @@ La opci -t \family default opcional que permite generar un archivo comprimido multivolumen, donde - volsize será el tamaño en kbytes de cada volúmen, excepto el último que + volsize será el tamaño en kbytes de cada volumen, excepto el último que podrá ser menor. \layout Subsection @@ -241,8 +241,8 @@ La opci 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 +Además de los flags estándar que hemos visto recién, nuestro compresor cuenta + con otra serie de ellos para la utilización de los características 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: @@ -253,7 +253,7 @@ Ademas de los flags standards que hemos visto reci \family typewriter -c \family default - Indica que se desea comprimir un archivo (mutualmente exclusivo con + Indica que se desea comprimir un archivo (mutuamente exclusivo con \family typewriter -d \family default @@ -265,8 +265,7 @@ Ademas de los flags standards que hemos visto reci \family typewriter -d \family default - Indica que se desea descomprimir un archivo (mutualmente exclusivo con - + Indica que se desea descomprimir un archivo (mutuamente exclusivo con \family typewriter -c \family default @@ -298,6 +297,19 @@ Zero Grouping \labelwidthstring 00.00.0000 +\family typewriter +-r +\family default + Puede ser utilizado únicamente en una compresión y activa el característica + de +\series bold +Word Scaping +\series default +, que realizar un reemplazo de palabras frecuentes antes del BlockSorting. +\layout List +\labelwidthstring 00.00.0000 + + \family typewriter -s \family default @@ -415,7 +427,7 @@ Block Sorting La técnica de Block Sorting \begin_inset Foot -collapsed true +collapsed false \layout Standard @@ -429,7 +441,7 @@ desde ahora lo llamaremos BS, para minimizar la notaci En una implementación simple, el BS debe crear una matriz y crear todos los desplazamientos sobre ella. - Esto hace que se necesito + Esto hace que se necesite \begin_inset Formula $O(n^{2})$ \end_inset @@ -444,10 +456,10 @@ En una implementaci El otro problema es el tiempo de ordenamiento de los desplazamientos, que debe ser lo menor posible. - Una posibiliad es utilizar un método de ordenamiento de bajo órden, como + Una posibilidad es utilizar un método de ordenamiento de bajo orden, como el Quick Sort \begin_inset Foot -collapsed true +collapsed false \layout Standard @@ -592,7 +604,7 @@ Luego de inicializar el vector Desplazamiento (esta parte es \begin_inset Foot -collapsed true +collapsed false \layout Standard @@ -650,8 +662,7 @@ abcd \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 +Salida: 00001011001000200020101000300010004 \layout Standard Un símbolo es codificado como el índice (ó posición) en la lista de símbolos @@ -688,8 +699,8 @@ Si bien no ahondaremos en detalles de implementaci \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 +, en la cual se especificarán cosas tales como si el compresor actúa sobre + archivos o chunks de datos, si es un huffman canónico o estándar, archivo a comprimir, archivo destino, etc. \layout Paragraph @@ -772,7 +783,7 @@ Persistencia del Modelo Estad \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 + consiste en una tabla de frecuencias/probabilidades de los 255 símbolos posibles en un archivo, dando lugar al Huffman Canónico que será explicado posteriormente, se cuenta con dos funciones: \family typewriter @@ -781,6 +792,44 @@ shuff_save_model() , y \family typewriter shuff_load_model() +\layout Subsection + +Virtual File +\layout Standard + +Uno de los problemas que teníamos al principio era que las tareas estaban + mezcladas, entonces donde se estaba comprimiendo, se estaba guardando también + en un archivo y manejando la lógica de hacer los splits de los archivos. +\layout Standard + +Obviamente como eso resultaba muy molesto planteamos un modelo más abstracto + al que llamamos Virtual File, que es una API escrita sobre la API ANSI-C + de Input/Output que maneja de manera transparente este tema. +\layout Standard + +Utilizar la API esta tan simple como agregar una +\begin_inset Quotes eld +\end_inset + +v +\begin_inset Quotes erd +\end_inset + + delante de las funciones fopen, fclose, fread, etc y reemplazar la estructura + FILE por VFILE. +\layout Standard + +Cuando se abre un archivo para escritura a medida que se van escribiendo + bytes se va incrementando un contador. + Si el contador llega al limite pedido, se cierra el archivo actual, se + abre el siguiente y se sigue escribiendo en éste, de manera totalmente + transparente para el usuario/programador. +\layout Standard + +La lectura es similar. + Cada vez que se llega al EOF de un archivo, si éste no es el último volumen, + se cierra el archivo actual y se abre el siguiente hasta llegar al EOF + del último volumen. \layout Section @@ -1074,20 +1123,11 @@ Benchmarks 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 se dan a continuación, para dos configuraciones de PC distintas: +El conjunto de prueba Calgary Corpus Test es utilizado internacionalmente + para la prueba y comparación de compresores, contando con archivos diseñados + específicamente para estos fines. + Es por ello que hemos utilizado dicho conjunto y a continuación exponemos + los resultados: \layout Standard @@ -2476,7 +2516,7 @@ Comparaci \align center \begin_inset Tabular - + @@ -2486,6 +2526,8 @@ Comparaci + + \begin_inset Text @@ -2553,6 +2595,22 @@ Filename 32K WS \end_inset + +\begin_inset Text + +\layout Standard + +128K +\end_inset + + +\begin_inset Text + +\layout Standard + +128K ZG +\end_inset + @@ -2628,6 +2686,22 @@ bib 2.8483 \end_inset + +\begin_inset Text + +\layout Standard + +2.4574 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.1822 +\end_inset + @@ -2694,6 +2768,22 @@ book1 3.3399 \end_inset + +\begin_inset Text + +\layout Standard + +3.0509 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.9647 +\end_inset + @@ -2769,6 +2859,22 @@ book2 2.9248 \end_inset + +\begin_inset Text + +\layout Standard + +2.6511 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.5122 +\end_inset + @@ -2835,6 +2941,22 @@ geo 5.7076 \end_inset + +\begin_inset Text + +\layout Standard + +5.5323 +\end_inset + + +\begin_inset Text + +\layout Standard + +5.0823 +\end_inset + @@ -2901,6 +3023,22 @@ news 3.3910 \end_inset + +\begin_inset Text + +\layout Standard + +3.0845 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0120 +\end_inset + @@ -2967,6 +3105,22 @@ obj1 4.7757 \end_inset + +\begin_inset Text + +\layout Standard + +4.7638 +\end_inset + + +\begin_inset Text + +\layout Standard + +4.5078 +\end_inset + @@ -3033,6 +3187,22 @@ obj2 3.1025 \end_inset + +\begin_inset Text + +\layout Standard + +2.9758 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7462 +\end_inset + @@ -3099,6 +3269,22 @@ paper1 3.0785 \end_inset + +\begin_inset Text + +\layout Standard + +2.8913 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7998 +\end_inset + @@ -3165,6 +3351,22 @@ paper2 3.1110 \end_inset + +\begin_inset Text + +\layout Standard + +2.8342 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7034 +\end_inset + @@ -3231,6 +3433,22 @@ paper3 3.3091 \end_inset + +\begin_inset Text + +\layout Standard + +3.1365 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0760 +\end_inset + @@ -3297,6 +3515,22 @@ paper4 3.9025 \end_inset + +\begin_inset Text + +\layout Standard + +3.8928 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.9073 +\end_inset + @@ -3372,6 +3606,22 @@ paper5 4.0616 \end_inset + +\begin_inset Text + +\layout Standard + +4.0455 +\end_inset + + +\begin_inset Text + +\layout Standard + +4.0723 +\end_inset + @@ -3447,6 +3697,22 @@ paper6 3.0537 \end_inset + +\begin_inset Text + +\layout Standard + +3.0008 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.9546 +\end_inset + @@ -3495,6 +3761,7 @@ progc \layout Standard +3.2187 \end_inset @@ -3521,6 +3788,22 @@ progc 3.0749 \end_inset + +\begin_inset Text + +\layout Standard + +2.9618 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.8826 +\end_inset + @@ -3569,6 +3852,7 @@ progl \layout Standard +2.2816 \end_inset @@ -3595,9 +3879,34 @@ progl 2.3124 \end_inset - - - + +\begin_inset Text + +\layout Standard + +2.2016 +\end_inset + + +\begin_inset Text + +\layout Standard + + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +1.9899 +\end_inset + + + + \begin_inset Text \layout Standard @@ -3634,6 +3943,7 @@ progp \layout Standard +2.3066 \end_inset @@ -3660,6 +3970,31 @@ progp 2.3409 \end_inset + +\begin_inset Text + +\layout Standard + + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +2.2359 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.0279 +\end_inset + @@ -3699,6 +4034,7 @@ trans \layout Standard +2.4646 \end_inset @@ -3725,6 +4061,22 @@ trans 2.3410 \end_inset + +\begin_inset Text + +\layout Standard + +1.9957 +\end_inset + + +\begin_inset Text + +\layout Standard + +1.7303 +\end_inset + @@ -3764,6 +4116,7 @@ pic \layout Standard +0.8794 \end_inset @@ -3790,6 +4143,22 @@ pic 1.6069 \end_inset + +\begin_inset Text + +\layout Standard + +1.5960 +\end_inset + + +\begin_inset Text + +\layout Standard + +0.8671 +\end_inset + @@ -3816,7 +4185,7 @@ Comparaci \align center \begin_inset Tabular - + @@ -3826,6 +4195,8 @@ Comparaci + + \begin_inset Text @@ -3893,6 +4264,22 @@ Filename 32K WS \end_inset + +\begin_inset Text + +\layout Standard + +128K +\end_inset + + +\begin_inset Text + +\layout Standard + +128K ZG +\end_inset + @@ -3973,6 +4360,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +1.095 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.790 +\size footnotesize +s +\end_inset + @@ -4069,6 +4476,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +8.613 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +4.758 +\size footnotesize +s +\end_inset + @@ -4149,6 +4576,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +5.787 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +4.052 +\size footnotesize +s +\end_inset + @@ -4245,6 +4692,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.902 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.690 +\size footnotesize +s +\end_inset + @@ -4341,6 +4808,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +3.378 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +2.520 +\size footnotesize +s +\end_inset + @@ -4421,6 +4908,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.682 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.602 +\size footnotesize +s +\end_inset + @@ -4501,6 +5008,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +2.631 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +1.891 +\size footnotesize +s +\end_inset + @@ -4581,6 +5108,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.497 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.296 +\size footnotesize +s +\end_inset + @@ -4661,6 +5208,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.706 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.498 +\size footnotesize +s +\end_inset + @@ -4757,6 +5324,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.373 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.266 +\size footnotesize +s +\end_inset + @@ -4837,6 +5424,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.117 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.080 +\size footnotesize +s +\end_inset + @@ -4917,6 +5524,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.173 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.075 +\size footnotesize +s +\end_inset + @@ -4997,6 +5624,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.333 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.225 +\size footnotesize +s +\end_inset + @@ -5048,7 +5695,7 @@ s \layout Standard -0.272 +0.292 \size footnotesize s \end_inset @@ -5058,6 +5705,9 @@ s \layout Standard +0.313 +\size footnotesize +s \end_inset @@ -5090,6 +5740,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.262 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.234 +\size footnotesize +s +\end_inset + @@ -5125,7 +5795,7 @@ s \layout Standard -0.485 +0.585 \size footnotesize s \end_inset @@ -5135,6 +5805,25 @@ s \layout Standard + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +0.666 +\family default +\series default +\shape default +\size footnotesize +\emph default +\bar default +\noun default +\color default +s \end_inset @@ -5183,6 +5872,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.640 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.640 +\size footnotesize +s +\end_inset + @@ -5218,7 +5927,7 @@ s \layout Standard -0.310 +0.510 \size footnotesize s \end_inset @@ -5228,6 +5937,9 @@ s \layout Standard +0.598 +\size footnotesize +s \end_inset @@ -5260,6 +5972,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +0.546 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +0.544 +\size footnotesize +s +\end_inset + @@ -5295,7 +6027,7 @@ s \layout Standard -0.632 +0.832 \size footnotesize s \end_inset @@ -5305,6 +6037,9 @@ s \layout Standard +0.926 +\size footnotesize +s \end_inset @@ -5337,6 +6072,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +1.109 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +1.094 +\size footnotesize +s +\end_inset + @@ -5372,7 +6127,7 @@ s \layout Standard -323 +551 \size footnotesize s \end_inset @@ -5382,6 +6137,9 @@ s \layout Standard +572 +\size footnotesize +s \end_inset @@ -5414,6 +6172,26 @@ s s \end_inset + +\begin_inset Text + +\layout Standard + +784 +\size footnotesize +s +\end_inset + + +\begin_inset Text + +\layout Standard + +739 +\size footnotesize +s +\end_inset +