Teoría de la Información: Búsqueda Jerárquica

Búsqueda Jerárquica

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 el capítulo anterior…

En el capítulo anterior se nos planteó un problema: teníamos que encontrar la respuesta correcta entre 8 posibles opciones. Se nos permitía hacer preguntas que se pueden responder con un Si o un No.

Más Datos = Menos Preguntas

Si nos dan unos cuantos datos más sobre las posibles respuestas es posible mejorar sustancialmente el resultado obtenido anteriormente (3 preguntas de media). Imaginen por ejemplo que nos dicen que, en realidad, de las 8 opciones sólo dos son posibles, la A y la B. Entonces podríamos reducir el problema a preguntar: ¿Es la A? Y usaríamos así 1 pregunta de media para resolverlo.

Supongamos un caso más realista: 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%.

Este caso es mucho más frecuente que el anterior donde habíamos supuesto que todas eran equiprobables y por lo tanto todas aparecían con una probabilidad del 12,5% (= 1/8). Veamos si para este caso se nos ocurre algo que mejore las 3 preguntas de media.

Lo primero es lo primero

Lo primero que debería venirnos a la cabeza al ver unos datos así de asimétricos es que las letras más frecuentes deberían requerir menos preguntas que las menos frecuentes de manera que, de media, podamos reducir el número de preguntas.

Hay muchas maneras de hacer esto, pero una de las más sencillas es la Búsqueda Jerárquica. La Búsqueda Jerárquica consiste en preguntar una por una las diferentes opciones siguiendo el orden de mayor a menor probabilidad. Así, en un 35% de las ocasiones sólo haremos una pregunta: ¿Es A? – Si. Y en un 25% de las ocasiones haremos dos: ¿Es A? – No – ¿Es B? – Si.

Si nos ponemos a hacer cuentas la cosa queda así:

0,35×1 + 0,25×2 + 0,12×3 + 0,10×4 + 0,08×5 + 0,06×6 + 0,03×7 = 2,83

De manera que con este método, en este ejemplo, usamos 2,83 preguntas de media. No parece mucho, pero les aseguro que en cuestiones de Teoría de la Información una mejora de casi el 6% es más que significativa.

BOLAEXTRA: ¿Eso significa que hemos acabado ya? ¿Podemos darnos por satisfechos? Bien, no del todo, si las probabilidades de todas las posibles respuestas se parecen entre sí lo suficiente este método es bastante peor que el anterior (3,5 preguntas de media si todos los elementos tienen una probabilidad del 12,5%). Deberíamos buscar alguna idea que sea más flexible y adaptativa y que nos sirva para todos los caso. No se pierdan el próximo capítulo.

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

Comentarios

Gravatar.com se ha roto

Creo que estoy reviviendo todas las clases de “Transmisión de Datos” de la carrera :D

RinzeWind | 09/12/08 19:30 | #
Gravatar.com se ha roto

Sinceramente, espero que os explicaran algo más…

Carlos Luna | 09/12/08 21:54 | #
Gravatar.com se ha roto

¡¡ Me ha pasado exactamente lo mismo !!

Cambia el nombre del método por Codificación Huffman y el número medio de preguntas por la longitud media de bits enviados y obtienes uno de los mecanismos más eficientes para codificación de fuentes con probabilidades no balanceadas :)

Eisenreich | 09/12/08 22:19 | #
Gravatar.com se ha roto

@Eisenreich: Cambiaré los nombres cuando tú te leas los 5 post que hay publicados. Incluyendo el que habla de Huffman y el que explica que hacer preguntas es como codificar con bits.

Carlos Luna | 09/12/08 22:35 | #
Gravatar.com se ha roto

Corríjome. Se parece a Huffman pero no es exactamente igual.

De hecho, acabo de ver que tienes otro link explicando en qué consiste Huffman. ¡Waw. Recomendaré a los alumnos de TD que se pasen por aquí! ;)

Eisenreich | 09/12/08 22:37 | #
Gravatar.com se ha roto

Hola, creo que hay un error en la fórmula:

0,35×1 + 0,25×3 + 0,12×3 + 0,10×4 + 0,08×5 + 0,06×6 + 0,03×7 = 2,83

El segundo término (0,25) debería estar multiplicado por 2, y no por 3.

(¡Espero no haber metido la pata!)

Mario | 16/06/09 12:00 | #
Gravatar.com se ha roto

@Mario: Efectivamente, estaba mal. Muchas gracias por avisar!

Carlos Luna | 16/06/09 14:02 | #

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