+Este algoritmo se aplica a la salida del
+\series bold
+MTF
+\series default
+ que, gracias al
+\series bold
+BS
+\series default
+ que aumenta la localidad, genera estadísticamente muchas secuencias de
+ ceros repetidos.
+ 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 (
+\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:
+\layout LyX-Code
+
+
+\size scriptsize
+Salida de MTF: 0 0 0 0 0 0 1 5 3 0 0 0 0 12 0 1 0 0 0 0 0 0 0 0 0 1 1
+ 4 0 0 1 0 2
+\layout LyX-Code
+
+
+\size scriptsize
+Salida de ZG: 0 5 1 5 3 0 3 12 0 0 1 0 8 1 1
+ 4 0 1 1 0 0 2
+\layout LyX-Code
+
+
+\size scriptsize
+ |
+ |
+\layout LyX-Code
+
+
+\size scriptsize
+ expandió
+ expandió
+\layout Standard
+
+Como se puede ver, la salida del MTF es de 33 bytes, mientras que la del
+
+\series bold
+ZG
+\series default
+ es de 22 (incluso cuando hubieron expansiones).
+ Como se podrá ver en las pruebas del capítulo
+\begin_inset LatexCommand \vref{cha:Benchmarks}
+
+\end_inset
+
+, 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
+MTF
+\series default
+.
+\layout Subsection
+
+Word-Scaping
+\layout Standard
+
+Esta optimización se ha realizado específicamente para mejorar la compresión
+ de archivos de texto.
+ La base de esta técnica es la previa confección de un diccionario de palabras
+ (en nuestro caso 255 palabras máximo), a través del cual aplicando un pre-proce
+samiento al archivo a comprimir, reemplazamos las palabras de ese diccionario
+ que se encuentren en el archivo, por un código de escape sucedido por el
+ índice en el diccionario de la palabra que se abrevia.
+\layout Standard
+
+Es decir, si tenemos el siguiente diccionario de 4 palabras:
+\family typewriter
+padre
+\family default
+,
+\family typewriter
+él
+\family default
+,
+\family typewriter
+nos
+\family default
+,
+\family typewriter
+superman
+\family default
+; y poseemos el texto:
+\emph on
+
+\begin_inset Quotes eld
+\end_inset
+
+El
+\family typewriter
+padre
+\family default
+ de
+\family typewriter
+superman
+\family default
+ es el hombre araña
+\begin_inset Quotes erd
+\end_inset
+
+
+\emph default
+, luego del pre-procesamiento tendremos:
+\emph on
+
+\begin_inset Quotes eld
+\end_inset
+
+El
+\family typewriter
+[escape][
+\backslash
+0x00]
+\family default
+ de
+\family typewriter
+[escape][
+\backslash
+0x03]
+\family default
+ es el hombre araña
+\begin_inset Quotes erd
+\end_inset
+
+
+\emph default
+.
+\layout Standard
+
+Para la confección de un buen diccionario, hemos desarrollado una utilidad
+ que contabiliza las 255 palabras que más aparecen dentro de una fuente
+ especificada, y luego del análisis de varios textos en castellano de toda
+ índole (informáticos, novelas, noticias), se obtiene el diccionario que
+ será entregado con el software.
projects / z.facultad / 75.06 / jacu.git / blobdiff