X-Git-Url: https://git.llucax.com/z.facultad/75.06/jacu.git/blobdiff_plain/64d649ff0b05d95cdd40ee1a59fff0ba2100bc52..b7363b3e0c059ce04f5f2bfa913e06940915aa7c:/doc/InformeTP3.lyx?ds=sidebyside

diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx
index c8fd5fa..5c9068e 100644
--- a/doc/InformeTP3.lyx
+++ b/doc/InformeTP3.lyx
@@ -428,7 +428,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 +441,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
 
 
@@ -535,20 +588,77 @@ BS
 \series default 
  que aumenta la localidad, genera estadísticamente muchas secuencias de
  ceros repetidos.
- El algoritmo es muy simple, cada secuencia de ceros se codifica con 2 bytes,
- el primero es siempre 0 (0x00) y el segundo indica la cantidad de ceros
- que le siguen.
+ Como el Huffman Estático no aprovecha esta característica (comprime igual
+ 
+\family typewriter 
+000001234
+\family default 
+ que 
+\family typewriter 
+010203040
+\family default 
+), se buscó un método que sí la explote para optimizar el compresor y se
+ llegó a un algoritmo muy simple que bautizamos 
+\series bold 
+Zero Grouping
+\series default 
+.
+\layout Standard
+
+Cada secuencia de ceros se codifica con 2 bytes, el primero es siempre 0
+ (
+\family typewriter 
+0x00
+\family default 
+) y el segundo indica la cantidad de ceros que le siguen.
  En el caso de haber un byte de valor cero aislado, también se codifica
- con 2 bytes (0x00 0x00, que indica que viene un cero y luego de ese cero
- no viene ningún cero más), expandiendo la salida, pero estos son casos
- aislados que estadísticamente se ven superados por la cantidad de secuencias
- largas de ceros que son comprimidas a sólo 2 bytes.
+ con 2 bytes (
+\family typewriter 
+0x00 0x00
+\family default 
+, que indica que viene un cero y luego de ese cero no viene ningún cero
+ más), expandiendo la salida, pero estos son casos aislados que estadísticamente
+ se ven superados por la cantidad de secuencias largas de ceros que son
+ comprimidas a sólo 2 bytes.
  Además, la salida del 
 \series bold 
 ZG
 \series default 
  (Zero Grouping) es comprimida con Huffman por lo que en casos extremos
  la expansión no se manifiesta en forma notoria.
+\layout Standard
+
+Como la cantidad de ceros que le siguen al primero en una secuencia es expresada
+ con un byte, sólo se pueden comprimir a 2 bytes secuencias de hasta 256
+ ceros (el primer cero más los 0-255 siguientes).
+ De haber secuencias con mayor cantidad de ceros, simplemente se generan
+ 
+\family typewriter 
+N
+\family default 
+ 
+\emph on 
+grupos
+\emph default 
+ (siendo 
+\family typewriter 
+N
+\family default 
+ la cantidad de ceros en la secuencia dividido 256, redondeando hacia arriba)
+ de 2 bytes cada uno.
+ Por ejemplo, una secuencia de 257 ceros será expresada como 
+\family typewriter 
+0x00 0xFF 0x00 0x00
+\family default 
+ (2 grupos) y una de 525 como 
+\family typewriter 
+0x00 0xFF 0x00 0xFF 0x00 0x0B
+\family default 
+ (3 grupos).
+ Nuevamente, se comprobó estadísticamente que las secuencias de ceros rara
+ vez superan los 50 ceros seguidos, por lo que de utilizar más de un byte
+ para expresar la cantidad de ceros que siguen al primero se obtendrían
+ peores resultados.
 \layout Subsubsection*
 
 Ejemplo:
@@ -589,7 +699,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 
@@ -701,11 +811,23 @@ doc/api/html
 Benchmarks
 \layout Section
 
-Prueba Calgary
-\layout Section
+Prueba Calgary Corpus
+\layout Standard
 
-Archivos de Texto
-\layout Section
+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:
+\layout Standard
 
-Archivos Binarios
 \the_end