El código Hasselhoff. ¡Perdón!, "Huffman"

Después del espíritu crítico de ayer y del tono sobrio de dos post en los que, por un día, dejé de lado los conocimientos para embarcarme en la aventura de la opinión, toca "volver al tajo" y retomar un tema del que prometí hablaros en su momento. Me refiero al invento de David Huffman (que no David Hasselhoff; éste comprimía abdominales y aquél comprimía datos). Intentaré simplificar al máximo su explicación para aquellos que nunca habéis oído hablar de él o que nunca llegásteis a ver en qué consiste, porque si queréis detalles muy técnicos hay información de sobra en la Web.

Seguramente el razonamiento de Huffman debió de ser más o menos así: los códigos númericos habituales codifican utilizando siempre un número fijo de símbolos dependiendo del volumen total de elementos de información que debo codificar. Este planteamiento adolece de un gran problema, y es que, de esta manera, los elementos que se repiten con mucha frecuencia ocupan muchísimo en comparación con los que no aparecen tan asiduamente. Si hubiése alguna forma de equilibrar la balanza de modo que los elementos que se repiten con más frecuencia se codifiquen con menos símbolos que aquellos que aparecen con menos, tendría un sistema que, además de codificar, comprime. El hombre debió de ponerse manos a la obra y acabó inventando el código de longitud variable y compresión sin pérdida más famoso de la historia, hasta el punto de que, como ya os comenté en el post del 1 de octubre, su idea está presente en codificaciones tan de actualidad como el MP3.

Pero para acabar de entenderlo bien, lo mejor es un ejemplo simple. Lo he extraído de un nuevo diccionario de Informática que he descubierto hoy perteneciente a un portal denominado ¡Exception!. Supongamos que en un archivo de datos se tiene la siguiente información: AAAAAABBBBCC. Donde A tiene una frecuencia de 6, B de 4 y C de 2. Cada caracter es representado usando una longitud fija de códigos de dos bits, entonces el número de bits requeridos para almacenar el archivo sería 24, esto es, (2 bits x 6) + (2 bits x 4) + (2 bits x 2) = 24 bits. Si esa información es comprimida usando compresión Huffman, el caracter más frecuente debería ser representado por la secuencia más corta como sigue:

• A por el código 0 (1 bit)
• B por el código 10 (2 bits)
• C por el código 11 (2 bits)

Por lo tanto el tamaño del archivo pasará a ser de 18,

(1 bit x 6) + (2 bits x 4) + (2 bits x 2) = 18 bits

O sea: 000000101010101111

En el ejemplo anterior, los caracteres que se repetían más frecuentemente son asignados al código más pequeño, resultando en un menor número de bits en el archivo final comprimido.

Una vez entendido el concepto, veamos cómo se construye. Como el diccionario de ¡Exception! se detiene aquí y no todo es copy/paste por más que se rumoreé, enriquezco el contenido con mi aportación personal: un esquema gráfico del proceso.

Si ya estáis deseando ver su implementación aquí os dejo unos enlaces a una codificación C++, huffman.hpp y huffman.cpp

Por si mis explicaciones no resultasen suficientemente aclaratorias disponéis de estas diapositivas un poco más elaboradas de todo el proceso: