Buscando en el Pajar

Buscar en WWW puede ser más difícil que encontrar una aguja en un pajar

En esta columna continuamos hablando de la telaraña mundial de computadores o WWW. El mes pasado la caracterizamos, ahora hablaremos de como se puede buscar en ella. Hay varias formas, ninguna de ellas resuelve todos los problemas.

¿Cómo Buscar?

Hay dos maneras más usadas para buscar. Podemos usar catálogos similares a páginas amarillas telefónicas como Yahoo!. Estos catálogos son taxonomías jerárquicas que intentan clasificar los distintos temas o áreas del conocimiento. La ventaja principal de este método es que si encontramos algo, seguramente será útil. Las desventajas son que la clasificación muchas veces no es suficientemente especializada y no todo lo que existe en la WWW está clasificado. De hecho, la WWW crece más rápido que cualquier catálogo. Los esfuerzos para realizar esto en forma automática datan de los comienzos de la inteligencia artificial. Sin embargo hasta hoy, el procesamiento de lenguaje natural para extraer términos relevantes de un documento no es 100% efectivo. En el párrafo subsiguiente quedará claro la dificultad del problema.

La segunda técnica es usar una máquina de búsqueda (search engine) como Altavista, Lycos o Infoseek, que usan el paradigma de recuperación en texto completo. Es decir, todas las palabras de un documento se almacenan en un índice para su posterior recuperación. Más adelante hablaremos de los desafíos técnicos para crear este índice. Un problema adicional es que el recorrer la WWW actualizando y agregando nuevas páginas, es una tarea que no termina nunca y que además tampoco puede copar con el crecimiento de WWW. Aunque las búsquedas en estas máquinas son efectivas en muchos casos, en otros son un total desastre. El problema es que las palabras no capturan toda la semántica de un documento. Hay mucha información contextual o implícita que no está escrita, pero que entendemos cuando leemos.

El siguiente ejemplo es iluminador. Supongamos que queremos encontrar a qué velocidad corre un jaguar buscando las siguientes palabras: jaguar speed (queramos o no, el lenguaje más usado en WWW es inglés y tal vez tengamos que convertir millas por hora a kilómetros por hora). El resultado en Altavista es un montón de páginas acerca del auto Jaguar, un juego de video para Atari, un equipo de fútbol americano, un servidor de redes locales, etc. ¡La primera página acerca del animal está en el lugar 183 y es una fábula! Si intentamos eliminar los documentos acerca del modelo de auto, igual encontraremos páginas acerca de él que no mencionan ni car, ni auto. Tratemos jaguar speed +cat, que indica que la palabra cat (felino) debe estar en el documento. Los dos primeros resultados son acerca de los clanes Nova Cat and Smoke Jaguar, luego, la empresa LMG, seguido de automóviles finos. La número 25 es la primera con información de jaguares, pero no tiene lo que necesitamos. Si miramos en Yahoo!, podemos buscar en Science:Biology:Zoology:Animals:Cats:Wild_Cats y en Science:Biology:Animal_Behavior, pero en ninguno encontramos una página acerca de jaguares.

Es decir, las máquinas de búsqueda todavía devuelven demasiada paja para poder encontrar la aguja mientras los catálogos no tienen la profundidad y volumen suficiente para clasificar la aguja. El problema de ordenar documentos en base a palabras como hace Altavista no se puede resolver bien con tan poca información (dos palabras) y adolece de la misma dificultad intrínseca de la clasificación automática. Más efectivo sería tratar de realizar búsquedas por temas, como trata LiveTopics, pero también aquí tenemos el problema de la poca amplitud de temas (buscando jaguar sólo se obtienen autos o equipos de fútbol). Búsquedas en Yahoo! debieran entregar caminos en la jerarquía para asegurarnos que estamos recuperando del tema de nuestro interés. Moraleja: si quiere algo específico, mire una enciclopedia. Por otro lado, si no sabe exactamente lo que quiere, use una máquina de búsqueda. O si está interesado en un tema amplio, vaya a Yahoo!.

Indizando la WWW

Queda claro que para extender Yahoo! se necesitan expertos que clasifiquen nuevas páginas que en general son enviadas por los propios interesados. Por otra parte, indexar toda la WWW implica el uso de programas que la recorren (robots o wanderers) y recopilan nuevas páginas. A continuación hablamos de cómo crear un índice de toda la WWW.

Nadie conoce el volumen exacto de WWW. Estimemos por debajo la cantidad de texto. Si cada página tiene 6Kb (ver columna anterior) y hay unas 400 páginas por servidor, tenemos 2.5Mb. Considerando que hay 650 mil servidores, tenemos al menos 1600Gb de texto. Esta es una estimación conservadora y por supuesto el volumen total es mayor. Indices como Altavista mantienen todas las palabras distintas ordenadas y para cada palabra la lista de páginas WWW donde aparecen. Esta estructura de datos se llama archivo invertido.

El número de palabras distintas no crece en forma proporcional al texto, sino que crece en forma sublineal. Esto se debe a que el vocabulario es finito. Por otra parte, la frecuencia de las palabras sigue una variante de la Ley de Zipf. Esta ley experimental indica que la j-ésima palabra más frecuente ocurre una cantidad de veces proporcional al inverso de j. Actualmente esta distribución es más sesgada y se aproxima más al inverso del cuadrado de j. Es decir, hay un conjunto pequeño de palabras muy frecuentes y muchas que ocurren muy pocas veces o sólo una vez (sea cual sea el lenguaje usado).

Usando distintas técnicas, el tamaño de este índice puede reducirse a un 5% del tamaño del texto, es decir al menos unos 16Gb (en la realidad es mucho más). Estos índices se pueden reducir usando particiones lógicas en vez de documentos (por ejemplo, poniendo muchas páginas pequeñas en un mismo grupo). Usando búsqueda binaria en las palabras ordenadas, podemos encontrar todos los documentos en que aparece en menos de un segundo. Dependiendo del sistema de búsqueda, estos documentos serán ordenados usando distintos criterios y heurísticas, con el objeto de indicar al usuario cuál es el documento más relevante (esto funciona muchas veces, pero otras no). Otro problema debido al volumen de datos es que la cantidad de documentos resultantes es del orden de miles, por lo cual es necesario usar paradigmas visuales para poder manipularlos.

En la práctica el tamaño de la WWW es mayor. Por ejemplo, el índice de Altavista tiene casi 200Gb. Esto indicaría un volumen de 4 Terabytes de texto. Para atender las consultas se usan 16 servidores Alpha, cada uno con varios procesadores y 8Gb de memoria RAM (sí, leyó bien, 8Gb). Por lo tanto, gran parte del índice y muchas de las respuestas están almacenadas ya en RAM (para poder rápidamente retornar la siguientes 20 páginas de una consulta). Claramente este esquema tiene un límite si la WWW sigue creciendo como hasta ahora y el final de los buscadores existentes hoy en día podría ocurrir en el futuro cercano.


Si tiene preguntas o sugerencias, envíe e-mail a rbaeza@dcc.uchile.cl