CSI X: cuando la cosas ocupan menos

Recuerdo perfectamente una de las primeras clases de informática, allá en primero. Bueno, no, eso sería casi un milagro habida cuenta que no recuerdo qué comí ayer... Pero sí que recuerdo una frase pronunciada por un profesor, a modo de jocosa obviedad. "Dicen que 'el saber no ocupa lugar'... ¡No pollas!".

Y es que el saber, cualquier tipo de información, SÍ ocupa lugar. Y sea del tipo que sea, ese lugar tiene un coste o precio. El cerebro también tiene un coste, por más que algunos se empeñen en destrozarlo a base de etanol o mítines. Por ello siempre que podamos comprimir los datos, información o saber (y el coste de la compresión no supere al de sus beneficios, claro está) nos interesará hacerlo. De este modo saldremos ganando espacio. Pero... ¿pueden ocupar las cosas menos lugar de lo que ocupan?. ¿Cómo se realiza este milagro?

Pues eso, en Cosas que Sí se dan en Informática, hablaremos de compresión.

Utilizaremos a modo de ejemplo las letras. Supongamos que queremos comprimir un fichero de texto que tan sólo contiene caracteres de nuestro alfabeto (unos 25 caracteres), por simplificar. Sabido es que en Informática los computadores sólo entienden de unos y ceros (bits). Bien, normalmente se emplean 8 bits para codificar caracteres (codificación ASCII extendida). Con 8 unos y ceros podemos codificar 256 (2⁸) 'letras' distintas... pero si ya sabemos que nuestro fichero tiene tan sólo 25 letras distintas... ¿para qué queremos tantas?. Quitemos bits.

Para codificar 25 caracteres distintos necesitamos al menos 5 bits, ya que 2⁵ es 32. Por tanto, un fichero con 10 caracteres ocuparía 50 bits. Pero imaginemos que, de estos 10 caracteres, 4 son 'a's. ¿Ya que hay más 'a's, no ganaríamos espacio si codificamos las 'a's con unos pocos menos bits que el resto?.

Esa es la idea base de la codificación Huffman, desarrollada por el señor del mismo nombre en 1951. Aunque variantes de la misma codificación son más eficientes en determinadas circunstancias, Huffman encontró la forma óptima de mapear cualquier símbolo de una alfabeto con una secuencia de bits de longitud óptima. La idea es tan sencilla y elegante que bien merece la pena explicarla.

Partimos de una alfabeto y una cadena de letras. Supongamos que nuestra cadena es 'aavnvavfja'. Conociendo la cadena, podemos asociar a cada símbolo de nuestro alfabeto una cuenta de apariciones. Esto se llama histograma. Por tanto, tenemos que a --> 4, v --> 3, n --> 1, f --> 1, j --> 1. El resto de símbolos son ceros. Bien, pues ahora vamos a construir un arbol binario. Árbol porque es un árbol al revés. Binario, porque cada rama se separa en 2 ramas. Cogeremos los dos símbolos con menor número de apariciones y los agruparemos, sumando sus apariciones: 'fj' --> 2. Y volvemos a operar del mismo modo... y otra vez y otra... ¡hasta que la raíz del árbol agrupa todos los símbolos! (ver imagen).

Y ya está. Porque si asignamos un bit a cada rama del árbol, '0' para la izquierda '1' para la derecha, podemos obtener el código para cada símbolo sin más que andarnos por las ramas encadenando estos bits hasta llegar al carácter que deseamos codificar. Codifiquemos, pues, nuestra cadena 'aavnvavfja'.
001011010010111011110
Hemos utilizado 21 bits. De codificar cada símbolo con 8 bits habríamos gastado 80. 50 si sólo codificáramos con 5 (alfabeto de 25 letras). Y 30 si codificáramos cada símbolo de este alfabeto en particular {a, v, n, f, j} con 3 bits.

¿Está ya nuestra cadena comprimida?. Pues no. Porque además de comprimirla, queremos enviarla por correo, que le llegue a un amigo y que éste, sin tener ni idea de cual era la cadena original, poder descomprimirla y leerla. Para eso es necesario que nuestro amigo conozca, bien la tabla de códigos que hemos creado, bien el histograma de apariciones de la cadena original. Aunque el histograma puede ser muy grande si el alfabeto lo es, su tamaño será despreciable cuando consideremos cadenas de miles y miles de bits.
Con el histograma nuestro amigo (o el descompresor de nuestro amigo) puede construir el mismo árbol que hemos creado y decodificar la cadena. Para ello sólo tiene que 'andarse por las ramas' con los símbolos que le han llegado.

El primero es un 0. Se anda por la rama izquierda y llega a la 'a'. Ya tiene un símbolo. Otro 0: se anda por las ramas y consigue otra 'a'. Ahora un 1: rama derecha. 0, rama izquierda: ha encontrado una 'v'... y así hasta completar la cadena entera.

Y ya está: una cadena que tendría 8 bits por símbolo de codificarse ASCII se comprimiría hasta 2.1 bits por símbolo (21 bits, 10 símbolos). Bueno, no está, porque este tema tiene mucha tela por cortar. ¿Sabéis que se puede calcular el mínimo de bits por símbolo necesarios para representar una cadena?. Lo hizo Claude Shannon, padre de la teoría de a información, antes de que Huffman inventara este método. El mínimo número de bits con el que se puede codificar una cadena viene definido por la entropía de primer orden.

En nuestro caso, H = 2.046439. Así que nuestra codificación Huffman no está nada mal. Hay mejores codificadores que los de Huffman, ojo. Por ejemplo los codificadores aritméticos. Sin embargo, Huffman se sigue gastando mucho... más que nada porque estos últimos (que tampoco son tan complicados de entender) están sujetos a patentes por parte de compañías poderosas. Lo de las patentes de software también tiene tela. Porque en muchos casos es algo tan absurdo como patentar la forma de darle la vuelta a una tortilla. Y nadie que quiera dar la vuelta a una tortilla lo podrá hacer de ese modo (aunque se le ocurra a él sólo) sin arriesgarse a ser demandado.

Con Huffman, la secuencia que obtenemos tras la descompresión es idéntica a la original. Se llama compresión sin pérdidas. Pero en muchos casos podemos tolerar cierto grado de pérdidas, esto es, de calidad. Por ejemplo, el oído humano enmascara ciertas frecuencias por debajo de otras, de manera que al ir seguidas, no percibimos algunas de ellas. ¿Por qué almacenar esa información, pues?. Con esa idea funciona MP3. O, en dos fotogramas seguidos el fondo de la imagen apenas cambia, ya que el protagonista sólo mueve el pie... ¿por qué almacenar dos veces el mismo fondo estático?... con esa (y otras muchas) idea funcionan los compresores de vídeo.

A la compresión que se aprovecha de cómo percibimos nosotros la información se le llama compresión basada en la fuente. Suele tener pérdidas, pero son aceptables, y obtenemos cotas altísimas de compresión. Pero de ellas ya hablaremos otro día...

Apuntes de clase: ¡esto es básico!

Posts relacionados

Codificación de datos