COMPUTACION	Desenredando la Madeja
	© Ricardo Baeza-Yates rbaeza@dcc.uchile.cl

RESUMEN [ABSTRACT]

En este artículo presentamos las características principales de la Web, incluyendo su tamaño, estructura e idiomas. Luego, a través de varios ejemplos, describimos las herramientas que existen actualmente para buscar en la Web y la tecnología que está detrás de ellas. El buen uso de la información que existe en la Web dependerá de si estas tecnologías pueden evolucionar tan rápido como crece la Web.

Introducción

¿Qué estructura tiene la telaraña mundial de computadores o World Wide Web? (Web de ahora en adelante, aunque no queda claro si es femenino o masculino) Nadie sabe. Crece más rápido que la capacidad de ella misma para detectar sus cambios. Sus conexiones son dinámicas y muchas de ellas quedan obsoletas sin ser nunca actualizadas. El contenido de la Web es hoy de varios terabytes (un terabyte o Tb son un billón de megabytes) de texto, imágenes, audio y video. Para aprovechar esta gran base de datos no estructurada, es importante poder buscar información en ella, adaptándose al crecimiento continuo de la Web.

Al igual que Internet, la red de computadores que interconecta el globo, que ya sobrepasó los 40 millones de computadores conectados en más de 200 países [8], los servidores de Web también crecen en forma exponencial desde 1993 (un servidor Web es el software que administra un sitio Web). Lamentablemente nadie sabe su número exacto, pues no es posible a partir de un nombre de dominio saber si es o no un servidor Web (la mayoría comienza con www, pero muchos lugares no siguen esta convención). Un dominio es una dirección de Internet, como por ejemplo dcc.uchile.cl. Además un mismo computador puede manejar distintos servidores y también existen servidores virtuales (un mismo servidor Web puede manejar lógicamente otros servidores, que entonces se denominan virtuales). Se estima que a fines de 1998 habían entre dos y tres millones de servidores Web [6,7].

Por otra parte nos gustaría distinguir servidores físicos de sitios Web (lógicos). Es decir, contar instituciones con servidores Web, ya que cada institución se puede considerar como una fuente de información distinta. En 1995, el número de sitios era el 30% de los servidores [4] y esa fracción debería haber aumentado si la tasa de crecimiento de nuevas instituciones es mayor que la tasa de crecimiento de nuevos servidores. En este artículo caracterizamos algunos aspectos de la Web, incluyendo su impacto en Iberoamérica y el castellano, concluyendo con las formas que existen para buscar en ella y cómo funcionan los buscadores de información en la Web.

Estructura y Visibilidad

¿Cuántas referencias tiene una página HTML? (HTML es un acrónimo para Hyper Text Markup Language, el lenguaje usado para estructurar páginas Web) Más del 75% de las páginas tiene al menos una referencia, y en promedio cada una tiene entre 5 y 15 referencias. La mayoría de estas referencias son a páginas en el mismo servidor. De hecho, la conectividad entre sitios distintos no es muy buena. En particular, la mayoría de las páginas no son referenciadas por nadie y las que sí son referenciadas, lo son por páginas en el mismo servidor.

Considerando sólo referencias externas (entre sitios distintos), más del 80% de las páginas tienen menos de 10 referencias a ella. Otros sitios son muy populares, teniendo decenas de miles de referencias a ellos (por ejemplo en 1995 los top-5 eran Univ. of Illinois at Urbana- Champaign, National Institute of Health, Mass. Inst. of Tech., NASA y Carnegie Mellon Univ. [4]). Si contamos sitios que referencian a sitios, aparecen Yahoo!, Microsoft y Netscape entre los 5 primeros. Por otro lado, hay algunos sitios que no son referenciados por nadie (están porque fueron incluidos mediante el envío directo de una dirección Web a Yahoo u otros buscadores, pero que realmente son islas dentro de la Web). En este mismo sentido, las páginas personales también se pueden considerar como entes aislados en la mayoría de los casos. Asi mismo, la mayoría de los sitios (80%) no tiene ninguna referencia hacia páginas en otros servidores. Esto significa que una minoría de los servidores mantiene toda la carga navegacional de la red. En particular hay sitios que tienen miles de punteros externos que son los que al final engloban la Web, siendo obviamente el mayor de todos ellos Yahoo!. Estadísticas recientes indican que el 1% de los servidores contienen aproximadamente el 50% del volumen de datos de la Web, que se estima es de alrededor de 320 millones de páginas a mediados de 1998 [3]. El siguiente gráfico muestra el crecimiento aproximado en el último tiempo del número de servidores y páginas Web.

Tamaños y características

¿Cómo es una página Web promedio? Una página de texto promedio tiene alrededor de 5 kilobytes (poco menos de mil palabras). Si agregamos audio o video, este promedio aumenta. De hecho la distribución de tamaños se dice que es de ``cola pesada'', como por ejemplo la distribución de Pareto (ver figura siguiente). En otras palabras, aunque la mayoría de los archivos son pequeños, existe un número no despreciable de archivos grandes; y hasta 50 kilobytes predomina el volumen de las imágenes. Desde allí hasta 300 kilobytes son importantes los archivos de audio. Más alla de este límite, llegando a varias decenas de megabytes, tenemos archivos de video. Los formatos más populares (en base a la extensión del nombre de archivo) son HTML, GIF, TXT, PS y JPG, en ese orden.

¿Cómo es una página HTML? Alrededor de la mitad de ellas no tiene ninguna imagen. Un 30% no tiene más de dos imágenes y su tamaño promedio es de 14Kb. Por otra parte hay un porcentaje no despreciable (mayor al 10%) de páginas con más de 10 imágenes. La razón es que son imágenes tipográficas, como por ejemplo puntos rojos, líneas de separación de color, etc. La mayoría de las páginas usan HTML simple. Sólo un porcentaje pequeño siguen todas las normas y otro porcentaje mayor (alrededor del 10%) son sólo texto. Finalmente, la calidad del texto deja mucho que desear, pues hay errores de tipeo, errores que viene de la conversión de imágenes de documentos a texto, etc. Más aún, la información contenida puede estar obsoleta, puede ser falsa o engañosa. Hay que tener esto en mente cuando usamos una página Web como fuente de información.

Los Idiomas en la Web

Existen sólo tres estudios de los distintos idiomas usados en páginas Web. Uno es de Funredes, una organización no gubernamental establecida en República Dominicana y dirigida por Daniel Pimienta, un francés. Este estudio está hecho en base a frecuencia de palabras en AltaVista y sus últimos datos son de Septiembre de 1998. El segundo estudio pertenece a Alis Technologies, una compañía francesa, que hizo un muestreo de 8000 servidores, usando un producto propio que reconoce distintos idiomas. Uno de los objetivos de esta investigación fue validar esta herramienta y data de abril de 1997. En ambos casos, el estudio se centra en el uso del francés. El tercer estudio pertenece a [10] y estima el número de servidores Web en cada idioma y fue hecho muestreando el 0.1% de las direcciones de Internet en Junio de 1998. La siguiente tabla muestra los resultados más importantes, incluyendo cuántas personas hablan cada idioma. Actualmente, existen páginas Web en más de 100 idiomas distintos.

Idioma	Funredes	Alis Tech.	OCLC	Parlantes
	(%)	(%)	(%)	(millones)
Inglés	76.4	82.3	71	450
Japonés	4.8	1.6	4	126
Alemán	4.4	4.0	7	118
Francés	2.9	1.5	3	122
Castellano	2.6	1.1	3	266
Italiano	1.5	0.8	1	63
Portugués	0.8	0.7	2	175

De acuerdo a esto, el castellano es la quinta lengua más usada en la Web, pero debería estar mejor ubicada de acuerdo al numero de personas que la hablan (aunque en la tabla no aparecen ni el chino ni otros idiomas más hablados cuyos porcentajes son aún menores). Estos datos son aproximados, pues ninguna metodología es exacta y hay muchas páginas multilingües. Otro dato interesante es que no todas las páginas usan ASCII extendido (acentos, etc), y el porcentaje de páginas correctamente escritas es 80% en francés y sólo 50% en castellano. De acuerdo al estudio de Funredes, desde 1996 a la fecha la razón francés/castellano ha pasado de 2.4 a 1.1, por lo que en el año 2000 el castellano debiera ocupar ya el cuarto lugar.

¿Cómo Buscar?

Son dos las maneras más usadas para 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. 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, 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 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.

El siguiente ejemplo ilustra los problemas de buscar en la Web. Supongamos que queremos encontrar a qué velocidad corre un jaguar buscando las siguientes palabras: jaguar speed (queramos o no, el idioma más usado en la Web 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 tampoco 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 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). 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, 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 Yahoo!. Allí encontrará buenos lugares donde comenzar a navegar.

Recursos en Castellano

Si queremos buscar información en castellano, hay varias alternativas. La más simple es usar un buscador estándar, por ejemplo Altavista (que actualmente es el de mayor cobertura) y usar palabras en castellano (que no existan en otro idioma). Algunos buscadores también permiten especificar el idioma o el área geográfica. También Yahoo! tiene ahora un directorio en castellano de datos en esta lengua, con páginas específicas de 6 países, entre ellas Chile y España.

Por otra parte, hay otros buscadores especializados. Por ejemplo, en España hay más de 35 de ellos, tales como Elcano, Lycos España, Ole, etc. Una dirección útil está en Inglaterra. En Chile un buen directorio es La Brújula.

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 subestimemos la cantidad de texto existente en la Web. Si cada página tiene 5Kb y hay como 300 millones de páginas, estamos hablando de más de 1.5 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. 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 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). Estas distribuciones se presentan a continuación, donde V representa el tamaño del vocabulario y F la distribución de probabilidad de las palabras, ordenadas de la más frecuente a la menos frecuente.

Usando distintas técnicas, el tamaño de un archivo invertido puede reducirse a un 20% del tamaño del texto, es decir al menos unos 300 mil megabytes, pero en 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 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 el más grande y registra sobre 100 millones de páginas Web, tiene más de 200Gb. 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). Los restantes buscadores en orden de cobertura son Hotbot, NorthernLight y Excite. Este esquema 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.

Resultados recientes demuestran que el número de páginas que están en los buscadores más grandes es menor al 2% [3] y en general se encuentran páginas distintas en cada uno de ellos. Por lo tanto, un buen metabuscador (buscador que busca en muchos buscadores) puede ser muy efectivo si sabe combinar y clasificar bien las respuestas. Otras ideas recientes incluyen agentes de software especializados o metabuscadores en temas específicos, por ejemplo Search Broker o Meta Miner.

Epílogo

La Web es un gran repositorio de datos y un nuevo medio de publicación al alcance de más de 50 millones de personas. El hacer uso eficiente y adecuado de estos datos depende de nosotros y de las herramientas que existen y que han sido descritas en este artículo. El futuro dirá si es posible adaptar estas herramientas al crecimiento explosivo de la Web y que además la Web misma no colapse debido a la congestión en las redes y servidores Web. Para mayor información en este tema, ver el capítulo 13 de Modern Information Retrieval [2].

Agradecimientos

Agradezco los comentarios de Tania Bedrax, Helena Fernández y un revisor anónimo.

Referencias

[1] Marc Abrams (editor), World Wide Web: Beyond the Basics, Prentice Hall, 1998.

[2] Ricardo Baeza-Yates y Berthier Ribeiro-Neto, Modern Information Retrieval (Capítulo 13: Searching the Web), Addison-Wesley-Longman, Wokingham, Inglaterra, Marzo 1999.

[3] K. Bharat y A.Z. Broder, A Technique to measuring the relative size and overlap of public Web search engines, 7th WWW Conference, Brisbane, Australia, 379-388.

[4] Tim Bray, Measuring the Web, Fifth International World Wide Web Conference, Paris, Mayo 1996.

[5] Martin Dodge, The Geography of Cyberspace Directory: Main Page, 1997.

[6] Netcraft Web Server Survey, 1998.

[7] NetSizer: Main Page, 1998.

[8] Network Wizards, Internet Domain Survey, 1998.

[9] Greg Notess, Search Engines Showdown: Main Page, 1998.

[10] OCLC, Study of Web Characteristics, 1998.

[11] Scientific American, Número especial dedicado a Internet, Marzo de 1997.

[12] Danny Sullivan, Search Engine Watch: Main Page, 1997.