Compresión Huffman

Entender los Algoritmos de Compresión de Huffman, LZ y LZ77 Por DARK-N naldo_go@hotmail.com Julio del 2004/Revisado: Dic/2006 V1.1: Algoritmo LZ77 explicado http://bicharraco.dyndns.org/darkn

NOTA 1: Todo lo que hay aquí es TEORIA, nada de cómo implementarlo en ASM.

NOTA 2: Lo que investigue estaba todo en ingles y portugués por lo que pueda que tenga errores en algunas cosas que yo las entendí de cierta forma y quizás no es así, por lo que sugiero que si alguien sabe mi error (si es que lo hay) que me mande un mail.

CONTENIDO

Introducción 2 Algoritmo de Huffman 3 Como Funciona Teóricamente 3 Como funciona en la práctica con un Ejemplo 3 LZ (Lempel-Ziv) 6 Como Funciona Teóricamente 6 Como funciona en la práctica con un Ejemplo 7 La Descompresión 9 LZ77 10 Conceptos previos 10 DECODIFICACIÓN 12 MEJORAS DE LZ77: 13

Introducción

La compresión busca reducir el número de bits para almacenar o transmitir información. Los compresores de datos se dividen en 2 grandes familias: Los compresores SIN pérdida de la información (Losless) y los compresores CON pérdida de información (Lossy).

Los compresores con pérdida son utilizados para comprimir representaciones digitales con señales análogas como por ejemplo sonidos o imágenes (les suena mp3 o jpeg). Esto es ya que los datos si los descomprimimos no necesariamente deben ser una copia exacta de los originales debido a que esta perdida de información no es importante para el sistema audio/visual humano.

En cambio los compresores sin pérdida de información garantizan la regeneración exacta de los datos comprimidos, al momento de realizar la descompresión ya que no se ha perdido ningún tipo de información. Esta es la compresión que se usa cuando se almacenan archivos con caracteres ASCII, registros de una base de datos, información de una hoja de cálculo, etc. Estos compresores son los llamados “compresores de Texto”.

La compresión sin pérdida de información se ocupa para comprimir texto, y existen varios algoritmos para estos casos, los cuales los mas importante son LZ77 y LZ88 (con sus variantes LZW y LZH) y el famoso Huffman muy conocido solo “de nombre” por nosotros, los traductores de juegos.

Los más comunes algoritmos de compresión son:

Compresión Lossless (compresión SIN pérdida de la información)

• Run-length encoding - PackBits - PCX

• Código de mínima redundancia también conocido entropy coding - Huffman coding (entropy coding simple) - Arithmetic coding (entropy coding avanzado)

• Dictionary coders - DEFLATE - LZ77 & LZ78 - LZW - Other LZ compression methods

• Burrows-Wheeler transform (procesamiento de ordenamiento de bloques)

Compresión Lossy (compresión CON pérdida de la información)

• Discrete cosine transform based coders - MPEG (compresión de video) - MP3 (compresión de música y sonido de moda) - JPEG (compregión de imagen)

• Compresión Fractal - Fractal transform • Compresión Wavelet

Algoritmo de Huffman

(Para este documento me base en uno hecho por Salvador Pozo, pero jamás hice un Copy-Paste)

Un clásico algoritmo usado en muchos juegos de SNES para comprimir texto. Fue creado por David A. Huffman en 1952 y es usado ampliamente en programas de compresión como GZIP, máquinas de FAX, esquemas de compresión de imágenes como el conocido JPEG, etc. Este algoritmo utiliza el método llamado la propiedad de estadística de alfabetos en fuentes de corriente (the statistical property of alphabets in source stream) [Walley, 1997]

Como Funciona Teóricamente

Este algoritmo se basa en asignar códigos de distinta longitud de bits a cada uno de los caracteres de un fichero. Si se asignan códigos más cortos a los caracteres que aparecen más a menudo se consigue una compresión del archivo. Esta compresión es mayor cuando la variedad de caracteres diferentes que aparecen es menor. Por ejemplo: si el texto se compone únicamente de números o mayúsculas, se conseguirá una compresión mayor. El algoritmo de codificación es el siguiente: • Contar cuantas veces aparece cada carácter en el fichero a comprimir. Y crear una lista enlazada con la información de caracteres y frecuencias. • Ordenar la lista de menor a mayor en función de la frecuencia. • Convertir cada elemento de la lista en un árbol. • Fusionar todos estos árboles en uno único, para hacerlo se sigue el siguiente proceso, mientras la lista de árboles contenga más de un elemento: o Con los dos primeros árboles formar un nuevo árbol, cada uno de los árboles originales en una rama. o Sumar las frecuencias de cada rama en el nuevo elemento árbol. o Insertar el nuevo árbol en el lugar adecuado de la lista según la suma de frecuencias obtenida. • Para asignar el nuevo código binario de cada carácter sólo hay que seguir el camino adecuado a través del árbol. Si se toma una rama cero, se añade un cero al código, si se toma una rama uno, se añade un uno. • Se recodifica el fichero según los nuevos códigos.

Como funciona en la práctica con un Ejemplo

Tomemos un texto corto, por ejemplo: "ata la jaca a la estaca" Recuerda que cada letra es un byte, entonces el texto tiene 23 byte. 1) Contamos las veces que aparece cada carácter y hacemos una lista enlazada: ' '(5), a(9), c(2), e(1), j(1), l(2), s(1), t(2) 2) Ordenamos por frecuencia de menor a mayor e(1), j(1), s(1), c(2), l(2), t(2), ' '(5), a(9) 3) Consideremos ahora que cada elemento es el nodo raíz de un árbol.

4) Fundimos los dos primeros nodos (árboles) en un nuevo árbol, sumamos sus frecuencias y lo colocamos en el lugar correspondiente, a este árbol se le llama Árbol Huffman:

Y sucesivamente:

El resultado final es:

5) Asignamos los códigos, las ramas a la izquierda son ceros, y a la derecha unos (por ejemplo), es una regla arbitraria. Recuerda que el carácter con mayor probabilidad tiene menor número de bits asignados, para que la cantidad de bits finales sea menor. a ' ' c l t s e j 0 10 1100 1101 1110 11110 111110 111111 6) Y traducimos el texto: a t a ' ' l a ' ' j a c a ' ' a ' ' l a ' ' e s t a c a 0 1110 0 10 1101 0 10 111111 0 1100 0 10 0 10 1101 0 10 111110 11110 1110 0 1100 0 Y sólo queda empaquetar los bits en grupos de ocho, es decir en bytes: 01110010 11010101 11111011 00010010 11010101 11110111 10111001 10000000 0x72 0xD5 0xFB 0x12 0xD5 0xF7 0xb9 0x80 En total 8 bytes, y el texto original tenía 23. Pero no nos engañemos, también hay que almacenar la información relativa a la codificación, por lo que se puede ver que para textos cortos no obtendremos mucha reducción de tamaño.

LZ (Lempel-Ziv) Este algoritmo (es en verdad un estilo de algoritmo) fue descubierto por Jakob Ziv y Abraham Lempel en 1977 y 1978. Existen 3 tipos de algoritmos LZ, estos son LZ77, LZ78 y LZSS. LZW (Lempel-Ziv Welch) es una variante de LZ78 y que es usado en programas de compresión como el compress de UNIX. LZH es una modificación de LZ77 que incluye un segundo nivel de compresión usando codificación de Huffman. En esta guía se explicará LZ77 ya que es usado en compresión de gráficos y textos de SNES. La particularidad de LZ es que además de tomar en cuenta los caracteres uno a uno de una frase o palabra, sino que además se consideraran aquellas secuencias de alta probabilidad en el texto. Por ejemplo, en el texto: aaabbaabaa Obtendríamos un mayor grado de eficiencia si además de considerar caracteres como a y b, también considerásemos la secuencia aa al momento de codificar. Como Funciona Teóricamente Como la compresión LZ es de Diccionario, por lo que usa un diccionario y su medida varia dependiendo del máximo valor de entrada y del número de entradas. El diccionario es conocido como ventana sliding (sliding window) que es básicamente un buffer historial que guarda los últimos n bytes de entrada que no tengan una combinación. A esta ventana de le hacen referencias (con un offset y cierto largo). LZ77 tiene una ventana sliding, con un máximo de largo de 0K a 64K, así en esta ventana no puede estar todo el archivo o frase en caso que sea mayor a 64K. También usa un buffer delantero (ahead buffer) que opuesto a la ventana sliding ya que se guardan los primeros n bytes de la entrada o que se leen. Los valores extremos de este buffer delantero es de 0 - 258.

El algoritmo de codificación es el siguiente: 1. Leer del buffer delantero n bytes (n es el tamaño del buffer delantero). 2. Buscar la ventana sliding por la mejor combinación de datos del buffer delantero. Si se encuentra pasamos al punto 3, si no, la ventana y el buffer avanza un byte, la salida es el primer byte del Buffer y se sigue leyendo. Pasamos al Paso 1. 3. Si el largo de la combinación es mayor que el mínimo largo de match o combinación (generalmente es 2), entonces la Salida output es el par <largo, distancia>. Donde largo es el largo del match, y la distancia es cuantos bytes hacia atrás de la entrada fue encontrado el match.

Como funciona en la práctica con un Ejemplo La Compresión del algoritmo de LZ común (Explicado por un tal Jay, mejorado por mi)

Tomemos la frase:

Los "_" son Espacios. Este es el mensaje original son 43 bytes, o 43 x 8 = 344 bits de largo. Lo primero que hace LZ77 es buscar una combinación (o match) repetidos y que estan JUNTAS así en el ejemplo avanzamos letra a letra (de 1 avanzando) y nos encontramos con rain_in_ es decir:

the_rain_

y seguido: in_

Paso 1: El buffer delantero leyó 9 bytes (the_rain_) y luego se encuentra con una combinación entonces the_rain_pasa a ser parte de la ventana sliding y el buffer delantero ahora es “in_”. Paso 2: Entonces tomando el contenido del buffer delantero se busca la mejor combinación dentro del la ventana sliding y se encuentra (in_). Paso 4: Como el largo del match es 3 (in_) y es mayor al mínimo largo del match, 2 (ya que 2 caracteres deben comprimirse como mínimo), entonces se representa con un puntero que nos indica el largo y la distancia hacia atrás donde esta la combinación repetida, es un puntero <largo, distancia>. En tutoriales en ingles le llaman pointer <length, offset>. De esta forma tenemos:

the_rain_<3,3>

El “the_rain_” se quedará sin comprimir en cuanto al <3,3> es porque el largo de la combinación es 3 y si nos situamos en el carácter 10 (letra i) que es donde nos encontramos ahora y vamos hacia atrás 3 espacios nos encontramos con el comienzo de lo que queremos almacenar.

Hay 2 formatos de punteros:

• Un puntero de 8-bit + 4-bit largo, el cual asume un máximo distancia (offset) de 255 y un largo (length) de 15. • Un puntero de 12-bit + 6-bit largo, que asume un máximo distancia de 4096, lo que implica un buffer de 4 KB, y un largo máximo de 63.

También hay un bit FLAG con un valor de 0 que indica un puntero. Este es seguido por un segundo bit que indica el formato del puntero que se usara, con un 0 indica el un puntero de 8-bit y un 1 indica a uno de 12-bit. De esta forma, bináriamente el puntero <3,3> es así:

00 00000011 0011

Los primeras 2 bits son las Flag, indican un puntero de 8 bit. Los siguientes 8 bits son la distancia o valor del puntero (3), y los ultimos 4 son el largo.

Sigamos con la frace:

Sp

El cual tiene salida sin comprimir, por lo que queda:

the_rain_<3,3>Sp

Ahora nos damos cuenta que los caracteres "ain_" de “Spain” en “rain” por lo que se comprimen con un puntero:

the_rain_<3,3>Sp<9,4>

El <9,4> es que tensmos una distancia hacia atras de 9 y un largo (ain_) de 4. La distancia es 9 ya que si nos situamos en la letra a de “Spain_” y vamos 9 espacios hacia atrás nos encontramos con la letra a de “rain_”.

Seguimos leyendo y nos encontramos con “falls_mainly_” por lo que nos da:

the_rain_<3,3>Sp<9,4>falls_m<11,3>

Nota que hacemos referencia a “Spain” y NO a rain, es decir a la ocurrencia mas cercana por eso nos da <11,3>. Esto es para que nos de un puntero mas pequeño.

Los caracteres "ly" son lacados sin compresión pero "in_" y "the_" si se comprimen cada uno con su puntero, quedando:

the_rain_<3,3>Sp<9,4>falls_m<11,3>ly_<16,3><34,4>

Finalmente los caracteres "pl" se sacan sin comprimir, y "ain" nuevamente se comprime quedando:

the_rain_<3,3>Sp<9,4>falls_m<11,3>ly_<16,3><34,4>pl<15,3>

Esto nos da 23 caracteres sin comprimir con 9 bits cada uno, + 6 punteros de 14 bits, son un total de 291 bits.

Explicación: • Cada carácter sin comprimir es de 9 bit ya que al aplicarle este método se le agrega información. Originalmente cada carácter es de 8 bytes y se le agrega un 1 bit por el FLAG que indica 1 si NO hay puntero o 0 si hay puntero. Por esto hay raras veces que un archivo comprimido tiene un tamaño mayor que el original. • Los punteros son de 12 Bits (primer formato) ya que ninguno supero una distancia de 255 y se le agregan 2 bits más por los 2 Flag de Largo y Distancia. En total 12 + 2 = 14 bits.

Cantidad Total de Bits = ( 23 x 9 ) + ( 6 x 14 ) = 291.

Si los comparamos con los 344 bits que teníamos en un principio, ¡logramos una compresión! Esta no es una mala compresión a pesar de ser tan corto el mensaje, pero en la práctica se aplica con textos mucho más largos.

La Descompresión

Es muy simple ya que toma la frase comprimida:

Y se recorre de izquierda a derecha. Cuando se encuentra un puntero, se COPIAN los caracteres indicados por <distancia hacia atrás, largo de copiado>. De esta forma avanzamos y nos encontramos <3,3> es decir, vamos hacia a atrás 3 espacios y llegamos al carácter “i” ahora copiamos 3 espacios hacia delante, es decir “in_”, de esta forma nos queda:

El texto se descomprime como se ve arriba, entonces se sigue avanzando. Luego nos encontramos con <9,4>, bajamos 9 espacios y copiamos 4, es decir “ain_”, ahora nos queda:

y así sucesivamente, hasta que tenemos el texto completo descomprimido con sus 43 caracteres (43 bytes):

LZ77 (Extraído y mejorado del original del PPT de ROQUE MARÍN roque@dif.um.es)

Conceptos previos

El diccionario es una porción de la secuencia previamente codificada.

El codificador examina la secuencia de caracteres de entrada a través de una ventana deslizante que consta de dos partes: - Un buffer de búsqueda (Search Buffer): porción de la secuencia recién codificada - Un buffer de anticipación (Look-ahead Buffer): siguiente porción a codificar.

Para codificar la secuencia que hay en el buffer de anticipación:

-Se mueve un puntero de búsqueda hacia atrás sobre el buffer de búsqueda hasta que encuentra un carácter que concuerda con el primero del buffer de anticipación

-La distancia del puntero al buffer de anticipación se denomina offset (o)

-Comprueba si los caracteres que vienen a continuación del puntero concuerdan con los caracteres consecutivos del buffer de anticipación

-El número de caracteres consecutivos en el buffer de búsqueda que concuerdan con caracteres consecutivos del buffer de anticipación se llama longitud (l)

-Siempre busca la coincidencia de mayor longitud.

-Una vez que ha encontrado la coincidencia de mayor longitud, la codifica con una tripleta <o, l, c>, donde c es la palabra código correspondiente al carácter del buffer de anticipación que viene a continuación de la coincidencia

El número de dígitos binarios necesarios para codificar la tripleta es:

nº bits = log2 S + log2 W + log2 A

-S es el tamaño del buffer de búsqueda -W es el tamaño total de la ventana (S más tamaño del buffer de anticipación) -A es el número de posibles caracteres (mensajes de la fuente) Se considera W, en lugar de S, para tener en cuenta el caso en el que la longitud de la coincidencia excede a la longitud del buffer de búsqueda. - Log es un “Logaritmo” y Log 2 es Logaritmo en base 2. Matemática básica.

EJEMPLO:

Ejemplo: Supongamos que hay que codificar la secuencia: “...cabracadabrarrarrad....” El tamaño de la ventana que nos daremos es W = 13 caracteres. El tamaño del buffer de búsqueda para este ejemplo será S = 7.

Se ha comenzado a codificar y se ha llegado a la siguiente situación:

Recorremos el buffer de búsqueda buscando una d. No se encuentra coincidencia dentro del Buffer. Se transmite la tripleta <0, 0, C(d)> C(d) es, por ejemplo, la palabra código ASCII correspondiente a d.

Se desplaza la ventana deslizante hacia el siguiente carácter. Recorremos el buffer de búsqueda buscando una a.

-Se encuentra una coincidencia con o = 2 y l = 1. (recuerda 0=offset I=longitud) -Se continua buscando una a y se encuentra otra coincidencia con o = 4 y l = 1. -Se continua buscando una a y se encuentra otra coincidencia con o = 7 pero la Longitud aquí es primeramente 1 luego si coinciden consecutivamente lo del Buffer de Anticipación y el de Búsqueda se alarga esta Longitud, entonces vemos que después de la A en ambos casos sigue B, luego R, luego A, entonces se le suman 3 al largo que teniamos, es decir que finalmente la Longitud es 4. Finalmente queda o=7 y l=4.

Esta última es la coincidencia más larga. Se transmite la tripleta <7, 4, C(r)>

El C(r) nos dice que se desplaza la ventana deslizante (el buffer de búsqueda) 5 caracteres y nos encontramos en el Buffer de Anticipación con una r, entonces recorremos el buffer de búsqueda buscando una r.

Se encuentra de r una coincidencia con o = 1 y l = 0. Se continúa buscando una r y se encuentra otra coincidencia con o = 3 y l = 5. Observar que la coincidencia se adentra en el buffer de anticipación.

Como esta ultima es la coincidencia más larga., se transmite la tripleta <3, 5, C(d)>

En resumen, el fichero comprimido consta de las tripletas: ... <0, 0, C(d)>, <7, 4, C(r)>, <3, 5, C(d)>, ...

DECODIFICACIÓN

Supongamos que ya ha decodificado la secuencia cabraca Recibe a continuación las tres tripletas: <0, 0, C(d)>, <7, 4, C(r)>, <3, 5, C(d)>, ...

La primera tripleta <0, 0, C(d)> indica que no hay coincidencias y que hay que generar el carácter d

La secuencia decodificada es ahora cabracad

La segunda tripleta <7, 4, C(r)> indica que hay que mover el puntero 7 posiciones hacia atrás. Y hay que copiar 4 caracteres a partir del puntero.

Finalmente, genera el carácter r

La secuencia decodificada es ahora cabracadabrar

La tercera tripleta <3, 5, C(d)> indica que hay que mover el puntero 3 posiciones hacia atrás

Y hay que copiar 5 caracteres a partir del puntero. Se comienza copiando 3 caracteres.

Y se copian dos más.

Finalmente, genera el carácter d

La secuencia decodificada es ahora cabracadabrarrarrd

MEJORAS DE LZ77:

Hay distintas variantes que mejoran el algoritmo básico:

Hemos asumido que las tripletas se codifican con secuencias de longitud fija (por ejemplo, tres bytes)

Mejora: Codificar las tripletas en longitud variable Ej: Pkzip, Zip, LHarc, PNG, gzip, ARJ se basan en LZ77 con tripletas de longitud variable

Otras variantes consisten en usar grandes bufferes y estrategias de búsqueda rápida.

La codificación de tripletas del tipo <0, 0, C(d)> es ineficiente, sobretodo si aparece un gran número de caracteres infrecuentes. Mejora: Usar un bit de flag que indica si lo que sigue es la palabra código de un solo carácter Así se transmiten sólo palabras código C(d) o parejas <o, l>, y se intercala el bit de flag cada vez que se cambia de unas a otras.

El algoritmo LZ77 parte de la suposición de que los patrones recurrentes aparecen próximos : Sólo busca en el “pasado cercano” (dentro del buffer de búsqueda) Desaprovecha las recurrencias “lejanas”

El peor caso: un archivo con un patrón periódico, pero con un periodo mayor que la longitud del buffer

• Ejemplo: En este caso, cada carácter iría como una tripleta (expande en lugar de comprimir)

En LZ78, Lempel y Ziv eliminaron la suposición de recurrencia cercana: En lugar de ventana deslizante, construye explícitamente un diccionario. Compresor y descompresor construyen así un diccionario idéntico.

El algoritmo genera parejas : • i es un índice que indica la posición dentro del diccionario de la secuencia previa más larga coincidente con la entrada • C es el código del carácter que viene a continuación de la secuencia coincidente • Si no se encuentra coincidencia, i = 0 • Cada nueva pareja generada <i, C> se añade al diccionario.

Por Dark-N naldo_go@hotmail.com