Agrego el Mitico y Enigmatico Word Scaping al block sorting. Para usarlo usar parame...

[z.facultad/75.06/jacu.git] / doc / InformeTP3.lyx

diff --git a/doc/InformeTP3.lyx b/doc/InformeTP3.lyx
index c8fd5fa2cb0af11317746c29b84e6ffd6ed9467b..5c9068e66121dd3aefa468f238c7fed407b57df4 100644 (file)
--- 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 
 \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
  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 
 
 
 \family typewriter 

+\noun on 

 HUFF_STATE *shuff_init_encoder_byfile(char *inputfile, char *outputfile,
  long volsize);
 \layout Itemize
 
 
 \family typewriter 
 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 
 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 
 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 
 void shuff_deinit_encoder(HUFF_STATE *shuff);
 \layout Itemize
 
 
 \family typewriter 

+\noun on 

 void shuff_deinit_decoder(HUFF_STATE *shuff);
 \layout Standard
 
 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
 
 
 \layout Section
 
 


@@ -535,20 +588,77 @@ BS
 \series default 
  que aumenta la localidad, genera estadísticamente muchas secuencias de
  ceros repetidos.
 \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
  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.
  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:
 \layout Subsubsection*
 
 Ejemplo:


@@ -589,7 +699,7 @@ ZG
 
 \end_inset 
 
 
 \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 
  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
 
 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
 \the_end