implementacion de un motor de b´ usqueda´ para el … · teor´ıa de c´omo esta compuesto y...
TRANSCRIPT
UNIVERSIDAD DE MAGALLANES
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA
EN COMPUTACION
IMPLEMENTACION DE UN MOTOR DE BUSQUEDA
PARA EL DOMINIO UMAG.CL
Bozydaj Andres Biskupovic Trujillo
2008
La presente Memoria de Titulacion ha sido aprobada con la siguiente
calificacion:
Bozydaj Andres Biskupovic Trujillo
Memoria :
Examen de Tıtulo :
Nota Final :
Dra. Patricia Maldonado Cardenas
Directora Departamento
De Ingenierıa En Computacion
30 de abril de 2008
2
UNIVERSIDAD DE MAGALLANES
FACULTAD DE INGENIERIA
DEPARTAMENTO DE INGENIERIA
EN COMPUTACION
IMPLEMENTACION DE UN MOTOR DE BUSQUEDA
PARA EL DOMINIO UMAG.CL
“Trabajo de titulacion presentado en
conformidad a los requisitos para obtener el
tıtulo de Ingeniero en Computacion e Informatica.”.
Profesor Guıa: Jose Canuman
Bozydaj Andres Biskupovic Trujillo
2008
RESUMEN
Desde su creacion, la Web ha vivido un acelerado crecimiento, convirtiendose en un gran
recurso de informacion. Debido a esto se hace muy complicado recuperar la informacion si
no se dispone de una herramienta y/o modelo para lograrlo.
La principal herramienta para la recuperacion de la informacion es una maquina o motor
de busqueda. Por esta razon, en esta tesis se desarrollo y implemento un modelo de motor
de busqueda para recuperar los documentos del dominio que alberga la Web en la Universi-
dad de Magallanes. La principal motivacion para este trabajo fue cubrir la ausencia de un
buscador de este tipo en la Web de esta universidad.
Para entender los conceptos necesarios a la hora de implementar primero se estudio la
teorıa de como esta compuesto y como funcionan los motores de busqueda en general, lo que
se describe en el comienzo del presente trabajo. Luego para la implementacion, se uso un
sistema de recoleccion de informacion, que genera una coleccion de paginas, que luego de ser
analizadas, parametrizadas y rankeadas, dieron paso a formar un ındice invertido y ası pos-
teriormente consultar sobre los documentos de la coleccion.
La eficacia de esta herramienta fue evaluada con distintos tipos de consultas. Las que
permitieron descubrir resultados interesantes y de gran valor para realizar mejoras tanto en
la estructura como en los algoritmos utilizados.
i
Indice general
I. Introduccion 1
1.1. Motivacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2. Un poco de historia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. Recuperacion de la informacion . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4. Vista logica de los documentos y usuario . . . . . . . . . . . . . . . . . . . . 4
1.5. Motor de busqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.6. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
II. Marco Teorico 7
2.1. Recuperacion de la informacion . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2. Caracterizacion de la Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1. Metodos de muestra . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2. Dinamica de la Web . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.3. Estructura de los Links . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3. Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1. Modelo Booleano . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2. Modelo Vectorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.3. Modelo Probabilıstico . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.4. Comparacion de los modelos clasicos . . . . . . . . . . . . . . . . . . 19
2.3.5. Modelos Alternativos . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
ii
2.3.6. Expansion de Consultas . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.7. Retroalimentacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3.8. Evaluacion: Precision y Recuperacion . . . . . . . . . . . . . . . . . . 24
2.4. Indexacion y consulta de paginas . . . . . . . . . . . . . . . . . . . . . . . . 25
2.4.1. Indice Invertido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.4.2. Consultas en Modelo Booleano . . . . . . . . . . . . . . . . . . . . . 28
2.4.3. Consultas en Modelo Vectorial . . . . . . . . . . . . . . . . . . . . . . 29
2.4.4. Consultas con frases . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.4.5. Espacio extra: Ley de Heaps - Ley de Zipf . . . . . . . . . . . . . . . 31
2.4.6. Construccion del Indice Invertido . . . . . . . . . . . . . . . . . . . . 33
2.4.7. Indices invertidos distribuidos . . . . . . . . . . . . . . . . . . . . . . 35
2.4.8. Generacion Distribuida de Indices Invertidos . . . . . . . . . . . . . . 36
2.4.9. Otros tipos de ındices . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.4.10. Ranking basado en texto . . . . . . . . . . . . . . . . . . . . . . . . . 44
2.5. Conectividad basada en el ranking . . . . . . . . . . . . . . . . . . . . . . . . 45
2.5.1. Consulta dependiente del ranking . . . . . . . . . . . . . . . . . . . . 46
III. La Web Chilena 49
3.1. Caracterısticas de la Web Chilena . . . . . . . . . . . . . . . . . . . . . . . . 50
IV. Un motor de busqueda para umag.cl 53
4.1. Recoleccion en umag.cl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.2. Normalizacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.3. Ranking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4. Indexador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.5. Buscador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.5.1. Memoria compartida . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.5.2. Proceso de busqueda: . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
iii
4.6. Comportamiento y resultados . . . . . . . . . . . . . . . . . . . . . . . . . . 66
V. Conclusiones 72
5.0.1. Trabajos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
VI. Anexo 75
6.1. WIRE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
6.2. Archivos - Scripts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
iv
Indice de figuras
2.1. Ejemplo de un grafo aleatorio y scale-free, cada grafo tiene 32 nodos e igual
numero de enlaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2. Estructura macroscopica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3. Coseno del angulo entre los dos vectores . . . . . . . . . . . . . . . . . . . . 17
2.4. Cercanıa entre terminos que aparecen en los mismo documentos . . . . . . . 22
2.5. Precision - Recuperacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.6. Procesos off-line y on-line. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.7. Indice invertido simple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.8. Restricciones. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.9. Busqueda de informacion sobre las consecuencias de la crisis de los misiles
cubanos en el desarrollo de la guerra frıa. . . . . . . . . . . . . . . . . . . . . 30
2.10. Ejemplo: “Camiones de ocasion”[con errores]. . . . . . . . . . . . . . . . . . 31
2.11. Ley de Heap - Ley de Zipf . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.12. Mezcla de ındices parciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
2.13. Mezcla de ındices parciales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.14. Pasos de mensajes entre procesadores para generar el ındice invertido central. 37
2.15. Indexacion de la Web: (1) Se analizan y extraen los links de las paginas. (2)
Se crean ındices parciales en caso de ausencia de memoria principal. (3) Los
ındices son fusionados para formar el ındice invertido completo. (4) Analisis
off-line para rankear los enlaces. . . . . . . . . . . . . . . . . . . . . . . . . . 39
v
2.16. Arbol de sufijos - Arreglo de sufijos. . . . . . . . . . . . . . . . . . . . . . . . 40
2.17. Sufijos del texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
2.18. Arreglo de sufijos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.19. Arreglo de sufijos, busqueda . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2.20. Arreglo de sufijos usando supraındice . . . . . . . . . . . . . . . . . . . . . . 43
2.21. Arreglo de sufijos usando el vocabulario como supraındice. . . . . . . . . . . 43
4.1. Diagrama del diseno de un motor de busqueda para umag.cl . . . . . . . . . 54
4.2. Distribucion de los enlaces en umag.cl . . . . . . . . . . . . . . . . . . . . . . 57
4.3. Normaliza1: normaliza el texto . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4. Normaliza2: separa texto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.5. Proceso de busqueda. 1: se recupera los terminos de la consulta usando CGI. 2:
busqueda binaria de cada uno de los terminos y son almacenados en estructura
respuesta. 3: Se ordenan de acuerdo a relevancia y cantidad de aciertos de los
terminos para luego entregar respuesta HTML. . . . . . . . . . . . . . . . . . 65
vi
Capıtulo I
Introduccion
Introduccion
1.1. Motivacion
La informacion, en su significado general es un conjunto de datos organizados que pro-
porcionan sentido o significado a alguna cosa, pero para esto primero debe ser localizada.
Cuando se dispone de un universo con gran cantidad de datos estructurados, en forma de
informacion, y solo se necesita un determinado tema, surge el problema de como alcanzar
lo deseado entre basto lote de recursos. Es por esto que surge la ciencia, recuperacion de
la informacion, que cubre desde la misma recoleccion hasta la busqueda de informacion en
particular, tanto en documentos, bases datos, imagenes, etc.
Para este caso, el interes sera la recuperacion de la informacion en los documentos de
la Web, y en forma particular, la informacion existente bajo el dominio umag.cl. Siendo
que este dominio no posee de una herramienta de busqueda, se ha generado la motivacion
de implementar un motor de busqueda. De esta manera el presente informe dara cuenta de
los pasos a seguir en la implementacion, como tambien los conceptos, estructuras de datos y
algoritmos a utilizar.
1.2. Un poco de historia
La tecnologıa, motor de busqueda ha tenido que mejorar rapidamente debido al creci-
miento de la Web. En 1994, uno de los primeros motores de busqueda, el World Wide Web
Worm (WWWW) tuvo un ındice de 110,000 paginas Web y documentos Web accesibles.
Ası, en Noviembre de 1997, se indexaba de 2 millones de paginas Web (WebCrawler) a 100
millones (de Search Engine Watch). Y para el ano 2000 se predecıa , que la Web contendrıa
sobre mil millones de documentos [2]. Y en forma paralela, el numero de consultas en los
motores de busqueda crecıa muchısimo. En Marzo y Abril de 1994, el World Wide Web
Worm recibio como promedio unas 1500 consultas por dıa. En Noviembre de 1997, Altavista
2
aseguro haber manejado 20 millones de consultas por dıa, aproximadamente. Teniendo en
cuenta el creciente numero de usuarios en la Web, y los sistemas automatizados de consulta
en buscadores, para el 2000 ya se preveıa alcanzar los cien millones de consultas por dıa.
Y en la actualidad, Google uno de los buscadores mas popular y usado recibe mas de 200
por dıa, teniendo en cuenta que hoy en dıa existe una gran cantidad de buscadores. Todo lo
anterior habla por si solo de la creciente cantidad de documentos y usuarios que existen en la
actualidad, y por lo mismo nace la necesidad del estudio de recuperacion de la informacion.
1.3. Recuperacion de la informacion
Es una ciencia, tambien, y mas conocida en ingles como information retrieval (IR), la cual
consiste basicamente en la busqueda de informacion en documentos, busqueda de los mismo
documentos, o datos dentro de los documentos.
Considerada un estudio interdisciplinario, pues cubre muchas disciplinas, tales como la
sicologıa cognitiva, la arquitectura de la informacion, diseno de la informacion, el comporta-
miento humano frente a la informacion, la linguıstica, la semiotica, informatica, entre otras.
Viendo la recuperacion de la informacion como un proceso de busqueda, este proceso tiene
como herramienta unica y principal, un motor de busqueda, a quien a traves de una consulta
se le solicita una determinada informacion para ası en forma respectiva responderla.
La Web crea nuevos desafıos para la recuperacion de la informacion. La cantidad de in-
formacion en la Web va aumentando rapidamente, como tambien su numero de usuarios.
La personas en general acostumbran a navegar pasando de enlaces a enlaces, o usando la
respuestas de los motores de busqueda. Los distintos enlaces que entrega un buscador para
una respectiva consulta tienden a ser muy subjetivos en su relevancia. Es por eso que la
recuperacion de la informacion se enfoca en entregar respuestas con buena calidad.
3
1.4. Vista logica de los documentos y usuario
Teniendo en cuenta que a nivel de computadores, para que un documento presente un
sentido de lenguaje natural, este debe ser expresado como un conjunto de palabras.
La efectividad en la recuperacion de la informacion esta directamente ligada tanto al
usuario como a la vista logica que tienen los documentos.
Por parte del usuario pueden existir dos sistemas de recuperacion de la informacion, a
traves de exploracion o por busqueda. En el primer caso, esto es, el usuario dispone de
directorios con nombres, normalmente separados por tema, luego el usuario para encontrar
lo que busca debe ir explorando hasta llegar a lo que busca, siendo esto una analogıa a la forma
en que ordenamos nuestros archivos en los distintos directorios de los sistemas operativos. Y
para el sistema de busqueda, el usuario debe abstraerse a la vista logica de los documentos,
es decir, pensar en un conjuntos de palabras, y de esta manera a traves de palabras claves el
usuario debe tratar de ubicar lo que desea en las respuestas de un buscador.
Si se considera una gran cantidad de documentos la primera opcion se hace muy tediosa y
costosa, mientras que la segunda es mucho mas eficiente en tiempo. Este trabajo se focalizar
en la segunda opcion.
1.5. Motor de busqueda
De igual modo que se ha mencionado antes , el motor de busqueda es la herramienta por
la que es posible recuperar informacion de la Web, para este caso.
De manera general, el motor de busqueda se separa en 3 partes o procesos:
Recoleccion
Estructuracion
Busqueda
4
Recoleccion: El primer proceso consiste en recorrer y conocer toda la informacion que se
desea abarcar. Para esto primero se debe definir nuestro universo de informacion , es decir,
decidir cuanta informacion sera tomada en cuenta y considerada como el total, por ejemplo
el universo podrıa ser, solo el dominio .cl, o solo los documentos bajo .org, o como para el
caso de este proyecto, solo los documentos bajo el dominio .umag.cl . Una vez definido el
dominio, se procede a copiar toda la informacion de igual forma en que esta estructurada,
para su posterior analisis. En el capıtulo 2 se tomara nuevamente el tema con mayor enfasis
describiendo las caracterısticas que tiene la Web.
Estructuracion: Este proceso se realiza una vez terminada la recoleccion, y debe reali-
zar el analisis de los documentos descargados. Dentro del analisis, existen funciones de quitar
etiquetas HTML para el caso y contenido demas que correspondan a la informacion en si,
quitar palabras de baja relevancia, formar estructuras de datos con la informacion de manera
de poder ser guardada con un formato especıfico, para luego poder ser leıdas facilmente. Esta
etapa sera estudiada en el capıtulo 2 y descrita con mayor profundidad en el capıtulo 3.
Busqueda: Este tercer proceso, es el encargado de llevar acabo la busqueda de la in-
formacion, dentro de la estructuras formadas en la etapa anterior. Esta es la unica parte del
motor de busqueda que interactua en forma directa con el usuario, ya que el procesamiento y
ejecucion es en tiempo real o online. En el capıtulo 2 se explican los algoritmos de busqueda
y metodos que se usan para la implementacion de motores de busqueda. Y en el capıtulo 4,
el metodo que fue usado para este trabajo.
Este informe en el capıtulo 2 da inicio a la descripcion del universo de los documentos, la
Web; revisando el modelo que tiende a seguir, su distribucion, cualidades, la caracterizacion
de la Web, y tambien cada uno de los factores que deben de ser considerados para realizar
una buena muestra, a la hora de recolectar la informacion. Luego se estudiara el motor de
5
busqueda y cada una las 3 etapas, describiendo cuales son sus caracterısticas, procesos, fun-
ciones, algoritmos y su forma general de funcionar. En el capıtulo 3, se vera como es la Web
en Chile. Y finalmente en el capıtulo 4, se sera mas especıfico, explicando la implementacion
del motor de busqueda en cuestion y los resultados obtenidos.
Para el capıtulo 4 se ha dejado, el estudio y explicacion de este caso particular de motor
de busqueda implementado en el presente trabajo. Y finalmente en el capıtulo 5 se obtienen
las conclusiones del caso.
1.6. Objetivos
Con el fin de acotar y declarar posibles metas de la implementacion del motor de busque-
da, se plantean los siguientes objetivos:
Objetivo General:
Implementar un Motor de busqueda para el dominio umag.cl, que permita la recupe-
racion de informacion de los documentos HTML que aloja este dominio. Y a la vez,
servir como herramienta para analisis y gestion de la Web bajo umag.cl.
Objetivos Especıficos:
Implementar un algoritmo de busqueda que responda cada una de las consultas, entre-
gando resultados en funcion de la relevancia de un documentos con respecto a resto de
los documentos.
Permitir consultas de multiples terminos
6
Capıtulo II
Marco Teorico
Marco Teorico
2.1. Recuperacion de la informacion
Para empezar cabe aclarar las diferencias existentes entre recuperar datos (RD) y recu-
perar informacion (RI).
Para el primer caso es simple, los datos acostumbran a tener un formato y orden
especıfico el cual se conoce, mientras que la informacion no tiene una estructura clara
y tampoco es facil crearla.
Cuando se recuperan datos, existe una respuesta exacta, pero en la recuperacion de la
informacion no existe una respuesta correcta.
El la RI, cada documento puede ser mas o menos relevante, y esto puede cambiar segun
el usuario y la situacion
Para la RD, lo que prima es la eficiencia (velocidad de la respuesta y espacio), mientras
que en RI, lo que mas importa es la calidad de la respuesta.
Dado que comprender cabalmente el significado de un texto en forma automatica es
imposible en la practica, RI busca una aproximacion a responder lo que el usuario
busca.
El problema formal:
El problema de RI se puede definir como:
Dada una necesidad de informacion (consulta + perfil del usuario + ...) y un conjunto
de documentos, ordenar los documentos de mas a menos relevantes para esa necesidad y
presentar un subconjunto de los mas relevantes.
Como solucion se plantean tres etapas
1. Tomar una buena muestra de la Web.
8
2. Disenar algoritmos y estructuras de datos para dar orden a la informacion.
3. Elegir un modelo que permita calcular la relevancia de un documento frente a una
consulta, con el uso de la estructuras implementadas.
2.2. Caracterizacion de la Web
2.2.1. Metodos de muestra
Cuando se desea tener una coleccion de estampillas, para evitar las repeticiones se debe
saber cual tenemos y cual no, tambien importa el tamano, su origen, por lo que existe todo un
seguimiento de como llevar a cabo una buena coleccion. De la misma manera sucede cuando
se realiza un censo de poblacion, se mantiene un registro de los hogares contados, tampoco se
puede entrevistar un mismo hogar en forma simultanea, aunque los hogares pueden ser muy
similares, estos son unicos, etc. De una forma muy similar ocurre con la recoleccion en la Web,
debido a que una de las mayores dificultades en la caracterizacion de la Web es como obtener
una buena muestra. Ya que hay pocas paginas relevantes en un gran conjunto de paginas no
importantes, no basta con elegir una URL en forma aleatoria. Muchas veces aplicaciones o
paginas con poca relevancia deben ser descartadas, es por esto ultimo que la asignacion de im-
portancia es un tema muy delicado de tratar, inclusive cuando solo tenemos un tema a tratar.
Principalmente se distinguen dos metodos para el muestreo de paginas Web:
Muestreo Vertical, se realiza un recorrido de las paginas de acuerdo a sus dominios.
Los dominios se traducen en una estructura jerarquica, de tal modo que el muestreo se hace
en niveles, por ejemplo, por paıses luego por tipo de dominios de cada paıs, edu ,org etc ..
ası sucesivamente...
9
Muestreo Horizontal, criterio de muestreo que no se basa en los nombre de dominio.
En este caso, existen dos tipos de aproximacion a la informacion a ser recolectada: usando
los registros (logs) de los servidores proxy de grandes organizaciones o ISP (Proveedor de
Servicio a Internet); y la segunda usando un Web Crawler. Estas dos opciones presentan
ciertas ventajas y desventajas: cuando se monitorea un servidor proxy es facil de encontrar
las paginas mas populares, pero su visita periodica es imposible ya que esta depende de los
usuarios; por otro lado usando un Crawler la popularidad de las paginas debe ser estimada
a priori, pero si pueden ser facilmente revisadas .
2.2.2. Dinamica de la Web
Existen dos areas en la dinamica de la Web: primero, el estudio de como crece la Web;
y segundo, el estudio de la actualizacion de sus sitios [8]; en este caso nos enfocaremos en
la frescura de la Web, es decir, en terminos de la creacion, actualizacion y eliminacion de
documentos. Con respecto a como la Web crece existe un modelo estudiado por Huberman
y Adamic [8].
Cuando se estudia la actualidad de los documentos, la informacion es obtenida por repe-
tidos accesos a un conjuntos de paginas en un tiempo determinado.
Para cada pagina p y cada visita, se dispone de la siguiente informacion:
La hora de acceso a la pagina, time-stamp : visitp.
La hora de la ultima modificacion del documento (dada por la gran mayorıa de los
servidores Web).
El texto de la pagina , el cual puede ser comparado con copias antiguas, para detectar
cambios: modifiedp La siguiente informacion puede ser reconocida a la hora de revisar
una pagina en un periodo corto de tiempo:
10
La hora de la primera aparicion de una pagina : createdp.
La hora en que la pagina o documento dejo de ser alcanzable : deletedp. Segun Koehler
[8] las paginas que son inalcanzables en el futuro, seran alcanzables por lo cual el
prefieres llamarlas ”paginas en coma.en vez de ”paginas muertas”
En todo caso los resultados antes mencionados son solo estimaciones de los valores actua-
les de una pagina determinada ya que estos son obtenidos por asignacion de eventos y no
notificaciones de eventos, por lo cual una pagina Web que es accedida dos veces puede haber
cambiado mas de dos veces entre medio de las 2 revisiones.
Estimacion de frescura y vida
Existen diferentes metricas relativas al tiempo que nos dan informacion de una Web, las
mas usadas :
Age : visitp −modifiedp .
Lifespan: deletedp − createdp.
Numero de cambios durante el trecho de vida: changesp
Promedio de cambios : lifespanp/changesp. Una vez teniendo los valores anteriores se
pueden obtener utiles mediciones de por ejemplo:
Distribucion del intervalo de cambios.
Promedio del trecho de vida de las paginas
La media de vida de las paginas Web, llamado ”vida promedio”
11
2.2.3. Estructura de los Links
Con respecto a las redes de computadores, Barabasi [8] dice ”Tal como el diseno del ser
humano, las redes emergentes parecen tener mas en comun con la celula o el sistema ecologico
que con el reloj suizo”.
La representacion grafica de las conexiones entre sitios web tiene una topologıa escalar-
libre (Scale-free) y una estructura macroscopica que es diferente a la distribucion completa-
mente aleatoria de un grafo. Por esto ultimo un Web Crawler debe estar dotado de capaci-
dades especiales para la recoleccion.
Redes Scale-Free , Escalarmente libres
Las redes scale-free, a diferencia de las redes aleatorias, se caracterizan por tener una
distribucion desigual constante de sus enlaces. Estas redes han sido tema de estudio por
Barabası [8], y son distinguidas como redes donde su numero de links Γ(p) a una pagina p
se rige de la siguiente ley:
Pr(Γ(p) = k) k−Θ
Una red de este tipo se caracteriza por tener unos pocos nodos mas enlazados que otros,
actuando como hubs. La diferencia con la red aleatoria es mostrada en la figura 2.1
Las redes scale-free son usadas en una gran cantidad de contextos, por lo que existe una
infinidad de documentacion al respecto. A continuacion algunos ejemplos fuera del ambito
de los computadores:
Amigos y la popularidad en los humanos. Economicamente hablando algunas personas
arrastran toda la suerte mientras que otras no [8].
Las proteınas en la interaccion con el metabolismo
La colaboracion de los actores en las pelıculas
12
Figura 2.1: Ejemplo de un grafo aleatorio y scale-free, cada grafo tiene 32 nodos e igual
numero de enlaces
Citas en las publicaciones de cientıficos
Y otro ejemplos relacionados a la computacion son:
La ınter conectividad de nodos para Internet geograficamente y fısicamente hablando.
Numero de enlaces a paginas web.
La participacion de usuarios a grupos y comunidades.
Intercambio de e-mails.
Estructura Macroscopica
La mayorıa de los estudios de la Web y su estructura, se enfocan en un subconjunto de
millones de paginas del motor de busqueda Altavista, al cual definen como un grafo conexo,
ignorando la direccion de los enlaces [8]. Estos estudios identifican un solo componente que
esta fuertemente interconectado, a quien llaman el componente principal o MAIN. Empe-
zando en MAIN, y siguiendo los enlaces que apuntan hacia afuera, de encuentran los OUT,
y a los que llegan a MAIN, se les denomina IN. Tambien existen documentos que no salen
ni entran de MAIN, sino que estan conectados con IN o OUT, a estos se les llama tentacu-
13
los, TENTACLES. Y finalmente existen las islas, ISLANDS, aquellos archivos que no estan
enlazados con ningun otro documento.
MAIN: Sitios que estan fuertemente ligados, y que se puede llegar de cualquier sitio a
cualquier otro dentro del mismo componente.
IN: Sitios de donde se puede llegar a main pero no al reves.
OUT: Sitios que se llega desde MAIN, pero no es posible llegar de ellos a MAIN.
Otros sitios que se pueden alcanzar desde IN o solo llegar a OUT (TENTACLES),
y lugares en ambos sentidos llamados tuneles, TUNNEL, y los sin conexion alguna,
ISLANDS.
Figura 2.2: Estructura macroscopica.
2.3. Modelos
Los modelos corresponden a los metodos utilizados para intentar adivinar lo que el usuario
desea encontrar. De acuerdo a la documentacion en libros y en la Web existe una gran cantidad
de tipos pero todos ellos nacen de la combinacion o variantes de tres modelos clasicos, siendo
el modelo Booleano, modelo vectorial y el modelo probabilıstico.
14
2.3.1. Modelo Booleano
Este modelo corresponde al mas simple de los tres. De igual manera que su nombre lo da a
entender, este trabaja con valores booleanos, es decir, su relevancia es binaria, un documento
es relevante o no lo es. Al momento de hacerle consultas, un documento es importante solo
si contiene la palabra. Este tipo de modelo se hace uso de operadores logicos, AND y OR.
Cuando se hace uso del AND en una consulta, los documentos resultantes deben poseer
todas las palabras. Consultas con OR, los documentos deben contener alguna palabra. Y
para consultas A BUTNOT B: los documentos deben ser relevantes para A pero no para B.
Ejemplo:
Maradona AND Mundial AND ((Mexico OR Italia) BUTNOT U.S.A.)
Siendo uno de los modelos mas conocidos, es el mas primitivo, y se le considera bastante
malo para RI, por las siguientes razones:
No discrimina entre documentos mas y menos relevantes.
Da lo mismo que un documento contenga una o cien veces las palabras de la consulta
Da lo mismo que cumpla una o todas las clausulas de un OR
No considera un calce parcial de un documento (Ej. que cumpla con casi todas las
clausulas de un AND).
No permite siquiera ordenar los resultados.
El usuario promedio no lo entiende:
Se necesita investigar sobre los Aztecas y los Incas, entonces busca Aztecas AND Incas
(se perderan excelentes documentos que traten una sola de las culturas en profundidad,
debio ser Aztecas OR Incas)
Y es el mas famoso debido a que,
15
Es el primero que se viene a la mente a la hora de implementacion.
Es la opcion favorita para manejar texto en una base de datos.
Es simple de formalizar y eficiente de implementar.
Puede usar combinacion con otro modelo, Ej. para excluir documentos (Google usa
AND como filtro).
Puede ser util con mejores interfaces.
2.3.2. Modelo Vectorial
Este modelo en forma contraria al Booleano, asigna pesos no binarios a los terminos para
asimilar la relevancia. De hecho no se hace uso de todos los terminos, sino que se selecciona
un conjunto de palabras utiles para discriminar, las cuales son terminos que no otorgan ma-
yor sentido a la informacion, a este conjunto se les llama palabras vacıas o stopwords. Por lo
general corresponden a preposiciones, pronombres, etc.
Hay veces que lo anterior se enriquece con procesos de lematizacion o stemming, etique-
tado e identificadores de frases.
Sea {t1, ...tk} el conjunto de terminos y {d1, ...dN} el de documentos, entonces un documen-
to se modela como vector di −→ ~di = (w(t1, di), ..., w(tk, di)) donde w(tr, d) es el peso del
termino tr , en el documento di
Para calcular el peso existen varias formulas, pero las mas conocida es:
w(tr, di) = wr,i = tfr,i×idfr
|~di|=
tfr,i×log Nnr√∑k
s=1(tfs,i×log N
ns)2
donde tfr,i (frecuencia del termino), es la cantidad de veces que tr, aparece en di, y ni es la
cantidad de documentos donde aparece tr
Si un termino aparece mucho en un documento, se supone que es importante en ese
documento (tf crece).
16
Pero si aparece en muchos documentos, entonces no es util para distinguir ningun
documento de los otros (tf decrece).
Ademas se puede normalizar las frecuencias para no favorecer documentos mas largos
(por ejemplo tfnorm = tfr,d/maxk(tfk,d)).
Lo que se intenta medir es cuanto ayuda este termino a distinguir ese documento de
los demas.
Se calcula la similaridad entre dos documentos mediante la distancia coseno:
sim(di, dj) = ~di ∗ ~dj =∑k
r=1 wr,i × wr,j
(que geometricamente corresponde al coseno del angulo del angulo entre los dos
vectores).
Figura 2.3: Coseno del angulo entre los dos vectores
La similaridad es un valor entre cero y uno.
17
Los documentos iguales tienen valor 1, y ortogonales (si no comparten terminos) tienen
similaridad 0.
En particular, una consulta se puede ver como un documento(formado por esas pala-
bras) y por lo tanto como un vector
Dado que en general cada palabra aparece solo una vez en la consulta y esta es muy
corta, se puede en general calcular la relevancia de di para q con la formula:
sim (di, q) =∑k
r=1 wr,i × wr,q ∼∑
tr∈q wr,i × idfr
La ultima formula no es identica a sim pero genera el mismo orden en los documentos
(falta dividir por |~q|)
La formula anterior se puede simplificar aun mas definiendo wr,i = tfr,i
|~di|y wr,q = idfr.
El primer peso se llama factor de impacto.
Pero el modelo es mas general, y permite cosas como:
• Que la consulta sea un documento.
• Hacer clustering de documentos similares.
• Retroalimentacion (Relevance feedback)
• Este modelo es, de lejos, el mas popular en RI pura hoy en dıa.
2.3.3. Modelo Probabilıstico
Otro modelo clasico de la recuperacion de la informacion, donde la base principal de su
funcionamiento es el calculo de la probabilidad de un documentos de ser relevante a una
pregunta dada. Se usa un modelo de probabilidad de independencia en terminos binarios.
La probabilidad de los terminos es independiente (un termino es independiente de los
otros).
18
Los pesos asignados a los terminos son binarios.
La equiparacion probabilıstica se basa en que, dados un documento y una pregunta, es
posible calcular la probabilidad de que ese documento sea relevante para esa pregunta.
Si un documento es seleccionado aleatoriamente de la base de datos hay cierta probabi-
lidad de que sea relevante a la pregunta. Si una base de datos contiene N documentos, n de
ellos son relevantes, entonces la probabilidad se estima en:
P (relevancia) = n/N
En concordancia con la teorıa de la probabilidad, la de que un documento no sea relevante a
una pregunta dada viene expresada por la siguiente formula:
P (↓ relevancia) = 1− P (relevancia) = N − n/N
Obviamente, los documentos no son elegidos aleatoriamente, sino que se eligen sobre la base
de la equiparacion con la pregunta basado en el analisis de los terminos contenidos en ambos
casos. Ası, la idea de relevancia esta relacionada con los terminos de la pregunta que aparecen
en el documento.
Una pregunta dada divide la coleccion de documentos en dos conjuntos: los que responden
a la pregunta y los que no.
Se considera que a traves de este modelo se obtienen buenos resultados, de cualquier
forma, los resultados no son mucho mejores que los obtenidos en el modelo booleano y
en el vectorial
Sin embargo, todos los documentos seleccionados no son realmente relevantes.
2.3.4. Comparacion de los modelos clasicos
El modelo clasico mas popular es el vectorial, por ser simple, facil y eficiente de imple-
mentar, y entregar eficientes resultados. En muchos casos las aplicaciones suelen llegar
hasta aquı.
19
Hay modelos mas sofisticados. Pero sin duda lo que se gana no justifica su esfuerzo.
Todos los modelos clasicos tienen ciertas falencias comunes, la mas notoria es la inca-
pacidad para capturar las relaciones entre los terminos. Por ejemplo:
Si se busca : guerra frıa se desea recuperar informacion sobre la crisis de los misiles
cubanos. Sin embargo, el sistema no tiene idea que ambas cosas estan relacionadas y
la interseccion de vocabulario podrıa ser nula.
La solucion pasa por el analisis linguıstico :
• lematizar (para no perder variantes de la misma palabra)
• etiquetar (para distinguir verbos de sustantivos)
• detectar frases comunes.
Otro elemento es el uso de tesauros y sinominos para expandir la consulta, de modo de
poder recuperar:
se vende auto usado
frente a la consulta:
autos de segunda mano
Sin embargo mantener tesauro en muy costoso en terminos de trabajo manual y no
suele ser posible mantenerlo al dıa con las expresiones que van apareciendo.
El uso un tesauro global no siempre funciona bien, por ejemplo estrella puede ser
una generalizacion de supernova, pero no en un contexto que se refiere a estrellas de
television.
20
Se puede usar informacion del texto como la estructura para refinar mejor la consulta
(Ej. un termino que aparece en la cabecera o tıtulo debe ser mas importante que en un
pie de pagina.)
Se pueden usar distintas tecnicas para descubrir que ciertos terminos estan correlacio-
nados. A esto apuntan los modelos alternativos y las tecnicas de expansion de consultas
que se veras a continuacion.
2.3.5. Modelos Alternativos
Los modelos usados como alternativa a los clasicos, son en general costosos de implementar
y no siempre dan grandes resultados. Por ello son en general poco populares, LSI, las redes
neuronales y Bayesianas.
Extensiones al modelo Booleano
• Booleano Extendido.
• Conjuntos Difusos.
Extensiones al modelo Vectorial
• Vectorial generalizado.
• LSI: Latent Semantic Indexing.
• Redes Neuronales.
Extensiones al modelo Probabilıstico
• Redes Bayesianas.
• Redes de inferencia Bayesiana.
21
2.3.6. Expansion de Consultas
Con el fin de mejorar la relevancia del resultado de una consulta, es posible expandir una
consulta sin alterar el modelo original. Para llevar esto a cabo, un modelo posible es considerar
un espacio vectorial donde los terminos son los puntos y los documentos las coordenadas del
espacio:
tr −→ ~tr = (w1,r, ..., wN,r)
Para este caso , la similaridad entre terminos se define exactamente como la de los
documentos:
sim(tr, ts) = ~tr ∗ ~ts =∑N
i=1 wi,r × wi,s
Si dos terminos tienden a aparecer en los mismos documentos sus vectores seran cerca-
nos.
Figura 2.4: Cercanıa entre terminos que aparecen en los mismo documentos
Dada una consulta formada por terminos, estos se consideran vectores y la consulta se
expande con todos los vectores(terminos) cercanos a los de la consulta.
22
Tambien es posible usar diccionarios o tesauros para agregar sinonimos y/o terminos
relacionados (un OR de ellos).
Otra forma de usar la distancia
2.3.7. Retroalimentacion
Es la funcion que usan algunos sistemas de recuperacion de la informacion, por el cual
recuperan informacion de similar relevancia con respecto a un documento o un conjunto
de ellos. La idea tras este metodo, es tomar los resultados que inicialmente fueron dados
a una determinada consulta y sobre parte de estos realizar una nueva consulta, donde el
valor de relevancia sera similar a los documentos iniciales. Esta funcion es comun verla en
los buscadores, tal es el caso de Google donde en cada uno los documentos de la respuesta,
existe una opcion llamada Paginas similares, la cual da la opcion al usuario de buscar
documentos similares. De este modo, puede preguntarsele al usuario cuales documentos de
los recuperados son relevantes o no, y volver a empezar todo de nuevo, en funcion de la
respuesta del usuario.
Sea V el conjunto de documentos recuperados que el usuario divide en Vr (relevantes)
y Vn (no relevantes). La formula clasica de Rochio modifica el vector ~q de la siguiente
forma:
~qm = α~q + β|Vr|
∑dj∈Vr
~di - γ|Vn|
∑di∈Vn
~di
La idea es acercar el vector ~q al conjunto de documentos relevantes y alejarlo del
conjuntos de documentos no relevantes.
Se puede particularizar segun el caso. Por ejemplo puede ser mucho pedir que el usuario
marque los documentos no relevantes. En ese caso se puede usar γ (retroalimentacion
positiva).
El uso de ”paginas similares”de varios buscadores Web es la version sencilla de esto.
23
2.3.8. Evaluacion: Precision y Recuperacion
Cuando se responde una consulta, es recuperada la informacion y generada la respuesta,
pero como evalua esta salida, pues bien, existen muchas medidas pero de momento solo se
abarcara la mas popular, la cual corresponde a un diagrama precision-recuperacion (precision-
recall).
Precision: cuantos documentos recuperados son relevantes.
Recuperacion: cuantos documentos relevantes se recuperaron ( tambien conocido como
exhaustividad).
Figura 2.5: Precision - Recuperacion
Segun la cantidad que se elige como relevantes, se puede hacer aumentar una a costa
de reducir la otra.
Para evaluar un modelo de recuperacion de la informacion se debe tener en cuenta todo
el grafico. En la figura, A o B pueden ser preferibles segun la aplicacion.
Es facil tener alta precision: basta con retornar el documento mas relevante, pero enton-
ces la recuperacion es cercana a cero. Es facil tener alta recuperacion: basta retornar
todos los documentos, pero ahora la precision se hace cero. El objetivo es tratar de
aumentar ambos al mismo tiempo.
24
Para comparar dos sistemas se debe decidir que precision y/o recuperacion se necesita.
Ademas se necesita una coleccion de referencia: documentos, preguntas y respuestas
correctas.
2.4. Indexacion y consulta de paginas
La busqueda en la Web tiene dos partes: off-line y on-line. La parte off-line se realiza
periodicamente por el motor de busqueda y se encarga de descargar un subconjunto de sitios
para luego formar una coleccion de paginas, que luego es transformada en una estructura
aplicable a busquedas. Mientras que la parte on-line es ejecutada cada vez que un usuario
hace una consulta al motor de busqueda, y usa la estructura o index para seleccionar posibles
candidatos referenciandose por una estimacion de la relevancia que posee sobre el resto de
los documentos.
Figura 2.6: Procesos off-line y on-line.
Los archivos en la Web estan en distintos formatos tales como texto plano, paginas HTML,
documentos PDF, y otro formatos propietarios. Es por esto que para la indexacion se debe
considerar una vista logica de los documentos, siendo la mas usaba, el modelo de una bol-
sa de palabras, donde cada pagina es visto como un conjunto desordenado de palabras. En
25
lo buscadores modernos esta vista es fortalecida y optimizada anadiendo informacion extra
como, frecuencia de las palabras, los atributos del texto, y informacion de las cabeceras de
los HTML .
Existen varias operaciones de normalizacion para la extraer palabras de los documentos,
siendo las mas usadas: tokenizacion, remover stopwords, lematizacion o stemming
Tokenizacion es la descomposicion de un texto en unidades mınimas de informacion, pala-
bras.
Stopwords son palabras que acarrean poca informacion semantica, que tienen un bajo poder
de discriminacion a la hora de asignar la relevancia de un documento. En el castellano, por los
general estos stopwords corresponden a preposiciones, artıculos, adverbios, etc. Usualmente
en la recoleccion de la informacion estas palabras son descartadas por razones de eficiencia,
y tambien por el espacio de almacenamiento que estas ocuparıan, debido a su alta taza de
frecuencia.
Stemming, operacion o metodo usado para reducir las palabras a su raız morfologica.
Existen otros metodos de normalizacion que son mas complejos como, traduccion y busqueda
por sinonimos, deteccion de expresiones de multiples palabras, identificacion de frases, etc.
que son usadas por algunos buscadores. Siendo estas ultimas muy costosas y pocas precisas
en caso de tener una taza de error alta.
2.4.1. Indice Invertido
Es la estructura de datos mas elemental usada para relacionar, asociar e identificar pala-
bras o terminos a una posicion de un documento o un conjunto de estos, la recuperacion de
palabras.
El ındice invertido en su forma mas basica esta compuesto por dos partes: vocabulario y
una lista de ocurrencia.
Vocabulario : es una conjunto de palabras distintas de un texto, llamadas llaves,
26
donde a cada uno de estos terminos se le asocia una lista de ocurrencias dentro de un
documento o un conjunto de documentos.
Lista de ocurrencias o posteo : corresponde a la posicion de una palabra. Existen
distintas variantes dependiendo del modelo de recuperacion a utilizar. ındice invertido
de archivos y ındice invertido de palabras, respectivamente.
Figura 2.7: Indice invertido simple.
Variante para modelo Booleano:
• Es conveniente almacena la lista de ocurrencia de cada termino en orden creciente
de documento.
Variante para modelo Vectorial:
• Se almacena el tf correspondiente en cada entrada de posteo (puede ser el factor
de impacto tf/|di|)
• Debe almacenar el idf correspondiente en cada entrada del vocabulario.
• Es conveniente guardar el maximo tf de cada uno de los terminos en el vocabulario.
27
• La lista de ocurrencia se cada termino, de ordena en forma decreciente de tf .
Variante para busqueda de frases:
• Se debe almacena la inversion: para cada termino y documento, las lista de sus
posiciones exactas en el documento.
• Con el fin de reducir espacio, se puede tener un ındice de bloques: se corta el
texto en grandes bloques y se guarda solo los bloques donde ocurre cada termino.
2.4.2. Consultas en Modelo Booleano
Para este modelo las palabras de la consulta se buscan en el vocabulario (cargado en
memoria), por ejemplo usando la funcion hashing.
Se recuperan del disco las listas de posteo de cada palabra involucrada (restricciones
de metadatos).
Se realizan las operaciones de conjuntos sobre ellas (union, interseccion, diferencia, etc).
Las lista estan ordenadas crecientemente, de modo que se puede operar recorriendolas
secuencialmente. Los documentos se recuperan ordenados por numero de documentos.
Si una lista es muy corta y la otra muy larga, es mas rapido buscar en forma binaria
la corta en la larga (O(1) por Zipf).
Se complica si las listas estan representadas por diferencias, pero se puede almacenar
cada tanto un valor absoluto.
Se puede usar evaluacion compleja o parcial (restricciones AND, BUTNOT).
28
Figura 2.8: Restricciones.
2.4.3. Consultas en Modelo Vectorial
La consulta puede tener varias palabras y solo interesa recuperar los R documentos
mas importantes o relevantes.
Los documentos de cada termino estan almacenados en orden decreciente de tf .
La idea es mantener un ranking de los R documentos di con mayor sim(di, q).
Se comienza con el termino de la consulta de mayor idf (lista de ocurrencia mas corta),
y se trae los R primeros documentos de su lista(almacenados en ese mismo orden).
Si no se logra juntar R, se sigue con el segundo termino de mayor idf y ası...
Una vez que se obtienen R candidatos, se sigue recorriendo las listas de los terminos,
de mayor a menor idf .
Sin embargo, como el tf en cada lista decrece, se puede en cierto momento determinar
que no es necesario seguir recorriendo la lista pues los candidatos no pueden entrar al
ranking de los R mejores.
Si se almacena el maximo tf en el vocabulario, es posible eliminar terminos completos
sin siquiera ir al disco una vez.
Puede hacerse incluso mas eficiente cortando las listas donde se considere improbable
que modifiquen el ranking.
29
Este tipo de relajamiento esta permitido en la recuperacion de la informacion y es muy
utilizado en las maquinas de busqueda de la Web.
En particular, en la Web la recuperacion no solo es difıcil de medir sino que ya viene
condicionada por el crawling, que raramente alcanza a recolectar el 50% del total. De
modos que las maquinas de busquedas se concentran mas en la precision. Es decir, que
lo que se recupera sea bueno mas que recuperar todo lo bueno.
Figura 2.9: Busqueda de informacion sobre las consecuencias de la crisis de los misiles cubanos
en el desarrollo de la guerra frıa.
2.4.4. Consultas con frases
Para busquedas por frase o proximidad, se obtienen las listas de las ocurrencias exactas
de las palabras involucradas y se realiza una pseudo insercion(inversion, secuencial o
combinado).
Si se tiene solo un ındice de bloques, este permitira determinar que el patron no aparece
en algunos bloques del texto, pero en los demas se debera recurrir a busqueda secuencial
(compresion).
Eligiendo correctamente el tamano del bloque se puede obtener un ındice que sea subli-
neal en espacio extra y tiempo de busqueda simultaneamente.
30
Esta alternativa es aceptable para colecciones medianas (200MB) y necesita tener acceso
al texto (Ej. no sirve para indexar la Web pero si para un buscador interno del sitio
Web)
Para busquedas mas complicadas se puede realizar una busqueda secuencial en el vo-
cabulario. Esto es tolerable por la ley de Heaps
Luego se realiza la union de las listas de posteo de todas las palabras del vocabulario
que calzaron con el patron de la busqueda. Se observa que esto puede ser costoso si la
consulta tiene poca precision.
Figura 2.10: Ejemplo: “Camiones de ocasion”[con errores].
2.4.5. Espacio extra: Ley de Heaps - Ley de Zipf
Estas dos leyes empıricas son ampliamente aceptadas por la ciencia de recuperacion de la
informacion.
Ley de Heaps : El vocabulario de un texto de largo n crece como:
31
k = C × nβ
donde C y 0 < β < 1 dependen del tipo de texto. En la practica, 5 < C < 50 y 0, 4 ≤ β ≤ 0, 6
y k es menos del 1% de n
En la practica el vocabulario entra en la memoria RAM (ejemplo, 5MB para 1GB).
Ley de Zipf : Si se ordenan los terminos de un texto de mas a menos frecuente,
entonces:
nr = NrαHN (α)
donde
Hn(α) =∑k
r=11rα
lo que significa que la distribucion es muy sesgada: unas pocas palabras (stopwords) aparecen
muchas veces y muchas palabras apareces pocas veces.
En particular, los stopwords se llevan entre el 40% y 50% de las ocurrencias y aproxi-
madamente la mitad de las palabras aparecen solo una vez.
Notar que la Ley de Heap puede deducirse a partir de la Ley de Zipf y entonces α = 1/β
Posteo/Inversion:
• Caso Booleano: los numeros de documentos son crecientes, se pueden almacenar
las diferencias (Elıas). Ası comprimiendo, requiere un 10% - 25% extra sobre el
texto.
• Caso Vectorial: eso ya no ocurre, pero todos los documentos con el mismo tf
(muchos por Zipf) pueden aun ordenarse. El ındice requiere 15% - 30% extra.
32
Figura 2.11: Ley de Heap - Ley de Zipf
• Busqueda de frases: la inversion lleva el espacio total al 25% - 45% extra (posi-
ciones crecientes).
• Con direccionamiento de bloques esto puede bajar hasta 4% para colecciones no
muy grandes, al costo de mayor busqueda secuencial
• Se puede comprimir el texto a 25% - 30% del espacio original (Huffman sobre
palabras).
2.4.6. Construccion del Indice Invertido
Se recorre la coleccion secuencialmente
Para cada termino leıdo, se busca en el vocabulario(que se mantiene en memoria)
Si el termino no existe aun, se agrega al vocabulario con una lista de posteo vacıa.
Se agrega el documento que se esta leyendo al final de las lista de posteo del termino.
Una vez leıda toda la coleccion, el ındice se graba en disco.
33
En caso de usar ındices de bloques, se construye solo el posteo considerado a los bloques
como documentos.
En caso de necesitar inversion, se almacena ademas de la lista de ocurrencias de cada
termino una de inversion, donde se debe almacenar la posicion de cada ocurrencia de
ese termino.
Para el caso de los ındices en el modelo vectorial, la lista de posteo esta ordenada por
tf y dentro del tf por numero de documento. A medida que se va encontrando mas
y mas veces el termino en el mismo documento su entrada va siendo promovida mas
adelante en las lista del termino.
Otro metodo: generar tuplas (t−r, tfr,i, i) y luego ordenar, pero no se puede comprimir
hasta el final.
El mayor problema que se presenta en la practica es que, obviamente, a medida que
el vocabulario se procesa , la lista de ocurrencia tambien crece, de tal forma, el ındice
puede llegar a ocupar demasiada RAM e incluso no disponer de memoria primaria.
Cada vez que la memoria primaria se agota, se graba en disco un ındice parcial, se
libera la memoria y se comienza de cero.
Luego de haber procesado todo el texto, se realiza un merge de los ındices parciales.
Esta mezcla no requiere demasiada memoria porque es un proceso secuencial, y resulta
relativamente rapido en I/O porque el tamano a procesar es bastante menos que el
texto original.
Debe existir un orden en la mezcla de los ındices parciales.
El metodo este se adapta facilmente para realizar actualizaciones de ındice.
34
Figura 2.12: Mezcla de ındices parciales
2.4.7. Indices invertidos distribuidos
En muchos casos, por bueno que sea el algoritmo de indexacion o de busqueda, no es
suficiente para cubrir la demanda, debido a las siguientes razones:
El texto es demasiado grande.
La frecuencia de actualizaciones es demasiado alta.
Llegan demasiada consultas por segundo.
La velocidad de los discos no esta creciendo al ritmo necesario.
Una de las alternativa para remediar esto es el uso del paralelismo. Bien disenado, puede
expandir la capacidad de procesamiento tanto como se desee. El uso de redes muy rapidas
formadas por unas pocas maquinas muy potentes se ha convertido en una alternativa de bajo
costo.
En estas redes el acceso remoto cuesta aproximadamente los mismo que el acceso al
disco local. Normalmente todos los procesadores pueden comunicarse de a pares sin producir
congestion.
Para la paralizacion, la RAM total se considera como una gran memoria distribuida.
35
Figura 2.13: Mezcla de ındices parciales
Este procesamiento en paralelo se puede usar de distintas formas:
Para construir o actualizar el ındice en paralelo.
Replicar el ındice (si no es muy grande), con el fin de poder responder las consultas en
paralelo .
Para particionar el texto.
Para las consultas existen dos medidas de interes:
1. Concurrencia (Throughput): que es la cantidad de consultas respondidas por segundo.
2. Tiempo de respuesta: tiempo que demora una consulta particular.
Cuando existe una alta concurrencia se debe replicar el ındice, y si existe el ındice ocupa
mucho volumen, se particiona el ındice.
2.4.8. Generacion Distribuida de Indices Invertidos
Para la construccion de ındices invertidos en forma distribuida, existen distintas variantes
de como hacerlo, algunas son:
1. Se distribuye el texto entre las maquinas equitativamente.
36
2. Cada maquina construye su ındice invertido local.
3. Luego, se aparean de a dos, jerarquicamente, hasta que una zona contiene el vocabulario
4. Esa maquina calcula que parte del vocabulario sera responsabilidad de cada procesador,
y distribuye esa informacion.
5. Los procesadores se aparean todos con todos intercambiando las listas de ocurrencias.
6. Secuencialmente transmiten su parte del ındice a un disco central, donde se concatenan
para formar un ındice globalizado.
Figura 2.14: Pasos de mensajes entre procesadores para generar el ındice invertido central.
Tipos de Indice Invertidos Distribuidos
Para el caso (2), se tiene un ındice particionado por documentos
• Para consultar de debe distribuir la consulta a todos los procesadores y luego
integrar los resultados.
• El trabajo se reparte bien, pero como el tiempo es sublineal, la concurrencia no se
escala idealmente.
• El tiempo de respuesta se reduce un poco.
37
• Para el modelo booleano es ideal porque no transmite informacion redundante por
la red.
• Para el modelo vectorial se debe seleccionar lo mejor de todos los ranking, pero
presenta un gran detalle: los ranking locales no son los mismos con el ranking
global.
• Otro problema que se puede presentar son los documentos muy populares que
pueden generar una carga mal repartida.
En el punto (4), se tiene una version de lo anterior que resuelve la inconsistencia en el
ranking.
El (5) es un ındice particionado por lexico.
• Para consultar se pide a cada procesador que resuelva las palabras de las es res-
ponsable y luego coopera para integrar los resultados
• Para consultas cortas maximizar la cantidad de respuestas posibles en un segundo,
pero el tiempo de respuesta puede no variar porque toda la consulta la sigue
resolviendo un procesador.
• Para el caso de consultas complejas, tiene el problema de enviar demasiada infor-
macion por la red ( caso modelo booleano). Mismo algoritmo que con las listas.
• En el modelo vectorial es problematico con exactitud por la misma razon que
cuando se cortaba el recorrido de las listas invertidas
• Para la Web es bueno porque la mayorıa de las consultas son cortas y suele haber
congestion, de modo que escala en forma casi ideal.
• Un problema posible son los terminos muy populares que pueden generar una
carga mal repartida.
La ultima variante es un ındice centralizado (construido en forma distribuida), que
puede ser replicado en todos los procesadores.
38
• Solo es factible si una maquina puede manejar toda la coleccion
• Permite repartir idealmente el trabajo y es tolerable a fallas.
Figura 2.15: Indexacion de la Web: (1) Se analizan y extraen los links de las paginas. (2)
Se crean ındices parciales en caso de ausencia de memoria principal. (3) Los ındices son
fusionados para formar el ındice invertido completo. (4) Analisis off-line para rankear los
enlaces.
2.4.9. Otros tipos de ındices
El ındice invertido suele imaginarse y implementarse con el uso de lista enlazadas y
arreglos. Pero estas estructuras no son muy eficientes a la hora de buscar sobre ellas. Es por
ello que existen otras estructuras con las cuales se puede implementar ındices, con mejor
eficiencia en la busqueda.
Estas son:
Trie (arbol digital) y arbol de sufijos
Se forma un arbol binario, con todos los sufijos del texto.
Busqueda simple en tiempo O(m).
Cada nodo es un intervalo en el arreglo de sufijos.
39
El arbol comprime caminos unarios, O(n) espacio y tiempo de construccion (arboles
Patricia).
Ocupan mucho espacio, 8 a 12 veces el tamano del texto.
Malos en memoria secundaria.
Puede utilizarse la idea para busqueda secuencial en el vocabulario.
Solucion : eliminar el arbol y quedarse con las hojas (espacio 1 a 4 veces el texto).
Figura 2.16: Arbol de sufijos - Arreglo de sufijos.
Arreglos de sufijos
Es un ındice que no necesita que es texto este formado por palabras.
Es capaz de recuperar subcadenas del texto, buscar expresiones regulares y realizar
busquedas aproximada en tiempo sublineal.
Es ideal para la biologıa computacional, lenguajes orientales, etc.
En la recuperacion de la informacion, puede ser util para:
• Analisis linguıstico especializado (por ejemplo, encontrar la autocorrecion mas
larga de una coleccion)
40
• Busqueda de frases de varias palabras, siendo mas rapido que un ındice invertido
• Busqueda de patrones que trascienda palabras (por ejemplo el ındice invertido no
permite detectar errores que involucren separadores)
El espacio que requiere es cercano al 40% del texto.
Es mas costoso de construir y mantener que el ındice invertido.
Es superior al ındice invertido para busqueda de patrones, pero no para el resto de
operaciones tıpicas en RI.
Arreglo de sufijos: Estructura
El arreglo de sufijos es simplemente un arreglo con los punteros a todas las posiciones
de interes en el texto.
Cada posicion define un sufijo del texto.
Figura 2.17: Sufijos del texto
En el arreglo, las posiciones estan ordenadas lexicograficamente por los sufijos.
Arreglos de sufijos: Busqueda
Todo substring del texto es el prefijo de un sufijo.
41
Figura 2.18: Arreglo de sufijos
La relacion prefijo se puede traducir a relaciones de orden lexicografico:
x : a prefijo de y ⇐⇒ (x : a ≤ y) ∧ (y < x : (a + 1))
Por lo tanto, basta un par de busquedas binarias en el arreglo de sufijos para obtener
el rango del arreglo que contiene todas las ocurrencias de x (en tiempo logarıtmico).
Figura 2.19: Arreglo de sufijos, busqueda
En memoria secundaria la busqueda binaria puede resultar costosa. El problema no es
tanto el acceso al arreglo sino a las posiciones aleatorias del texto.
Se puede usar supraındice en RAM para reducir ese costo.
Un supraındice interesante puede ser el mismo vocabulario.
42
Figura 2.20: Arreglo de sufijos usando supraındice
Figura 2.21: Arreglo de sufijos usando el vocabulario como supraındice.
En este caso la estructura es muy similar a un ındice invertido para la busqueda de
patrones (con inversion).
Arreglo de sufijos: Construccion
En principio no es mas que ordenar un arreglo.
Sin embargo, se puede aprovechar la estructura del problema: los sufijos son sufijos de
otros sufijos.
Existen algoritmos (Manber Myers) que en promedio toman tiempo O(n log log n).
43
Sin embargo, el verdadero problema aparece en memoria secundaria, por los accesos
aleatorios al texto.
La mejor solucion O((n2/M)) es la siguiente:
• Cortar el texto en bloques que se puedan indexar en memoria.
• Traer el primer bloque, construir su arreglo y mandarlo a disco.
• Al procesar el bloque i, el invariante es que el arreglo de sufijos para los i-1 bloques
anteriores estan construidos.
• Traer el bloque i-esimo y construir su arreglo de sufijos.
• Leer el texto de los i-1 bloques anteriores y buscar cada sufijo en el arreglo del
bloque i-esimo
• Determinar ası cuantos sufijos del arreglo grande van entre cada par de posiciones
del arreglo chico.
• Realizar el merge secuencial de los arreglos con esa informacion.
El metodo se adapta de manera facil para actualizar el ındice.
2.4.10. Ranking basado en texto
La tecnica estandarizada para el rankeo de los documentos de acuerdo a una consulta, es
el modelo espacio-vector. en este modelo, tanto el documento como la consulta misma son
vistos como vectores en un espacio con dimension proporcional al tamano del vocabulario.
En un espacio con las caracterısticas recien mencionadas, la similitud entre una consulta y
un documento esta dada por una formula que asigna un peso a cada vector y luego calcula
el coseno del angulo formado entre los pesos de ambos:
sim(q,d) =Σtwt,q×wt,d√
Σtw2t,q×√
Σtw2t,q
44
La tecnica de los pesos usa propiedades estadısticas del texto y la consulta para dar
mayor relevancia a ciertas palabras a la hora de hacer el calculo de similaridad. El esquema
de pesos mas usado es TF-IDF, que usa la frecuencia de los terminos en ambas consultas
y documentos para computar el grado de similaridad. Por TF se entiende, frecuencia del
termino, y la idea es que si un termino aparece muchas veces dentro de un documento, el
termino sirve para dar la descripcion del contenido del documento. La frecuencia del termino,
TF, usualmente es normalizado con respecto al tamano del documento, esto es, el parametro
usado es la frecuencia del termino t dividido por la frecuencia del termino mas frecuente en
un documento d:
tf t,d =freqt,d
maxlfrecl,d
La parte IDF del esquema, hace caso a la frecuencia invertida del documento y refleja que
tan frecuente es un termino en toda la coleccion. Lo racional es que un termino que aparece
en unos pocos documentos da mayor informacion que un termino que se repite en la mayorıa
de los documentos. Si N es el numero de documentos y nt el numero de documentos que
contienen la consulta del termino t, entonces :
idft=log Nnt
Usando esta medida, el peso de cada termino esta dado por la siguiente formula:
wt,q=(12
+ 12tft,q)idft, wt,d=tft,d
El factor 1/2 es agregado para anular el termino de consulta con peso 0. Varios esquemas
del peso han sido propuestos como alternativa, pero el esquema recien explicado es uno de
loas mas usados y en la practica entrega buenos resultados.
2.5. Conectividad basada en el ranking
Los enlaces en la red o Web, proveen una valorable fuente de informacion. En este contex-
to, el numero de paginas es demasiado grande y no existe un patron de medida que apueste a
45
la calidad de estas paginas, por lo cual, los enlaces pueden ser considerados como una medida
colectiva y emergente de calidad.
Es conocido que las paginas Web que comparten links son mas probables a tener una
relacion tematica, a no tenerla. La clave de esta asumicion de la conectividad basada en el
ranking va mas alla, y acierta a que un hipervınculo desde la pagina p’ hacia la pagina p,
significa de cierta manera, que el contenido de la pagina p esta endosado por el autor de la
pagina p’ Varios algoritmos para la conectividad del ranking se basan en esta asumicion, la
cual puede ser particionada en:
Consulta dependiente del ranking, asignando un puntaje a cada pagina de la coleccion.
Consulta independiente del ranking, o ranking dependiente del tema, asigna un puntaje
a cada pagina de la coleccion en contexto a cada consulta.
2.5.1. Consulta dependiente del ranking
El primer metodo basado en la dependencia del ranking fue llamado Hyperlink Vector Vo-
ting (HVV), y fue introducido por Li. El metodo HVV combina la relevancia entre el ranking
y la calidad de este. No solo se basa en la cantidad que un termino aparece en un documento
sino que tambien se considera la cantidad de enlaces que apuntan hacia el documento, o como
otra personas describen el documento y cuanta gente lo cita, haciendo analogıa a el metodo
del espacio vectorial, en este caso, el documento esta representado por cero o mas vectores.
Donde cada vector representa el numero de links que apuntan hacia el documento en cuestion.
Pagerank:
El algoritmo Pagerank (PG), introducido por Lawrence Page y Sergey Brin en 1998, es
actualmente una parte importante de la funcion de ranking que usa el conocido motor de
busqueda Google. El algoritmo es de tipo recursivo, basandose en una simple idea una pagina
con algo Pagerank es una pagina referenciada por muchas otras paginas con alto puntaje de
46
Pagerank. Pagerank es visto como la recursividad del metodo HVV.
En la publicacion de Page y Brin dieron una intuitiva justificacion a este algoritmo. Ellos
consideraron a Pagerank como un modelo que refleja el comportamiento del usuario, donde el
navegador hace click en los enlaces en forma aleatoria, sin fijarse hacia que tipo de contenido
apuntan.
El navegador aleatorio visita paginas web con una cierta probabilidad que se deriva en
el Pagerank de la pagina. La probabilidad que un usuario seleccione un enlace en la pagina
esta relacionado por el numero de enlaces que esta pagina posea.
De esta manera, la probabilidad que una persona no se detenga de hacer clicks en los
enlaces, esta dada por el factor de amortiguacion d. La justificacion a esto, es que el usuario
no navega solo siguiendo los enlaces en forma infinita, sino que se aburre y salta en forma
directa a otras paginas en forma totalmente aleatoria.
Por lo tanto el valor PG de una pagina T, es definido como la probabilidad de que un
usuario llegue a la pagina T, haciendo clicks a traves de los enlaces. Y para el caso en que
una pagina sea accedida en forma directa (por la URL), tambien existe una probabilidad
mınima, la cual corresponde a (d-1) en la formula de PG
El algoritmo de Pagerank fue descrito en la publicacion de Google [2], y este esta dado
por la siguiente ecuacion:
PR(A) = (1− d) + d(PR(T1)C(T1)
+ ... + PR(Ti)C(Ti)
+ ... + PR(Tn)C(Tn)
)
donde,
PR(A) es el Pagerank de la pagina A.
PR(Ti) es el Pagerank de la pagina T − i que tiene un enlace que apunta a la pagina
A. 0 < i < n donde n es el numero de paginas que apuntan a A.
C(Ti) es el numero de enlaces que salen de la pagina Ti
d es un factor de amortiguacion, el cual se inicializa entre 0 y 1. Es usado para que el
promedio de los Pagerank converja a 1.
47
Como se ve en la formula, este algoritmo no rankea la web como un todo, sino que lo hace
en forma individual para cada pagina. De esta forma el valor Pagerank de la pagina A es
recursivamente definido por el Pagerank del resto de las paginas que apuntan hacia A.
Los valores Pagerank de las paginas Ti que enlazan a la pagina A no influyen en el valor
final de Pagerank de A. Dentro de este algoritmo, el Pagerank de una pagina Ti siempre
es medido en funcion de su numero de enlaces salientes, esto significa que una pagina Ti
mientras mas enlaces salientes tenga, menos beneficios dara a una pagina A, que contenga
un enlacen proveniente de Ti[6].
Por otro lado, un enlace entrante a una pagina A siempre incrementara el valor Pagerank
de la pagina A.
Finalmente la sumatoria de todos los pesos de las pagina es multiplicado por el factor de
amortiguacion d, con el fin de reducir los valores y la probabilidad.
48
Capıtulo III
La Web Chilena
La Web Chilena
3.1. Caracterısticas de la Web Chilena
Para lograr los objetivos demandados en el presente trabajo, se debe conocer que carac-
terıstica presenta la Web chilena, pues es el dominio quien alberga a el dominio umag.cl
Como fundamento a este capıtulo se considerara el estudio [3] realizado por CIW (Centro
de Investigacion de la WEB) a la Web Chilena en el ano 2006.Del analisis de este estudio se
destacaron las siguientes observaciones:
La Web chilena esta compuesta por mas de 170.000 sitios, y estos sitios contienen mas
de 7 millones de paginas. Muchas de sus caracterısticas son muy similares a las de la
Web global en general.
Un 14% de los sitios estan conectados entre sı a traves de enlaces y tienen el 53,3% de
las paginas. Por otro lado, un 49,5% de los sitios esta completamente desconectado en
terminos de enlaces, pero representan solo el 14% de las paginas.
Un sitio promedio tiene 43 paginas, contenidas en 0,304 MB, con 1,56 referencias desde
otros sitios.
Un dominio promedio tiene 1,08 sitios y 46,61 paginas, contenidas en 0,328 MB.
Cerca de 1/4 de las paginas chilenas fue creada o actualizada en el ultimo ano, lo que
implica un alto grado de crecimiento y dinamismo.
Alrededor del 80% de las paginas de Chile esta en espanol y cerca de un 17% en ingles.
Otros idiomas tienen una presencia muy leve.
Los sustantivos que mas aparecen en la Web chilena son: Chile, producto, usuarios,
servicio y mensaje. Tambien aparecen Santiago, Web, blog, region e informacion.
50
Los paıses mas referenciados desde Chile son Argentina, Espana, Alemania, Reino Unido
y Mexico, y en general el numero de referencias a paıses extranjeros esta relacionado
con el volumen de intercambio comercial.
Los sitios que reciben mas enlaces son sii.cl, uchile.cl, mineduc.cl, meteochile.cl y bcen-
tral.cl.
Los proveedores de hosting con mayor numero de sitios son IFX Networks, VirtuaByte,
T-Chile, Telefonica Internet Empresas, DattaWeb y PuntoWeb.
Respecto a la calidad de las paginas y sitios:
El 20% de sitios mas grandes en tamano contiene el 99% de la informacion en la Web
chilena.
Cerca de un 21% de los sitios de Chile no son faciles de encontrar ya que estan hechos
con tecnologıas no visibles para los motores de busqueda, como Flash y Javascript.
Unas pocas paginas acaparan la mayorıa de los enlaces. De hecho, solo un 3% de las
paginas tienen algun valor de contenido en terminos de estar referenciadas desde otros
sitios. Sin embargo, estas paginas estan repartidas en el 35% de los sitios Web.
Cerca de un 5% de los enlaces ya no existen.
Respecto a las tecnologıas Web:
De los servidores que entregan informacion, el servidor Web mas utilizado es Apache
con 66,7%, seguido con un 32,8% por Microsoft Internet Information Server.
De los servidores que entregan informacion, el sistema operativo mas utilizado es Unix
con 48,5%, seguido por Microsoft Windows con 38,5%. Ademas, Linux es utilizado en
un 12% de los servidores.
51
El generador de paginas dinamicas mas usado es PHP con un 75% de participacion en
el mercado.
El formato de documentos mas usado es PDF con un 53% de participacion, seguido
por XML con un 21%.
Aproximadamente hay una disponibilidad del doble de archivos con paquetes de sof-
tware para Linux que para Windows en la Web chilena.
52
Capıtulo IV
Un motor de busqueda para umag.cl
Un motor de busqueda para umag.cl
En el capıtulo anterior se estudio la teorıa de estructuras y modelos usados por los mo-
tores de busqueda en general, para dar paso en el presente capıtulo, la solucion al problema
planteado en el capıtulo 1, la implementacion de un motor de busqueda para el dominio
umag.cl.
Siguiendo los pasos y fases comunes de un motor de busqueda, es como se define el diseno
para este caso en particular.
Es por lo anterior y, tambien con el fin de mantener cierto orden en el desarrollo, una
buena planificacion y un buen entendimiento de los procesos que implica la implementacion
de un motor de busqueda, se da inicio a este capıtulo planteando el siguiente diagrama:
Figura 4.1: Diagrama del diseno de un motor de busqueda para umag.cl
54
De esta manera, a medida que se vaya avanzando en el capıtulo se ira explicando el
desarrollo de cada uno de los pasos que presenta el diagrama.
4.1. Recoleccion en umag.cl
Para esta primera parte del motor de busqueda ( (1) en el diagrama), la recoleccion,
se hace uso de un crawler o spider, el cual recorre la Web parametrizada de acuerdo a su
configuracion.
En este caso se decidio hacer uso del sistema WIRE (Web Information Retrieval Environment)[4],
un crawler desarrollado por CIW, especıficamente el Dr. Carlos Castillo. Algunas de las cosas
que permite este sistema son:
Crear colecciones de documentos Web en un formato simple.
Recolectar la Web.
Generar estadısticas.
Generar reportes.
Y sus principales caracterısticas son:
Escalable : Disenado para trabajar con grandes cantidades de documentos, y probado
con millones de documentos.
Escrito en c/c++
Permite personalizar las opciones de recoleccion vıa un archivo XML
Posee herramientas de analisis, extraccion de estadısticas, y generador de reportes
Es Codigo-abierto, una de las principales razones por la que decidio su uso.
Funcionamiento del Crawler Son varias las tareas que debe realizar el crawler, por
esta razon esta dividido en 4 modulos de procesos:
wire-bot-seeder: Agrega URL para ser recolectadas.
55
wire-bot-harvester: Descarga los documentos y realiza desambiguacion.
wire-bot-manager: Estructura las descargas.
wire-bot-gatherer: Analiza en busca de nuevas URL.
Este proceso suele producirse en ciclos para abarcar toda la profundidad de los sitios.
Recolectando umag.cl
La recoleccion fue hecha en Noviembre de 2007, utilizando un computador con procesador
Intel Pentium IV 3,6 GHz y 1 GB de RAM, bajo sistema operativo Ubuntu 7.04 Feisty Fawn
Linux.
Un ciclo de recoleccion comienza descargando un conjunto de direcciones iniciales (seeds),
que fueron especıficadas en un comienzo. De las paginas descargadas se extraen nuevos en-
laces, de los cuales se discriminan aquellos apuntan a paginas o documentos en fuera del
dominio umag.cl Para la esta recoleccion se usaron 4 ciclos.
Algunos de los datos obtenidos una vez terminado el proceso, fueron:
Sitios encontrados 13
Documentos encontrados 8564
Documentos descargados 6322
Documentos OK 5439
Tiempo transcurrido 3,345 Hrs
Es importante recalcar que la cantidad de documentos recolectados no refleja el total
de los documentos existentes bajo umag.cl, debido a que existen sitios islas que no fueron
considerados en los seeds.
Con la informacion de los enlaces entrantes y salientes de las paginas se puede realizar
una representacion grafica de la distribucion del dominio, lo cual se observa en la figura 23,
y por cierto este es muy similar al modelo macroscopico que presenta la Web chilena y Web
en general.
56
Figura 4.2: Distribucion de los enlaces en umag.cl
Una vez hecho lo anterior, ya se dispone de la coleccion de documentos, los cuales a traves
de una herramienta de exportacion de WIRE, pueden ser extraıdos a formato txt, para su
visualizacion o tambien pueden ser usados los archivos binarios originales generados por el
crawler.
Con fines practicos, se decidio exportar los archivos. De esta manera, cada documento se
traduce a un archivo unico, que lleva como nombre el id del documento.
Aparte de los documentos, tambien se dispone del resto de informacion necesaria para
luego formar el ındice y el ranking, tal como links entrantes y salientes de cada uno de los
sitios encontrados, tamano, etc. Estos seran mejor descritos en su respectivo momento del
presente capıtulo.
57
4.2. Normalizacion
El proceso de normalizacion ( (3) en el diagrama ) consiste en dar formato legible al
computador de los documentos de la coleccion, esto es, quitar etiquetas HTML, espacios,
saltos, y stopwords. Con fines de simplicidad se omitio la lematizacion comentada en uno de
los capıtulos anteriores.
Como producto final cada documento sera representado por un conjunto de palabras que
juntos pasaran a ser el vocabulario del ındice final.
Para normalizar los documentos, en la implementacion se hizo uso de analizadores lexicos
, los cuales a traves de reglas de filtro se eliminan cada una de las etiquetas no deseadas.
Los analizadores lexicos fueron implementados en Flex, herramienta que traduce cada
una de las especificaciones, y luego genera un codigo en lenguaje C.
En su implementacion, se generaron tres analizadores, que corresponden a los siguientes
archivos lex:
1. normaliza1.lex: analizador para filtrar etiquetas, espacios, saltos de lıneas, y codigo
HTML en general. Luego que los documentos pasan por este filtro, se obtiene cada uno
de los documentos normalizados, sin etiquetas y con solo un espacio entre cada palabra.
2. normaliza2.lex: analizador encargado de juntar las palabras de cada uno de los docu-
mentos en un solo archivo, que contiene todas las palabras inclusive las repeticiones de
estas(datos.txt). A su vez quita minusculas y acentos a las palabras. A medida que las
palabras son escritas en el archivo final, se agregan etiquetas con el id del documento al
cual pertenecen, el id tambien es igual al nombre del archivo. Para la ejecucion de este
proceso sobre todos los documentos se uso un script de shell (bash).
3. normaliza3.lex: archivo usado para generar codigo C que luego se incluye en el indexador,
con el fin de ir leyendo el archivo que contiene los terminos de cada uno de los documentos
y simultaneamente ir creando el ındice invertido en memoria.
58
Figura 4.3: Normaliza1: normaliza el texto
4.3. Ranking
Para dar relevancia a los documentos recolectados y generar un ranking, que luego se
reflejara en las respuestas a las consultas, se decidio hacer uso del modelo que plantea Pa-
gerank. Para concretar esto es necesario la informacion de los links que posee cada pagina
recolectada.
Para extraer el detalle de los links de cada una de las 8564 paginas guardadas, se uso la
herramienta disponible de WIRE, wire-info-extract –links y fueron guardados en el archivo
links.txt
Una vez hecho, se debıa implementar la funcion de PG, por lo que este fue desarrollada
en el programa pagerank.c, de la siguiente manera:
de acuerdo a la estudiado en la formula de PG, se dispone de un sistema de ecuaciones
de n x n donde, n corresponde al numero de archivos recolectados.
para este caso donde n es igual a 8564, en terminos de recursos (memoria RAM) esto
bastarıa implementando un arreglo de flotantes de n x n.
59
Figura 4.4: Normaliza2: separa texto.
pensando que a lo largo del tiempo el numero de n debe aumentar, se decidio imple-
mentarlo con una estructura llamada pagerank.
Estructura Pagerank:
La estructura se compone de :
long int n, numero de documentos
long int **a, puntero a puntero, con asignacion de memoria, n punteros a n punteros, un
vector que representara las conexiones como vertices en un grafo
int *c, vector numero de links salientes de cada documento (Ti)
float *rank, vector de los valores PG de cada uno de los documentos
Una vez conociendo el tamano n y inicializada el tamano de la estructura, se procede a
leer las relaciones entre los links, del archivo links.txt, y almacenarlos en el vector a de la
estructura pagerank.
Despues ya teniendo el vector cargado, se guarda el numero de links salientes de cada
documento ( C(Ti) de la formula) en el vector c de la estructura.
60
Para resolver el sistema de ecuaciones, en este caso:
rank(Tj) = (1− d) + d( rank(T1)C(T1)
+ ... + rank(Ti)C(Ti)
+ ... + rank(Tn)C(Tn)
)
con, i 6= j , para i, j ∈ [1, n]
es necesario inicializar todas las incognitas (valores de rank) en 0,1, y luego , iterar N
veces con el fin de amortizar los resultados. El numero de iteraciones asignadas fue 10 y el
factor de amortiguacion, d igual a 0,85. O sea el valor mınimo PR para una pagina sera 0,15.
Este proceso genera un archivo pagerank.txt que asocia a cada documento con su valor PR.
4.4. Indexador
El proceso de indexacion (4), es el mas complejo de todos los procesos, pues se debe:
crear estructuras de datos (lista enlazada) en memoria.
indexar las palabras sin repeticion, a la lista de palabras. Se omiten los stopwords
ingresar el posteo en la lista de ocurrencia de cada termino, junto con asignar el valor
pagerank del respectivo documento.
revisar si el posteo de un termino se repite en el mismo archivo o documento.
contar la cantidad de veces que aparece el termino en todos los documentos.
luego, de agregar todos los terminos y sus respectivas ocurrencias, grabar el ındice en
disco.
En cuanto a la implementacion esta fue hecha en un solo el archivo, usando lenguaje C,
el codigo generado por Flex (normaliza3.lex ), y tambien la liberarıa estandar de plantillas
(STL) de C++.
1. En principio el archivo indexer.cc, entre su archivos de cabecera incluye el archivo
lex3.yy.c, luego abre los archivos, datos.txt, stopwords list.txt, pagerank.txt.
61
2. se hace uso de tres contenedores asociativos de STL , dos set de nombres stopwords y
palabras, para ir almacenando los stopwords y terminos, respectivamente, y uno de tipo
map, que asocia un valor pagerank a cada documento.
3. una vez cargadas todas las palabras stopwords en el contenedor, a traves del codigo
lex3.yy.c y usando la variable yytext (lee tokens) se procede a leer el archivo de todos
los terminos, termino por termino, hasta llegar al final del archivo.
4. se lee un termino y se consulta su existencia en el contenedor de stopwords, si este no
existe se continua con el paso 5, de otra manera se lee otro termino (paso 4).
5. el termino leıdo, es insertado en un contenedor de palabras, en caso de no existir (procede
paso 6), de lo contrario se salta al paso 7.
6. se llama a la funcion insertion sort, y se inserta el termino en la lista de terminos del
ındice, en su posicion correspondiente (orden lexicografico), luego se retorna al paso 4.
7. al estar el termino dentro del contenedor significa que ya se ha incluido dentro del ındice,
por lo cual ahora se llama a la funcion add doc, la cual busca el termino dentro del ındice,
cuando encuentra el nodo del termino en cuestion, agrega a su lista de posteo el id del
documento de ocurrencia y su respectivo peso. En caso de ya existir el id de documento,
solo se incrementa el campo num oc del nodo. Luego se retorna al paso 4.
8. finalmente, una vez que se leyeron todos los terminos, el ındice invertido estara creado
en memoria, por lo que ahora se procede a guardar el ındice en un archivo binario en
disco (index.dat).
Luego del proceso de indexacion se dispone del la estructura ındice invertido guardada en
disco, la cual puede ser recuperada en cualquier momento. Por motivos que seran explicados
en la proxima seccion, se implemento un programa split index, que carga en memoria el
ındice en index.dat, y luego, separa la lista de termino de la lista de ocurrencias en dos
archivos (term list y post list).
Para mantener la relacion termino - lista de ocurrencia, a cada termino de la lista le es
62
agregado un indicador de posicion (idpos oc) de su respectiva lista de posteo en el archivo de
posteos, post list.
4.5. Buscador
Este proceso (5), se ejecuta concurrentemente online cuando los usuario realizan las con-
sultas. Y es el encargado de recuperar la informacion solicitada.
Los dos mayores intereses en este proceso son la eficiencia en tiempo de respuesta y la
concurrencia, los cuales sin duda depende de multiples factores, algunos de estos son:
1. Distribucion de los archivos del ındice invertido.
2. forma en que se acceden a las estructuras.
3. estructuras en memoria primaria o secundaria.
4. dependencia de hardware.
Soluciones tomadas:
para (1), tal como se vio en la seccion anterior, se han separado la estructuras en distintos
archivos, doc url.dat, index.dat. con el fin de hacer mas rapido el acceso a sus datos.
para (2) y (3), se plantea como solucion usar una parte en RAM y la otra en disco,
la parte mas concurrente o a la que acceden todas las consultas es la lista de terminos
(archivo term list), por lo que lo ideal es mantenerla en memoria, mientras que las listas
de posteo (archivo post list) se almacenen y accedan en el disco.
Este proceso de busqueda o programa que realiza esta, sera ejecutado desde CGI(Common
Gateway Interface) en un servidor Web Apache, el cual crea hilos de procesos para su ejecucion
concurrente. Si se considera cargar en memoria la lista de termino para cada una de los hilos
de consultas esto no seria para nada efectivo pues, se traducirıa a leer por completo las lista
para cargarla en memoria, mas el tiempo que se tarda en recuperar la informacion de la
busqueda, y sin duda que en un cierto numero de consultas concurrentes la memoria no darıa
63
abasto. Es por esto que, se plantea hacer uso de memoria compartida para que solo una vez
se cargue la RAM.
4.5.1. Memoria compartida
Memoria compartida es memoria primaria, RAM, que da la posibilidad que multiples pro-
cesos o programas puedan acceder a una seccion de memoria en comun. El sistema operativo
es quien se encarga de gestionar este recurso a traves de tablas, asignandole un identificador
de memoria a cada proceso, y permisos respectivos. En general la administracion de esta
memoria es muy similar al sistema de archivos en Linux, donde el acceso es limitado con
permisos.
Para la implementacion de esta etapa, fue declarado una bloque de memoria compartida
suficientemente grande de modo que la lista completa de terminos calce dentro de ella. Por
esto mismo solo se utilizo solo un identificador de memoria. Al usar un solo bloque o piscina
de memoria esta puede ser tratada como un arreglo, pues es memoria contigua, y ası ser
accedida en forma directa a traves de ındices.
Desglosando el buscador, este se divide en tres partes:
1. un cargador de lista en memoria RAM, que no es mas que una programa que lee la lista
de terminos ( term list) y la carga en memoria compartida. Hay que recalcar que solo
la carga y no la libera, por lo que para que inicie el motor de busqueda basta con solo
ejecutar una vez este programa.
2. una funcion que extrae el o los terminos ingresados en la consulta a traves de la interfaz
HTML del buscador, para este caso por medio del metodo GET. Conjuntamente estos
terminos son analizados, reemplazando mayusculas, quitando caracteres ASCII que no
pertenezcan al abecedario espanol, etc. La consulta es guardada en una estructura query,
compuesta por un vector que guarda cada uno de los terminos y un valor entero que
representa la cantidad de terminos en la consulta.
3. y el buscador, es quien responde a las consultas recuperando la informacion desde la
64
memoria compartida y el disco. Para la ubicacion de un termino en la lista se usa el
algoritmo busqueda binaria sobre el bloque de memoria compartida.
4.5.2. Proceso de busqueda:
Figura 4.5: Proceso de busqueda. 1: se recupera los terminos de la consulta usando CGI. 2:
busqueda binaria de cada uno de los terminos y son almacenados en estructura respuesta. 3:
Se ordenan de acuerdo a relevancia y cantidad de aciertos de los terminos para luego entregar
respuesta HTML.
Cuando se realiza una consulta, primero se extrae la consulta desde el form y guardados
en la estructura query (2), para ası luego, recien comenzar la busqueda en si, la cual se puede
describir del siguiente modo:
se realiza la busqueda binaria, sobre memoria compartida, de cada uno de los n terminos.
Cuando el termino es encontrado, se usa el identificador de posicion idpos oc, para
acceder a la lista de ocurrencia del termino y ası recuperar los documentos (id doc).
65
cada id doc es almacenado en una estructura de datos (response), una lista de todos los
documentos de ocurrencia de la consulta, donde en una variable num ocse va registrando
si un id doc se repite, o sea que varios terminos estan en el mismo documento.
cuando se logra recuperar todos los posteos de los terminos, estos son ordenados des-
cendente de acuerdo a su peso PG.
luego, la lista de respuesta es recorrida, y se compara si num oc es igual a n (numero
total de terminos), si es igual entonces significa que ese documento posee todos los
terminos y este id es devuelto.
4.6. Comportamiento y resultados
Con motivo de evaluar el desarrollo del motor de busqueda, tanto la implementacion,
la distribucion de los archivos y funciones para futuras modificaciones a realizar. El com-
portamiento que desempeno el programa versus los objetivos a alcanzar, declarados en un
principio. Y rescatar las cosas positivas como tambien las que debieran modificarse en trabajo
futuros con el fin obtener un mejor desempeno.
En las siguientes secciones se detallara lo recien mencionado.
Ranking
En la designacion de relevancia de los documentos utilizando Pagerank, se generaron los
5 primeros documentos con mayor valor PR.
Pagerank URL
199.15 kataix.umag.cl/∼mmarin/topinf/php/manual.html
28.88 kataix.umag.cl/caa/fotosparrillada/index.htm
27.91 www.dic.umag.cl/caaieci/fotos parrillada/index.htm
24.58 hain.umag.cl/∼topinf 5/2004/TOPICOSC/notas-curso-BD/node1.html
23.38 hain.umag.cl/∼topinf 5/2004/TOPICOSC/notas-curso-BD/node218.html
66
Estas paginas corresponden a documentos que tienen demasiados links que apuntan a ella
misma, para los principales motores de busqueda estas paginas son consideraras como link-
farm[2], granja de links , y por esto mismo son sancionadas en tu valor PR, o excluidas del
ındice. De forma similar se deberıa proceder para este caso, pues en muchos caso debido al
valor PR que tienen estos documentos seran los primeros en aparecer en ciertas busquedas,
sin talvez tener mucha relevancia con respecto a las otras paginas.
Otras posible solucion al problema de las granjas de links, es usar otro metodo para
asignar la relevancia de las paginas, Authority ranking[thesis], parecido a Pagerank pero que
usando una heurıstica de Bharat, descarta los links internos de los sitios. (Trabajo futuro)
Recoleccion
Luego de la recoleccion, se logra hacer cierta analogıa de la web bajo umag.cl y la web
Chilena. De modo que la web en umag.cl:
tiene gran porcentaje de deformacion y ausencia de etiquetas HTML, siendo la principal
la etiqueta < tittle >, la cual solo esta presente menos del 50% de la paginas recolec-
tadas. Y de ese porcentaje solo un 40% tiene algun titulo valido, mientras que el resto
esta vacıa o tiene como titulo New Document.
tiene un modelo macroscopico a menor escalar debido a la poca cantidad de sitios
resuelto (solo 12). Pero de igual manera existen los sitios islas, principales, y tentaculos.
en total se recolectaron 34Mb en paginas HTML.
el sitio con mayor tamano fue www.umag.cl, con 3,9Mb. Y los con menor, www.sid.umag.cl
y enlaces.umag.cl, cada uno con 3,7Kb.
el tamano promedio de una pagina en umag.cl, es 6,46Kb.
las paginas en ingles tambien estan presentes en umag.cl, pero en menor que el promedio
de la Web en Chile, aquı representa menos del 5% de la web
67
En esta seccion tambien se debe concluir que es preciso adaptar el sistema WIRE con el
Normalizador y Indexador, de modo de poder actualizar el ındice de terminos y lista de ocu-
rrencias. Lo cual no tendrıa que implicar mucho trabajo pues con esta idea la implementacion
fue modular.
Normalizacion
En la etapa de post-recoleccion, analisis y normalizacion, se dio cuenta de lo complicado
que fue normalizar el texto de los documentos, ya que existen demasiadas inconsistencias,
tales como:
etiquetas HTML no cerradas, repetidas, ausentes, etc. Para esto se tomaron algunas
medidas como considerar las etiquetas repetidas y con malformaciones.
distintos tipos de codificacion de caracteres en los documentos, siendo las principales
ISO-8859-1(Occidental) y Unicode (UTF-8), aunque existen varias mas. Con estas dos
las mas usadas, se complico el proceso para el caso de caracteres especiales.
presencia de otros tipos de lenguajes incrustados en medio de HTML, javascript, xhtml,
etc.
Pero dentro de lo posible se logro una buena normalizacion, ya que lo mas importante fue
logrado, esto fue, eliminar todo tipo etiquetas HTML, separar los terminos del texto, y
eliminacion de caracteres extranos.
Indexacion
Por otro lado el uso de lista enlazadas para la construccion del ındice sin duda no fue la
mejor seleccion, ya que :
para la insercion de un nuevo termino se debıa recorrer secuencialmente la lista.
para la insercion de una nueva ocurrencia de un termino, se busco en forma secuencial,
traduciendo la creacion del ındice invertido en un tiempo de 3 hrs. y fraccion para,
68
589282 ocurrencias y 42378 terminos.
Aunque el tiempo de creacion es alto, se debe considerar que la web bajo umag.cl, no tiene
gran tendencia a aumentar en demasıa, por lo que solo se solo debiera ser creado en un inicio
y luego el ındice debiera ser actualizado.
Busqueda
Con objetivo de evaluar el comportamiento de busqueda se efectuaron las siguientes con-
sultas: “Departamento de computacion”, “Vicerrector Academico”, “postulacion
a credito fiscal”.
1. consulta “Departamento de computacion”: se espera llegar a la pagina del Depar-
tamento de Computacion.
posicion URL
1 www.umag.cl/biblioteca/informacion general/politicas.htm
2 kataix.umag.cl/dic/directorio.html
3 kataix.umag.cl/dic/carreras profesionales.html
4 kataix.umag.cl/dic/galeria.html
5 kataix.umag.cl/dic/memorias.html
6 kataix.umag.cl/dic/eventos destacados.html
7 kataix.umag.cl/dic/caa.html
8 kataix.umag.cl/dic/reportes tecnicos.html
9 kataix.umag.cl/dic/publicaciones.html
10 kataix.umag.cl/dic/grupos investigacion.html
En los diez primeros resultados se obtienen documentos esperados, los cuales corres-
ponden al departamento de Computacion. La pagina retornada en la posicion 1, ya no
existe, es por esto que con fines de demostrar que los terminos estan presentes, al costa-
do de cada respuesta se puso un link [cache] que abre el documento que fue recolectado
por el crawler.
69
2. consulta “Vicerrector Academico”: se espera llegar a algunos documentos que nos
indiquen quien es el Vicerrector Academico.
posicion URL
1 hain.umag.cl/∼topinf 5/l/2004/srdfinal.html
2 hain.umag.cl/∼topinf 5/l/2004/srd2.html
3 hain.umag.cl/∼topinf 5/l/2004/srd.html
4 hain.umag.cl/∼topinf 5/l/2004/urd2.html
5 hain.umag.cl/∼topinf 5/l/2004/urd.html
6 www.umag.cl/historia/organizacion.php
7 kataix.umag.cl/dic/ficha carias.html
8 www.umag.cl/mecesup/mag/mag0208.php
9 www.umag.cl/noticias/noticias.php?pag=2
Para esta consulta, recien en el la posicion numero 6 aparece el documento que supuesta-
mente se buscaba. Los 5 primeros resultados correspondes a paginas de una asignatura,
y aparecen primero por el hecho de tener mas Pagerank que el documento 6. Con esto
se puede concluir, lo que se planteo con anterioridad, respecto a la posible existencia de
granjas de links, y tambien el necesario analisis de otros factores para otorgar relevancia
a las respuestas, tales como las etiquetas de cabecera H1, H2, H3, TITLE, etc, para que
cuando los terminos buscados esten presenten en estas cabeceras se retorne primeros
esos documentos.
3. consulta “postulacion a credito fiscal”: el objetivos es dar con el sitio que tenga
informacion de las postulaciones a credito fiscal.
posicion URL
1 www.umag.cl/fondo solidario/cobranza credito/tipos credito.php
2 www.umag.cl/fondo solidario/aspectos legales/
3 www.umag.cl/fondo solidario/aspectos legales/index.php
70
Para esta consulta se propusieron 3 resultados, y todos ellos nos llevan a lo que se
buscaba.
A modo de ejemplo se expusieron solo 3 consultas, pero fueron muchas mas las consultas de
prueba que se hicieron. Todas las respuestas fueron consideradas como exitosas, ya que en
caso de existir informacion de la consulta buscada, esta fue posible recuperarla. Sin embargo,
el problema fue el ranking, en muchos casos se antepusieron documentos con alto Pagerank,
pero que no tenıan mayor relevancia. Estos documentos por general correspondıan a paginas
que se autoreferencias ( tienen links a si mismo), lo cual a la hora de hacer el ranking estos
alcanzaron grandes valores. Para solucionar este problemas bastarıa con excluir estas paginas
del ındice, o usar el tipo de ranking Authority.
Ya con los resultado presentados y analizados, es posible dar juicio al cumplimiento de las
metas que fueron expuestas en un principio de este documento. Con respecto a el objetivo
principal, es preciso decir que si fue cumplido, ya que se logro la implementacion de un motor
de busqueda, que permite recuperar los documentos bajo el dominio umag.cl.
Y por parte de los objetivos secundarios, cabe decir que las respuestas entregadas por
el motor de busqueda implementado y expuesto en el presente trabajo, tienen un efectivo
grado de relevancia por sobre los otros documentos, de acuerdo al modelo Pagerank. Pero sin
duda, siendo la relevancia algo mas o menos ambiguo e incierto, es posible que existan casos
donde las respuestas esperadas no esten dentro de las primeras. Para mejorar esta situacion se
deberıa considerar el resto de variables y factores incidentes en las respuestas y ser estudiadas
en un futuro trabajo.
Otro de los objetivos fue el de busqueda de frases, es decir, multiples terminos (no exactas),
esto tambien fue logrado exitosamente.
71
Capıtulo V
Conclusiones
Conclusiones
Siendo la recuperacion de la informacion un tema muy amplio, y especıficamente la recu-
peracion de informacion en la Web, relativamente emergente, es facil de dar con una gran
cantidad de documentacion al respecto, pero en aspectos generales, la mayorıa solo cubre el
tema en forma basica y general. Por esta razon en el presente trabajo, aparte del objetivo de
implementar un motor de busqueda, tambien se preciso en realizar una basta documentacion
del tema y estudiar en forma detallada el funcionamiento de los sistemas de busqueda y las
distintas posibilidades a optar para su implementacion.
Durante el desarrollo del trabajo, precisamente en el analisis de la informacion recolecta-
da, se reflejo cierta similitud entre la Web umag.cl y la Web en Chile, tanto en el esquema
de conectividad que ambos poseen, como tambien en su comportamiento y caracterısticas.
Teniendo como fundamento esto ultimo, es posible inferir, que la Web en umag.cl tiene una
tendencia, a crecer mas, que a disminuir, generando ası una mayor necesidad de un buscador
como el implementado.
En cuanto a la implementacion, se consiguio como producto final un Motor de Busqueda,
que permite la busqueda invertida de terminos sobre los documentos de umag.cl, es decir,
para cada consulta formada por terminos, estos son extraıdos, luego son buscados en el ındice
invertido, y se extraen solo los documentos ocurrentes de los terminos. La lista de documentos
resultante, es ordenada en forma decreciente de acuerdo al factor de relevancia, Pagerank,
y finalmente entregada en el mismo orden como respuesta final a la consulta. Deteniendose
en este punto, es preciso decir que al momento de realizar determinadas consultas y luego
estas ser evaluarlas, se pudo apreciar, que otorgar peso a los distintos documentos tiene un
relevante significado para el buscador, de modo de jerarquizar sus documentos y entregar los
resultados en funcion de esto, pero este orden de relevancia, no siempre se traduce en una
buena respuesta o respuesta esperada por el usuario. Es por esto, que se rectifica lo planteado
en el capıtulo 2, que no existe una respuesta correcta para todos los usuarios, teniendo cada
uno de ellos un perfil distinto, no es posible adivinar lo que cada usuario desea encontrar;
73
pero si tener talvez, una buena aproximacion, lo cual se logro con Pagerank, y tambien, puede
mejorar con otras variantes y complementos que son planteados en trabajos futuros.
Otro aspecto a recalcar, es el uso de memoria compartida en la implementacion del progra-
ma buscador, lo cual otorga gran grado de escalaridad al sistema para consultas concurrentes,
pues no es necesario cargar las lista completa de terminos para cada consulta, sino que la
lista es cargada en RAM solo una vez, y luego, accedida en forma simultanea por los hilos
generados por el CGI de consultas. Esto permite el mejor aprovechamiento de los recursos
del sistema.
Como conclusion, se logro desarrollar una herramienta para buscar informacion en la Web
de la Universidad de Magallanes, la cual a traves de distintas pruebas fue evaluada en forma
exitosa. Sin duda es una herramienta que ayudara tanto a docentes como alumnos a alcanzar
y utilizar de mejor forma la informacion disponible.
5.0.1. Trabajos Futuros
De acuerdo a la evaluacion del sistema de busqueda, es evidente que existen muchos
detalles que podrıan ser mejorados para un mejor desempeno, es por eso que se plantean los
siguientes trabajos futuros:
Para la construccion, usar otra tipo de estructura de datos, como por ejemplo un arbol
binario, con el fin de reducir el tiempo de creacion.
Evaluar otros tipos de ranking para dar peso a los documentos.
Actualizaciones de ındice.
Agregar algoritmo de lematizacion con el fin de encontrar variantes de palabras
similares.
LLevar un registro de posiciones exactas de las ocurrencias de terminos, con el
objetivo de realizar busqueda exactas de frases.
Paralelizar el algoritmo que responde a las consultas.
74
Capıtulo VI
Anexo
Anexo
6.1. WIRE
En esta seccion se describe la configuracion que se uso para el crawler WIRE. Para mas
documentacion oficial del sistema, visitar http://www.cwr.cl/projects/WIRE/doc/
Fuentes:
El paquete de las fuentes de WIRE se encuentra disponible en
http : //www.cwr.cl/projects/WIRE/releases/, para este trabajo fue descargada e
instalada la version 0.14.
Instalacion:
Previo a la instalacion fue necesario instalar los siguientes paquetes:
adns: DNS asincronico.
xml2: Librerıa XML
Luego, descomprimir el paquete de fuentes WIRE, y ejecutar en consola:
./configure
make
make install
Configuracion:
Una vez concretada la compilacion y instalacion, WIRE se configuro, a traves del archivo
XML config.conf ubicado en el mismo lugar donde fue descomprimido el paquete. Dentro
de este archivo son muchas los parametros configurables, pero solo hay algunos que son
relevantes. Las etiquetas modificadas fueron:
76
< config >< collection >< base > /wiredata < /base > , directorio de los archivos
de wire.
< config >< seeder >< accept >< domain− suffixes > .umag.cl <
/domain− suffixes >, dominio tope, para recolectar solo lo que este en umag.cl
< config >< collection >< harvest >< resolvconf > .192.162.1.1 <
/resolvconf >, ip del servidor DNS, para este caso se uso el del gateway.
< config >< collection >< maxfilesize > 400K < /maxfilesize >, se cambio el
tamano maximo de los documentos, de 100K a 400K.
Luego para que la configuracion sea cargada se debio exportar la variable de entorno,
WIRE CONF=/wiredata/config.conf; export WIRE CONF;
y, luego ejecutar wire-bot-reset, que borra las colecciones de datos existentes y crea los
directorios y archivos necesarios para la recoleccion.
Otro archivo importante es el de las URL iniciales (seeds), para comenzar el crawling, este
se llama start urls.txt, y las paginas iniciales para el primer crawling fueron:
http://www.umag.cl/
http://hain.umag.cl/
http://www.sid.umag.cl/
http://kataix.umag.cl/
http://kataix.umag.cl/∼mmarin
http://kataix.umag.cl/∼ruribe
http://kataix.umag.cl/∼jcanuman
Luego para que cargarlas se ejecuto, wire-bot-seeder –start /wiredata/start urls.txt. Ya
hecho esto, se encuentra todo listo para comenzar la recoleccion.
La sistema WIRE se ejecuta por numero de ciclos, para este caso 10 ciclos, se
ejecuto,wire-bot-run 10
77
6.2. Archivos - Scripts
Con respecto a la metodologıa de programacion que se aplico, esta fue modular, se uso
la idea dividir y venceras, de esta forma los grandes problemas se fueron desglosando a otros
mas pequeno hasta lograr una solucion completa.
Para esto, se trabajo con los archivos y programas, en forma de modulos, con el objetivos
que al momento de hacer cambios no se deba modificar todo el motor de busqueda.
En resumen la totalidad de los programas fueron:
sistema WIRE
normaliza1
normaliza2
indexador
idx split
carga
search
78
Bibliografıa
[1] Monica Henzinger, Allan Heydon, Michel Mitzenmacher y Marc Najork. On near-uniform
url sampling. En Proceeding of the Ninth Conference on World Wide Web , paginas 295-
308, Amsterdam, Netherlands, Mayo 2000. Elsevier Science.
[2] http://infolab.stanford.edu/ backrub/google.html The Anatomy of a Large-Scale Hyper-
textual Web Search Engine ,Sergey Brin and Lawrence Page,Computer Science Depart-
ment, Stanford University, Stanford, CA 94305
[3] http://www.ciw.cl/material/web chilena 2006/Web Chilena2006.pdf Estudio de la Web
Chilena, Agosto 2006 ,Ricardo Baeza-Yates, Carlos Castillo, Eduardo Graells
[4] http://www.cwr.cl/projects/WIRE/releases/ Web Information Retrieval Environment
Project ,Carlos Castillo, Centro de Investigacion de la Web.
[5] http://www.cwr.cl/projects/WIRE/doc/ Documentacion de WIRE ,Carlos Castillo,
Centro de Investigacion de la Web.
[6] http://pr.efactory.de/e-pagerank-algorithm.shtml The PageRank Algorithm
[7] Ricardo Baeza-Yates , Berthier Ribeiro-Neto. En Modern Information Retrival .Addison-
Wesiey
[8] Thesis for Ph.D. Carlos Castillo Effective Web Crawling Dept. of Computer Science -
University of Chile, 2004
[9] William B. Frakes, Ricardo Baeza-Yates. En Information Retrival, Data Structures &
Algorithms.
79