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”.