\layout Subsection
Move to Front
+\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
+
+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 Subsection
Huffman Estático
\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
\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
\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:
\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
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
projects / z.facultad / 75.06 / jacu.git / blobdiff