¿Qué estructura tiene el World
Wide Web (II)?

Por Ricardo Baeza (http://www.dcc.uchile.cl/~rbaeza/). Año 2000

Revisión: Jose Manuel Morales . Año 2002 - Leunam Gestión

¿Cómo Buscar en la Web?



Hay dos formas de buscar. Podemos usar catálogos similares a las 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. Los directorios más grandes tienen más de 100
mil categorías jerarquizadas y cerca de dos millones de sitios Web clasificados.




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 Web
está clasificado. De hecho, la Web crece más rápido que
cualquier catálogo. Los esfuerzos para realizar esto de forma automática
datan de los comienzos de la inteligencia artificial en los años 60.
Sin embargo, hasta hoy el procesamiento de lenguaje natural para extraer términos
relevantes de un documento no es 100% efectivo.

La segunda técnica es usar una máquina de búsqueda (search
engine) como AltaVista, Fast, Inktomi, Northern Light, Lycos o Google, 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.
Un problema adicional es que el recorrer la Web actualizando y agregando nuevas
páginas, es una tarea que no termina nunca y que además tampoco
puede mantenerse vigente con el crecimiento continuo de la Web.



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.
Los problemas principales son la polisemia, es decir, palabras que tienen
más de un significado, y por lo tanto encontramos páginas que
no queremos; y la sinonimia, palabras distintas que tienen el mismo significado
y por ende si no usamos la palabra correcta, no encontramos lo que queremos.

Las máquinas de búsqueda todavía devuelven demasiada basura
para poder encontrar la aguja mientras los catálogos no tienen la profundidad
y volumen suficiente para clasificarla. 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. Sería más efectivo tratar de realizar búsquedas
por temas, 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
y no el animal).



Moraleja: si quiere algo específico, mire una enciclopedia, para eso
se crearon. Por otro lado, si no sabe exactamente lo que quiere, use una
máquina de búsqueda y vaya modificando su consulta de acuerdo
a los documentos que recupere y sean relevantes. O si está interesado
en un tema amplio, vaya a los directorios. Allí encontrará buenos
lugares donde comenzar a navegar.

Aunque, actualmente no es posible distinguir los buscadores de los directorios,
porque los primeros han agregado jerarquías y los segundos permiten búsquedas
en toda la Web usando el servicio de algún buscador.



Indexando la Web



Queda claro que para extender un directorio como Yahoo! se necesitan expertos
que clasifiquen nuevas páginas que en general son informadas por los
propios interesados. Por otra parte, indexar toda la Web implica el uso de programas
llamados crawler, robot, wanderer, etc. que recorren la Web y recopilan páginas
nuevas o actualizadas. La arquitectura típica de un buscador (ver figura
siguiente) incluye el indexador y el robot. A continuación hablamos de
cómo crear un índice de toda la Web.

Nadie conoce el volumen actual de la Web. Tratemos de subestimar la cantidad
de texto existente en la Web. Si cada página tiene 5Kb y hay como 4000
millones de páginas, estamos hablando de más de 20 Tb de texto
solamente. 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 Web 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 (crece como nx con 0<x<1). Esto se debe
a que el vocabulario es finito y entonces muchas palabras se repiten. Por otra
parte, la frecuencia de las palabras sigue una variante de la Ley de Zipf que
caracteriza la ocurrencia de palabras en el texto.



Esta ley experimental indica que la j-ésima palabra más frecuente
aparece 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 aparecen muy pocas veces o sólo una vez (sea
cual sea el idioma usado).

Usando distintas técnicas, el tamaño de un archivo invertido
puede reducirse a un 20% del tamaño del texto. 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).



Con una búsqueda eficiente 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. Por ejemplo, el índice de AltaVista, que es uno de
los más grandes, registra sobre 1000 millones de páginas Web,
y para atender las consultas se usan decenas de servidores Alpha, cada uno con
varios procesadores y varios Gb de memoria RAM .



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). Los otros buscadores con un número
similar de páginas son Fast e Inktomi. Este esquema centralizado tiene
un límite si la Web sigue creciendo como hasta ahora y el final de los
buscadores existentes hoy en día podría ocurrir en un futuro cercano.

Un problema técnico importante es como jerarquizar las páginas.
La mayoría de los buscadores usan las ocurrencias de las palabras que
estamos buscando, pero esto muchas veces no funciona. Nuevas técnicas
incluyen información de los enlaces, lo que es muy efectivo. Un buscador
que usa esta idea es Google.



Otro peligro es que los buscadores de Internet estén jerarquizando las
respuestas en base a razones económicas y no de contenido. Y esto esta
dándose cada dia más. Pero esto es tema para otro artículo
algo mas peliagudo.

_________________________

Sobre el Autor: Ricardo Baeza

Ricardo Baeza Yates es profesor titular del Departamento de Ciencias de la Computación
de la Escuela de Ingeniería (Facultad de Ciencias Físicas y Matemáticas)
de la Universidad de Chile. Sus áreas de investigación incluyen
algoritmos y estructuras de datos, recuperación de información,
bases de datos de texto e imágenes, visualización de software
y bases de datos, e interfaces gráficas.