Teoría de la Información: Entropía

Huffman

Este post concluye una serie de 5 pequeños artículos sobre Teoría de la Información.

Se trata de dar un breve repaso a esta rama de las matemáticas mediante un ejemplo aplicado.

Los cinco artículos han sido: Búsqueda Binaria, Búsqueda Jerárquica, Shannon-Fano, Huffman y Entropía.

Veamos hoy las aplicaciones prácticas de todo esto.

De las preguntas a a los bits

La información digital se almacena en forma de largas cadenas de 0’s y 1’s. La idea es ponerse de acuerdo en que significa una cadena determinada mediante un diccionario. Por ejemplo, usando el diccionario ASCII podemos escribir la palabra “HOLA” como: 01001000010011110100110001000001

Hay muchos tipos de diccionarios y, en general, lo que más nos interesa es usar un diccionario que traduzca la información de manera que la ristra de 0’s y 1’s sea lo más corta posible.

Los programas de compresión de datos suelen definirse un diccionario a medida de manera que la información que queremos comprimir ocupe lo mínimo posible sin que se pierda ningún dato por el camino. En algunos casos (como en el JPG o el MP3) también se permiten ciertas pérdidas siempre que estas sean imperceptibles.

Una manera inteligente y práctica de usar el método de Huffman consiste en traducir las preguntas en 1’s y 0’s de manera que cada pregunta será un bit, cada Si será un 1 y cada No será un 0.

Así, siguiendo el ejemplo del post anterior crearíamos el siguiente diccionario:

A = 11
B = 10
C = 011
D = 010
E = 001
F = 0001
G = 00001
H = 00000

Como veis el número de preguntas es igual al número de bits y en ese sentido es equivalente hablar de preguntas y hablar de codificar textos.

Además, este diccionario (y en general todos los que se crean a partir de un árbol de preguntas de Huffman) tiene una propiedad muy deseable: es un código prefijo y eso significa que ninguna ristra de 0’s y 1’s es prefijo de ninguna otra de manera que para codificar la palabra ABC tan sólo tenemos que concatenar sus respectivos códigos: ABC = 1110011 y cualquiera que tenga el diccionario podrá decodificarlo sin ninguna ambigüedad.

Entropía = Cantidad de información

Si recordáis el caso equiprobable os daréis cuenta de que allí lo mejor que podíamos hacer era la Búsqueda Binária y ello representa 3 preguntas de media. Por el contrario, con una distribución menos simétrica y usando códigos de Huffman podemos realizar la misma tarea con tan sólo 2,54 preguntas de media. Parece razonable buscar una medida que nos indique cuantas preguntas se necesitan (de media) para codificar algo

Claude Shannon (el mismo Claude Shannon de los códigos Shannon-Fano) definió en su prodigioso artículo A Mathematical Theory of Information el concepto que estamos buscando. Y lo llamó Entropía.

Shannon determinó que la cantidad de información (medida en bits) necesaria para codificar un dato era de: log(1/p) donde p es la probabilidad de que aparezca ese dato y log es el logaritmo en base 2.

Si queremos saber la cantidad de bits que necesitaremos (de media) para codificar un elemento del conjunto tan sólo tenemos que multiplicar la información necesaria para codificar cada elemento por la probabilidad de que ese elemento aparezca. Entropía

Algunas ideas obre Entropía

La entropía es una cota inferior para cualquier codificación. O dicho de otro modo, necesitas al menos esa cantidad de bits para codificar ese conjunto de opciones. Con menos bits perderás información.

En el ejemplo que venimos analizando la entropía es de 2,482608152 bits mientras que Huffman (que es lo mejor que se puede hacer) nos da unos 2,54 bits de media. Eso significa que Huffman, a pesar de ser óptimo, no siempre iguala la cota inferior de la Entropía.

Cuanto más asimétrica es la distribución de probabilidades menos bits se necesitan. Esto es así porque el conjunto es, en cierto sentido, predecible y podemos aprovechar eso para codificarlo (hacer las preguntas) de manera inteligente y ahorrar espacio.

En el caso equiprobable la mejor solución es la búsqueda binaria. Si todos las opciones son equiprobables resulta que la entropía es exactamente igual a: log(n) donde n es el número de elementos.

En nuestro ejemplo equiprobable, tenemos 8 elementos y el logaritmo en base 2 de 8 es 3 de manera que se necesitan, como mínimo, 3 preguntas de media para determinar un elemento. Como la búsqueda binaria iguala la cota de la Entropía no es necesario que busquemos nada mejor, ya es lo mejor que podemos hacer. Cabe destacar que Huffman, en el caso equiprobable produce la misma codificación que la búsqueda binaria.

En resumen: Cuanto más homogénea sea la distribución de probabilidades mayor será la Entropía y No podemos encontrar ningún método que codifique información con menos bits de los que marca la Entropía.

Escrito en 12/12/08 09:07 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

He llegado hasta aquí
y me he maravillado
qué forma más didáctica de explicarlo

Para mí ha sido un EUREKA inicial.
Gracias

juan-crisos | 26/12/08 19:20 | #
Gravatar.com se ha roto

Caray, está excelentemente redactado. Hasta un completo principiante en la materia podría comprender este texto sin mayor dificultad. ¡Felicitaciones!

Carlos Solís | 15/06/09 04:31 | #
Gravatar.com se ha roto

Te felicito!! Era un tema que no comprendía mucho, y del que me voy a tener que examinar en un par de meses, y está muy bien explicado!

EnDleSs_DaRk | 04/11/09 21:13 | #
Gravatar.com se ha roto

Excelente explicacion me ha quedado clarisimo todo…
ahora todo tiene una justificacion y no simplemente el que es asi y ya.

vangogan | 16/03/10 23:02 | #
Gravatar.com se ha roto

Muchísimas gracias por el artículo, me aclaró muchos conceptos y fue una buena referencia para un artículo acerca de la teoría de la información que escribí en un blog que participo. Saldrá el fin de semana, invitado a verlo y los demás en Bit Uchile

Iván | 06/05/11 15:22 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)