Regresando al blog después de un montón de tiempo....(siempre digo eso).
Conversando sobre esto, una persona me dijo que la compresión de datos era algo que ya no era tan relevante, porque las capacidades de almacenamiento disponibles para cualquiera eran más que suficiente: llaves USB de 16 gigabytes, iPods de 120 gigabytes, discos de 1 terabyte, ¡o más! Sin embargo, considero que la compresión de datos tiene importancia aún, especialmente para nuestra comunicación en línea, aumentando la eficiencia de nuestros equipos.
Estamos acostumbrados a hablar de información que ha sufrido procesos de Compresión con Pérdidas (en inglés: Lossy Compression): los archivos MP3, que se comprimen por medio de algoritmos que modelan la percepción de frecuencias sonoras del oído humano, o las imágenes JPEG que se reducen en tamaño por medio de degradaciones en la calidad o fidelidad de las mismas.
En cambio, la Compresión sin Pérdidas (en inglés: Lossless Compression) reduce el tamaño de la información sobre la que trabaja, sin tener pérdida de fidelidad o contenido. Para todos son muy conocidos los archivos .ZIP, o .RAR. En ellos se obtiene como resultado algo de menor tamaño, que puede ser reintegrado a su versión original conservando todo el contenido sin ninguna pérdida: ¡es casi como ir en contra de las leyes de la física!
Para comenzar a explorar el tema de compresión, vamos a analizar el algoritmo de Huffman, creado en los años 50, ya que ésta es una de las técnicas de Compresión sin Pérdidas que usualmente se discuten para introducir el tema, tanto por su relativa sencillez, pero brillante concepto, así como su falta de protección por patentes. La leyenda (en Wikipedia) dice que este algoritmo fue creado como la respuesta a una tarea de la universidad.
El algoritmo está basado en el concepto que los símbolos más frecuentes deberían estar codificados con menos bits que los menos frecuentes, logrando así una reducción en la cantidad de bits totales del mensaje o documento a comprimir. En el caso de textos en español por ejemplo, las letras a y e son más frecuente que la letra r, por lo que si le asignamos menos bits a esas letras que los 8 normales de un carácter ASCII, podríamos reducir el espacio requerido para almacenar el contenido.
La codificación Huffman entonces formaliza este concepto relacionando el número de bits asociados a un símbolo a la probabilidad de ocurrencia del mismo. En este artículo veremos la forma estática del algoritmo, que requiere tener una tabla de probabilidades calculada antes de comenzar a comprimir los datos. Esta tabla puede ser calculada en base a suposiciones iniciales (por ejemplo, una tabla de frecuencias de textos en español o inglés, dependiendo del lenguaje), o se puede generar directamente de los datos que se desean comprimir, recorriendo el contenido y haciendo un conteo simple de la ocurrencia de los símbolos.
Con esta información, el procedimiento de compresión puede comenzar a construir un árbol binario que codifica esta información de probabilidades, insertando nodos dentro del árbol, de forma de poner en las hojas más alejadas de la raíz, los símbolos menos probables. De esa manera, al completar este proceso de inserción, se tendrá un árbol con las hojas representando los símbolos, y nodos interiores que solamente sirven para diferenciar los niveles. El recorrido del árbol, etiquetando los arcos izquierdos con un 0 y los derechos con un 1, producen las palabras de código Huffman, con bits mínimos.
La Figura 1 ilustra este proceso. Como primera actividad, estamos generando el conteo de frecuencias del string de entrada “bcbbbbbbaacaabbcade” de 19 caracteres de largo. Esto ocuparía 19*8=152 bits de espacio para representarse normalmente en ASCII. Del conteo de caracteres, vemos que el más frecuente es el carácter b, luego el a, y así sucesivamente. Los menos frecuentes son los caracteres d y e.
Es posible ahora crear el árbol Huffman de la siguiente manera:
- Paso 1: Seleccione los dos símbolos con la menor probabilidad
- Paso 2: Cree un nuevo nodo como padre de los dos símbolos de menor probabilidad
- Paso 3: Asignar al nuevo nodo una probabilidad igual a la suma de sus hojas
- Paso 4: Repita el paso 1 hasta que ya solamente quede un nodo sin padre, el cual se agregará a la raíz
El código Huffman para cada símbolo se obtiene ahora caminando hacia cada uno de ellos, con los vértices izquierdos etiquetados con un 0, y los derechos con un 1. En este momento, ya se puede proceder a emitir los códigos leyendo cada símbolo, y produciendo el valor para cada uno de ellos. Es de notar que solamente hay códigos Huffman para las hojas del árbol. Los nodos interiores no contienen información.
En el ejemplo, el string original queda ahora conformado por los siguientes códigos (separados por guiones): “0-101-0-0-0-0-0-0-11-11-101-11-11-0-0-101-11-1001-1000” que suman en total 36 bits, equivalentes a una compresión de 36/152=23% del tamaño original.
El proceso de decompresión ocurre a la inversa: se lee el input un bit a la vez y se emite un símbolo recorriendo el árbol, al llegar a la hoja correspondiente.
Para lograr la implementación de este algoritmo, debe considerarse el anexar la tabla de frecuencias (o tenerla fija, ya precalculada) para lograr la decompresión, así como enviar el número de símbolos del input, para tener el parámetro de parada del algoritmo, ya que el decompresor no puede saber precisamente dónde termina la entrada.
Es posible también conseguir ejemplos de código en diversos lenguajes en Internet, y la Wikipedia tiene múltiples links al respecto.
Aún cuando no se vaya a implementar, es interesante conocer los detalles internos del funcionamiento de este tipo de algoritmo.
Una pregunta de análisis: ¿qué pasaría con el input, si por fallas en la transmisión un solo bit se enviara erróneo?
Referencias usadas:
Apiki, Steve. “Lossless Data Compression”. Byte, marzo 1991.
Música:
The Beatles Stereo Box Set, Is there anybody out there? The Wall Live
TV:
Glee, Fringe S2, American Family
