Teoría de la Información: Huffman

Huffman

Este post forma parte de 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 son: Búsqueda Binaria, Búsqueda Jerárquica, Shannon-Fano, Huffman y Entropía. Pueden leerlos ya o esperar a que se vayan publicando diariamente durante esta semana.

En los capítulos anteriores…

Ante el problema de adivinar la letra correcta de entre 8 posibles opciones con el mínimo número de preguntas del tipo Si o No hemos estado repasando diferentes métodos cada vez más sofisitcados: Búsqueda Binaria, Búsqueda Jerárquica y Método de Shannon-Fano. El último, además, era adaptativo de manera que podía aprovechar el hecho de que no todas las opciones tienen la misma probabilidad: la A tiene una probabilidad del 35%, la B del 25%, la C del 12%, la D del 10%, la E del 8%, la F del 6%, la G del 3% y finalmente la H tiene una probabilidad del 1%.

Lamentablemente el que nos ha dado mejor resultado hasta ahora, el método de Shannon-Fano, era complicado de llevar a cabo con sencillez dado que requería resolver múltiples Problemas de la Mochila para elegir las preguntas correctas. En este capítulo veremos una solución ingeniosa al problema que llevamos tantos días intentando resolver.

Cuando tus alumnos te superan

David Huffman era alumno de Robert Fano (el mismo Robert Fano que creo el método de Shannon-Fano) y su profesor le propuso entregar un trabajo en vez de realizar el examen de la asignatura. El trabajo era, ni más ni menos, obtener el algoritmo óptimo para el problema que nos ocupa (en su versión más general) y ni Fano ni el mismísimo Shannon lo habían conseguido todavía (pese a ser dos pesos pesados de la Teoría de la Información).

Huffman sudó tinta buscando pero al final lo encontró: El método de Huffman.

El método de Huffman consiste en construir el árbol de preguntas de-abajo-a-arriba en vez de de-arriba-a-abajo como hemos intentado hasta ahora. Huffman se dio cuenta de que el árbol óptimo cumplía que sus dos elementos menos probables requerían el mismo número de preguntas para ser elegidos. A partir de ahí desarrolló un sencillo, rápido y elegante algoritmo que permite construir el árbol óptimo de preguntas.

En nuestro caso el árbol de preguntas queda como en la imagen superior y da un resultado de:

0,35*2 + 0,25*2 + 0,12*3 + 0,10*3 + 0,08*3 + 0,06*4 + 0,03*5 + 0,01*5 = 2,54

Es decir, con esta distribución de probabilidades y este método necesitamos 2,54 preguntas de media que es más de un 4% mejor que el anterior método.

Resumiendo

Huffman publicó un paper, Fano le puso una Matrícula de Honor y actualmente muchos métodos de compresión de datos (como el formato MP3) usan alguna variante del método de Huffman.

BOLAEXTRA: ¿Por qué no podemos hacerlo mejor? No se pierdan el último capítulo.

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

Comentarios

Gravatar.com se ha roto

Coooooooool!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!1

rf microwave components | 02/12/14 04:38 | #

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://...)