Algoritmo de Huffman adaptativo

Por Saiyine  el 2005-03-10 03:19:00 - Secciones:  ARTICULO  - Enlace permanente: 365

Los códigos de Huffman son posiblemente la variante más conocida de los compresores estadísticos, que aprovechan las características estadísticas de los datos de entrada asignando códigos más cortos a los datos que mas se repiten, logrando así un efecto compresor.

Para lograrlo, el compresor debe recorrer una vez el vector con la información entrante para crear una tabla con la frecuencia de cada carácter, y luego otra vez para traducir la fuente en los códigos adecuados. Esta doble pasada no siempre es posible, y aquí es donde entran las variantes adaptativas, que son capaces de generar la compresión en una sola pasada, al ir modificando los códigos de salida conforme van llegando nuevos códigos a la entrada.

El algoritmo

Como ya mencioné anteriormente, la compresión Huffman adaptativa se diferencia de la normal en que los datos estadísticos se generan en la misma pasada que se envían los códigos de salida, y esto tiene un problema evidente: ¿cómo se envía un dato que aún no ha sido registrado en la tabla de símbolos? ¡Reconstruir la tabla con cada carácter nuevo requeriría muchísimo tiempo de CPU!

Por ello, lo que se hace es modificar el árbol binario del algoritmo Huffman añadiendo un valor especial llamado NYT, not yet transmitted, que servirá como marcador de nuevo carácter, es decir, si tenemos la entrada “arañar”, la salida seria “NYT a NYT r CODIGO(a) NYT ñ CODIGO(a) CODIGO(r)”.

Otro problema que surge es el de la optimalidad de los códigos, ya que si simplemente vamos añadiendo caracteres al árbol estadístico conforme aparecen en la entrada, se perderían las ventajas de la compresión Huffman. Por ello, cada vez que se lee un carácter hay que actualizar el árbol, que pasa a ser bastante mas complejo que el algoritmo no adaptativo, de una manera determinada, dependiendo de si es un nuevo carácter o si ya estaba en el árbol.

Fig. 1. Árbol de ejemplo, conteniendo la palabra “abra”

Los nuevos elementos que podemos advertir en el árbol binario del algoritmo adaptativo frente al clásico son la presencia del código NYT, la numeración de los nodos y un contador de cada carácter. Con este contador llevamos la cuenta de cuantas veces ha aparecido el valor, y es lo que definirá en que posición del árbol pondremos al carácter en caso de reorganización, mientras que la numeración nos servirá para decidir que nodos deben intercambiar su posición.

Un ejemplo paso a paso

Veamos con un ejemplo como funciona el algoritmo, usando la palabra “abracadabra”.

Fig. 2. Árbol vacío

Comenzamos con un árbol vacío, al que le llega el primer carácter, “a”.

Fig. 3. Árbol para “a”

Con la llegada del primer dato, el algoritmo envía el dato tal cual, “a” y después genera los primeros nodos del árbol, es decir, el nodo para el NYT, con el contador a cero, y el del propio dato, con el contador a uno, y el nodo padre, el raíz en este caso, con la suma de los contadores de sus hijos.

Fig. 4. Árbol para “ab”

Tenemos un nuevo dato, así que enviamos el NYT para comunicárselo al destino, seguido del propio dato, por lo que el mensaje enviado completo por el momento es “a 0b”. Este mensaje realmente se compone de los ocho bits del símbolo “a”, seguido del bit 0 y de los ocho de “b”, por lo que es importante que tanto compresor como receptor estén de acuerdo en el tamaño del dato base, que en el programa que nos ocupa es de ocho bits.

Una vez enviados los nuevos códigos, se reestructura el árbol añadiendo el nuevo carácter “b” como hijo derecho del NYT, y creando un nuevo NYT como hijo izquierdo, y actualizando los contadores en cascada hacia la raíz, efectivamente creando un árbol balanceado.

Fig. 5a. Árbol para “abr” no actualizado

Con el nuevo carácter “r” llegamos a un punto crucial del algoritmo: la actualización del árbol. Primero, se manda el NYT y el dato r, con lo que el mensaje comprimido es ahora “a 0b 00r” (recordemos que siempre se mandan los NYT de antes de meter el nuevo carácter en el árbol). Lo introducimos en el lugar del NYT y llegamos a una posición en la que no se cumple la posición de balanceo del árbol, ya que el nodo 49 tiene el valor 2, suma de los valores de sus dos hijos, mientras que su hermano 50 tiene el valor 1, ya que el carácter “a” solo ha aparecido una vez hasta ahora. Por lo tanto, los intercambiamos, en un ajuste de balanceo que en este algoritmo es llamado simplemente proceso de ajuste del árbol.

Fig. 5b. Árbol para “abr” actualizado

Otro carácter “a”, que como ya está en el árbol es enviado comprimido, con lo que tenemos “a 0b 00r 0”.

Fig. 6. Árbol para “abra”

Ahora es el turno del dato “c”, que como no está en el árbol, mandamos el NYT y el dato en claro: “a 0b 00r 0 100c”. Después lo añadimos al árbol.

Fig. 7a. Árbol para “abrac” no actualizado

De nuevo el árbol necesita ser actualizado, ya que los nodos 47 y 48 han dejado de cumplir la condición de balanceo.

Fig. 7b. Árbol para “abrac” actualizado

Otra “a”, con lo que el mensaje completo es ahora “a 0b 00r 0 100c 0”.

Fig. 8. Árbol para “abraca”

El dato “d” es nuevo, así que lo enviamos (“ a 0b 00r 0 100c 0 1100d ”)y expandimos el nodo de NYT para acomodarlo. Además, va a desequilibrar el árbol, que necesitará un ajuste.

Fig. 9a. Árbol para “abracad” antes de actualizar

Fig. 9b. Árbol para “abracad” balanceado

La tercera “a”, con lo que el mensaje comprimido es ahora “a 0b 00r 0 100c 0 1100d 0”.

Fig. 10. Árbol para “abracada”

El siguiente carácter “b”, aunque ya está en el árbol y podría parecer que simplemente bastaría con aumentar su contador y enviar su código, en realidad va a generar un proceso interesante que podría cambiar el árbol casi por completo: una actualización en cascada.

Fig. 11a. Árbol para “abracadab” sin actualizar

Primero, los nodos 45 y 46 deben ser intercambiados, ya al aumentar el contador de b, su nodo tiene mas “peso” que su hermano derecho.

Fig. 11b. Árbol para “abracadab” actualizándose

Intercambiados los nodos, aumentamos el valor de “b” y de los padres hasta la raíz, verificando en cada nodo si es necesaria una nueva actualización, aunque en este ejemplo no se da el caso.

Fig. 11c. Árbol para “abracadab” actualizado

Los dos caracteres que faltan, “r” y “a”, no tienen mucha historia, simplemente enviamos el código y actualizamos los contadores correspondientes, con lo que el código final es “a 0b 00r 0 100c 0 1100d 0 110 110 0”, es decir, 60 bits, frente a los 88 que harían falta para mandar el mensaje sin comprimir.

Fig. 12. Árbol para “abracadabr”

Fig. 13. Árbol para “abracadabra”

La descompresión

Ahora veamos un ejemplo de descompresión. Tenemos la cadena “a 0b 00r 0 100c 0 1100d 0 110 110 0” (de nuevo, imaginemos que en vez de los caracteres tenemos grupos de 8 bits con la representación ascii de dichos caracteres). Leemos los primeros ocho bits, ya que forzosamente el primer carácter debe estar sin codificar, con lo que ya tenemos la “a”, y la introducimos en el árbol. El siguiente dato, o bien es un uno si es otra vez la “a”, o es un cero para indicar el valor NYT. En nuestro caso, es un cero, así que lo leemos y los siguientes ocho bits, con lo que ya tenemos “ab”.

Ahora el descompresor tendría en su memoria un árbol análogo al de la figura 4, por lo que al leer un cero sabemos que debemos leer al menos un bit más. Efectivamente, nos llega otro cero, con lo que tenemos un NYT. Leemos otros ocho bits y ya tenemos “abr”. Actualizamos el árbol, igual que hacíamos en la compresión, y leemos un cero, lo que nos indica que tenemos otra “a”.

Leemos un bit y tenemos un uno, que no es ningún código conocido, leemos otro y tenemos uno-cero, que sigue siendo desconocido. Volvemos a leer y tenemos uno-cero-cero, que en la disposición actual del árbol ( fig 6 ) es un NYT. Leemos ocho bits más, tenemos “abrac”. Sacamos un cero de la cadena, y como sabemos por el árbol que es una “a”, tenemos “abraca”.

Se lee bit a bit hasta que tenemos una combinación con significado, y en este caso, se trata de nuevo de un NYT, acompañado de los ocho bits de la “d”, con lo que el código hasta ahora es “abracad”. Hasta el final, tenemos caracteres sueltos que completan el mensaje, que es, claro esta, “abracadabra”.

Tu nombre (Nick):

Tu correo (Email):
  Necesario para tu gravatar!

Tu página (URL):

Escribe aqui tu comentario:

      

Vista previa activada.