X-Git-Url: https://git.llucax.com/z.facultad/75.06/jacu.git/blobdiff_plain/66f873a3de4adb65bbad6fb09cd57272216d332f..a678220ecfa90dcc47b66fa4003c834a84b02717:/doc/InformeTP3.lyx diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx index 2978894..7996145 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 @@ -415,7 +414,7 @@ Block Sorting La técnica de Block Sorting \begin_inset Foot -collapsed true +collapsed false \layout Standard @@ -429,18 +428,25 @@ 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 O(n^2) en memoria, donde n es la longitud del - vector sobre el cual se quiere operar. + Esto hace que se necesite +\begin_inset Formula $O(n^{2})$ +\end_inset + + en memoria, donde +\begin_inset Formula $n$ +\end_inset + + es la longitud del vector sobre el cual se quiere operar. Claramente es un problema, ya que para una página pequeña, digamos 1kb, se necesita una matriz de 1Mb. \layout Standard 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 @@ -455,47 +461,85 @@ Se ha optado por utilizar el qsort de la libc por ser ANSI-C y tener una \layout Standard Como última opción se estudió el Radix Sort, ya que justamente nuestro dato - a ordenar es de longitud fija n y se cuenta con un conjunto de L=255 elementos - posibles a aparecer en el dato. - El orden de éste método sería O(n*L), pero para que realmente el Radix - Sort sea efectivo, se requiere que L < log2(n) = 15, por lo que no convenía - tampoco. + a ordenar es de longitud fija +\begin_inset Formula $n$ +\end_inset + + y se cuenta con un conjunto de +\begin_inset Formula $L=255$ +\end_inset + + elementos posibles a aparecer en el dato. + El orden de éste método sería +\begin_inset Formula $O(n*L)$ +\end_inset + +, pero para que realmente el Radix Sort sea efectivo, se requiere que +\begin_inset Formula $255=L + @@ -2418,6 +2513,8 @@ Comparaci + + \begin_inset Text @@ -2485,6 +2582,22 @@ Filename 32K WS \end_inset + +\begin_inset Text + +\layout Standard + +128K +\end_inset + + +\begin_inset Text + +\layout Standard + +128K ZG +\end_inset + @@ -2516,6 +2629,7 @@ bib \layout Standard +3.1014 \end_inset @@ -2523,6 +2637,7 @@ bib \layout Standard +2.9700 \end_inset @@ -2558,6 +2673,22 @@ bib 2.8483 \end_inset + +\begin_inset Text + +\layout Standard + +2.4574 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.1822 +\end_inset + @@ -2589,6 +2720,7 @@ book1 \layout Standard +3.5561 \end_inset @@ -2596,6 +2728,7 @@ book1 \layout Standard +3.5369 \end_inset @@ -2622,6 +2755,22 @@ book1 3.3399 \end_inset + +\begin_inset Text + +\layout Standard + +3.0509 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.9647 +\end_inset + @@ -2662,6 +2811,7 @@ book2 \layout Standard +3.1380 \end_inset @@ -2669,6 +2819,7 @@ book2 \layout Standard +3.1313 \end_inset @@ -2695,6 +2846,22 @@ book2 2.9248 \end_inset + +\begin_inset Text + +\layout Standard + +2.6511 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.5122 +\end_inset + @@ -2726,6 +2893,7 @@ geo \layout Standard +5.8138 \end_inset @@ -2733,6 +2901,7 @@ geo \layout Standard +5.3860 \end_inset @@ -2759,6 +2928,22 @@ geo 5.7076 \end_inset + +\begin_inset Text + +\layout Standard + +5.5323 +\end_inset + + +\begin_inset Text + +\layout Standard + +5.0823 +\end_inset + @@ -2790,6 +2975,7 @@ news \layout Standard +3.5726 \end_inset @@ -2797,6 +2983,7 @@ news \layout Standard +3.5956 \end_inset @@ -2823,6 +3010,22 @@ news 3.3910 \end_inset + +\begin_inset Text + +\layout Standard + +3.0845 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0120 +\end_inset + @@ -2854,6 +3057,7 @@ obj1 \layout Standard +4.8441 \end_inset @@ -2861,6 +3065,7 @@ obj1 \layout Standard +4.5852 \end_inset @@ -2887,6 +3092,22 @@ obj1 4.7757 \end_inset + +\begin_inset Text + +\layout Standard + +4.7638 +\end_inset + + +\begin_inset Text + +\layout Standard + +4.5078 +\end_inset + @@ -2918,6 +3139,7 @@ obj2 \layout Standard +3.2264 \end_inset @@ -2925,6 +3147,7 @@ obj2 \layout Standard +3.0528 \end_inset @@ -2951,6 +3174,22 @@ obj2 3.1025 \end_inset + +\begin_inset Text + +\layout Standard + +2.9758 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7462 +\end_inset + @@ -2982,6 +3221,7 @@ paper1 \layout Standard +3.2693 \end_inset @@ -2989,6 +3229,7 @@ paper1 \layout Standard +3.2687 \end_inset @@ -3015,6 +3256,22 @@ paper1 3.0785 \end_inset + +\begin_inset Text + +\layout Standard + +2.8913 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7998 +\end_inset + @@ -3046,6 +3303,7 @@ paper2 \layout Standard +3.2811 \end_inset @@ -3053,6 +3311,7 @@ paper2 \layout Standard +3.2383 \end_inset @@ -3079,6 +3338,22 @@ paper2 3.1110 \end_inset + +\begin_inset Text + +\layout Standard + +2.8342 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.7034 +\end_inset + @@ -3110,6 +3385,7 @@ paper3 \layout Standard +3.4577 \end_inset @@ -3117,6 +3393,7 @@ paper3 \layout Standard +3.4632 \end_inset @@ -3143,6 +3420,22 @@ paper3 3.3091 \end_inset + +\begin_inset Text + +\layout Standard + +3.1365 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.0760 +\end_inset + @@ -3174,6 +3467,7 @@ paper4 \layout Standard +3.8928 \end_inset @@ -3181,6 +3475,7 @@ paper4 \layout Standard +3.9073 \end_inset @@ -3207,6 +3502,22 @@ paper4 3.9025 \end_inset + +\begin_inset Text + +\layout Standard + +3.8928 +\end_inset + + +\begin_inset Text + +\layout Standard + +3.9073 +\end_inset + @@ -3238,6 +3549,16 @@ paper5 \layout Standard + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +4.0455 \end_inset @@ -3245,6 +3566,7 @@ paper5 \layout Standard +4.0723 \end_inset @@ -3271,17 +3593,33 @@ paper5 4.0616 \end_inset - - - + \begin_inset Text \layout Standard -paper6 +4.0455 \end_inset - + +\begin_inset Text + +\layout Standard + +4.0723 +\end_inset + + + + +\begin_inset Text + +\layout Standard + +paper6 +\end_inset + + \begin_inset Text \layout Standard @@ -3302,6 +3640,16 @@ paper6 \layout Standard + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +3.3148 \end_inset @@ -3309,6 +3657,7 @@ paper6 \layout Standard +3.3241 \end_inset @@ -3335,6 +3684,22 @@ paper6 3.0537 \end_inset + +\begin_inset Text + +\layout Standard + +3.0008 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.9546 +\end_inset + @@ -3375,6 +3740,7 @@ progc \layout Standard +3.2316 \end_inset @@ -3382,6 +3748,7 @@ progc \layout Standard +3.2187 \end_inset @@ -3397,6 +3764,7 @@ progc \layout Standard +3.0289 \end_inset @@ -3407,6 +3775,22 @@ progc 3.0749 \end_inset + +\begin_inset Text + +\layout Standard + +2.9618 +\end_inset + + +\begin_inset Text + +\layout Standard + +2.8826 +\end_inset + @@ -3447,6 +3831,7 @@ progl \layout Standard +2.4080 \end_inset @@ -3454,6 +3839,7 @@ progl \layout Standard +2.2816 \end_inset @@ -3469,6 +3855,7 @@ progl \layout Standard +2.1395 \end_inset @@ -3479,6 +3866,31 @@ 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 + @@ -3510,6 +3922,7 @@ progp \layout Standard +2.4303 \end_inset @@ -3517,6 +3930,7 @@ progp \layout Standard +2.3066 \end_inset @@ -3532,6 +3946,7 @@ progp \layout Standard +2.1912 \end_inset @@ -3542,6 +3957,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 + @@ -3573,6 +4013,7 @@ trans \layout Standard +2.5698 \end_inset @@ -3580,6 +4021,7 @@ trans \layout Standard +2.4646 \end_inset @@ -3595,6 +4037,7 @@ trans \layout Standard +2.1422 \end_inset @@ -3605,6 +4048,22 @@ trans 2.3410 \end_inset + +\begin_inset Text + +\layout Standard + +1.9957 +\end_inset + + +\begin_inset Text + +\layout Standard + +1.7303 +\end_inset + @@ -3636,6 +4095,7 @@ pic \layout Standard +1.0351 \end_inset @@ -3643,6 +4103,7 @@ pic \layout Standard +0.8794 \end_inset @@ -3658,6 +4119,7 @@ pic \layout Standard +0.8697 \end_inset @@ -3668,6 +4130,22 @@ pic 1.6069 \end_inset + +\begin_inset Text + +\layout Standard + +1.5960 +\end_inset + + +\begin_inset Text + +\layout Standard + +0.8671 +\end_inset + @@ -3688,12 +4166,13 @@ collapsed false \layout Caption Comparación de tiempo de compresión con JACU utilizando distintos tamaños - de página en el Block Sorting, y comparando contra Zero Grouping. + de página en el Block Sorting, y comparando contra Zero Grouping y Word + Escaping. \layout Standard \align center \begin_inset Tabular - + @@ -3703,6 +4182,8 @@ Comparaci + + \begin_inset Text @@ -3770,6 +4251,22 @@ Filename 32K WS \end_inset + +\begin_inset Text + +\layout Standard + +128K +\end_inset + + +\begin_inset Text + +\layout Standard + +128K ZG +\end_inset + @@ -3805,6 +4302,9 @@ s \layout Standard +0.772 +\size footnotesize +s \end_inset @@ -3812,6 +4312,9 @@ s \layout Standard +0.821 +\size footnotesize +s \end_inset @@ -3844,6 +4347,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 + @@ -3895,6 +4418,9 @@ s \layout Standard +5.472 +\size footnotesize +s \end_inset @@ -3902,6 +4428,9 @@ s \layout Standard +7.939 +\size footnotesize +s \end_inset @@ -3934,6 +4463,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 + @@ -3969,6 +4518,9 @@ s \layout Standard +4.622 +\size footnotesize +s \end_inset @@ -3976,6 +4528,9 @@ s \layout Standard +4.723 +\size footnotesize +s \end_inset @@ -4008,6 +4563,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 + @@ -4043,6 +4618,25 @@ s \layout Standard + +\family roman +\series medium +\shape up +\size normal +\emph off +\bar no +\noun off +\color none +0.826 +\family default +\series default +\shape default +\size footnotesize +\emph default +\bar default +\noun default +\color default +s \end_inset @@ -4050,6 +4644,9 @@ s \layout Standard +0.827 +\size footnotesize +s \end_inset @@ -4082,6 +4679,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 + @@ -4133,6 +4750,9 @@ s \layout Standard +2.943 +\size footnotesize +s \end_inset @@ -4140,6 +4760,9 @@ s \layout Standard +2.906 +\size footnotesize +s \end_inset @@ -4172,8 +4795,28 @@ 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 + + + \begin_inset Text @@ -4207,6 +4850,9 @@ s \layout Standard +0.661 +\size footnotesize +s \end_inset @@ -4214,6 +4860,9 @@ s \layout Standard +0.647 +\size footnotesize +s \end_inset @@ -4246,6 +4895,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 + @@ -4281,6 +4950,9 @@ s \layout Standard +2.175 +\size footnotesize +s \end_inset @@ -4288,6 +4960,9 @@ s \layout Standard +2.258 +\size footnotesize +s \end_inset @@ -4320,6 +4995,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 + @@ -4355,6 +5050,9 @@ s \layout Standard +0.416 +\size footnotesize +s \end_inset @@ -4362,6 +5060,9 @@ s \layout Standard +0.426 +\size footnotesize +s \end_inset @@ -4394,6 +5095,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 + @@ -4429,6 +5150,9 @@ s \layout Standard +0.610 +\size footnotesize +s \end_inset @@ -4436,6 +5160,9 @@ s \layout Standard +0.571 +\size footnotesize +s \end_inset @@ -4468,6 +5195,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 + @@ -4519,6 +5266,9 @@ s \layout Standard +0.330 +\size footnotesize +s \end_inset @@ -4526,6 +5276,9 @@ s \layout Standard +0.366 +\size footnotesize +s \end_inset @@ -4558,6 +5311,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 + @@ -4593,6 +5366,9 @@ s \layout Standard +0.120 +\size footnotesize +s \end_inset @@ -4600,6 +5376,9 @@ s \layout Standard +0.108 +\size footnotesize +s \end_inset @@ -4632,6 +5411,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 + @@ -4667,6 +5466,9 @@ s \layout Standard +0.114 +\size footnotesize +s \end_inset @@ -4674,6 +5476,9 @@ s \layout Standard +0.107 +\size footnotesize +s \end_inset @@ -4706,6 +5511,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 + @@ -4741,6 +5566,9 @@ s \layout Standard +0.306 +\size footnotesize +s \end_inset @@ -4748,6 +5576,9 @@ s \layout Standard +0.313 +\size footnotesize +s \end_inset @@ -4780,6 +5611,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 + @@ -4831,6 +5682,9 @@ s \layout Standard +0.292 +\size footnotesize +s \end_inset @@ -4838,6 +5692,9 @@ s \layout Standard +0.313 +\size footnotesize +s \end_inset @@ -4855,6 +5712,9 @@ s \layout Standard +0.341 +\size footnotesize +s \end_inset @@ -4867,6 +5727,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 + @@ -4902,6 +5782,9 @@ s \layout Standard +0.585 +\size footnotesize +s \end_inset @@ -4909,6 +5792,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 @@ -4926,6 +5828,9 @@ s \layout Standard +1.229 +\size footnotesize +s \end_inset @@ -4954,6 +5859,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 + @@ -4989,6 +5914,9 @@ s \layout Standard +0.510 +\size footnotesize +s \end_inset @@ -4996,6 +5924,9 @@ s \layout Standard +0.598 +\size footnotesize +s \end_inset @@ -5013,6 +5944,9 @@ s \layout Standard +0.689 +\size footnotesize +s \end_inset @@ -5025,6 +5959,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 + @@ -5060,6 +6014,9 @@ s \layout Standard +0.832 +\size footnotesize +s \end_inset @@ -5067,6 +6024,9 @@ s \layout Standard +0.926 +\size footnotesize +s \end_inset @@ -5084,6 +6044,9 @@ s \layout Standard +1.401 +\size footnotesize +s \end_inset @@ -5096,6 +6059,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 + @@ -5131,6 +6114,9 @@ s \layout Standard +551 +\size footnotesize +s \end_inset @@ -5138,6 +6124,9 @@ s \layout Standard +572 +\size footnotesize +s \end_inset @@ -5155,6 +6144,9 @@ s \layout Standard +611 +\size footnotesize +s \end_inset @@ -5167,6 +6159,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 +