Motores de Búsqueda
Autores:
• Pedro Flores Pérez, José
Figueroa, Caleb Lizárraga,
Ernesto Brau, Adrian Lucero,
Carlos David Briceño, Ivo
Jimenez, Juan A. Raygoza y
Fernando Razo.
Qué es un motor de búsqueda?
- Es un sistema de
recuperación de información
-
Ejemplos: Google, Yahoo!
¿Para qué se utiliza?
Buscar “algo”
Universo de
Búsqueda
donde
“algo”
Páginas HTML
documentos: *.doc, *.pdf
imágenes
otros, proporciona información,
realizar cálculos, etc.
A futuro
“algo” = Música, melodía,
letra, video
Ejemplo:
¿Silvar una canción?
¿Por qué estudiar Motores de
Búsqueda?
Porque es una de las areas de mayor desarrollo
tecnológico y lo seguirá siendo durante los
próximos años.
Ejemplos:
Buscador de Microsoft
Buscador de Google
para Documentos en PC.
Investigación en Yahoo! y Altavista para
desarrollar sus propios métodos de búsqueda.
Nuevos esquemas de venta (E-Comerce)
a través de la red de Internet.
Porque es una de las areas de
mayor desarrollo en
Investigación.
El crecimiento exponencial de la
información en la red plantea
nuevos problemas en las areas
de lingüística, matemáticas,
Matemática Numérica, Bases de
Datos, Inteligencia Artificial, etc
Desde el punto de vista
académico, es toda una
experiencia el investigar sobre
este tema, ya que se aplican
conocimientos de Bases de
Datos, Estructuras de Datos,
Redes (Clúster), Ingeniería del
Software, Métodos
Matemáticas, Teoría de
Lenguajes, Compiladores, etc
¿Porqué hacer un motor de
búsqueda?
Porque es algo que esta al
alcance de la mano, pero ....
“es dificil..... dificil la primera
vez....”
Canción: “Difícil”
Autor: Alex Lora y el Tri
Los principales motores de
búsqueda en su primera versión
fueron hecho por pocas personas.
Google fue fundado en 1998 por
Sergey Brin’s y Larry Page
• Yahoo! se funda en 1994 por David Filo y
Jerry Yang.
¿Qué estamos haciendo en el
curso de Motores de Búsqueda?
Desarrollando un motor de búsqueda
original con las siguientes
características:
- Que no sea muy grande.
- Que tenga un funcionamiento
comparado con el de un motor de
búsqueda como Google.
- Que se monte sobre clusters y que
sea
escalable.
Otras actividades:
- Revisión de materiales,
artículos, libros, etc.
-
Escribiendo material.
Impartiendo este curso
Expositores del curso:
Clusters y Bases de Datos.
José Figueroa Martínez.
Robots.
Ernesto Brau y Caleb Lizárraga.
Conversión a texto plano (Word)
Adrian Lucero
Compresión de Archivos.
Carlos David Briceño.
Un ejemplo con triadas.
Ivo Jiménez Ramos y
Juan Antonio Raygoza.
Estructuras de Datos
Fernando Razo Mendivil
Temario:
- Principales aspectos de la
recuperación de información.
- Estructura de un motor de
búsqueda.
- Una introducción a las distintas
partes de un motor de búsqueda.
Objetivo del curso:
En 3 horas, dar una brevísima introducción a
motores de búsqueda
Motor de búsqueda:
Un sistema almacenamiento de
datos (Bases de Datos),
diseñado para indexar
direcciones web.
¿Qué es Indexación?
Análisis de documento para ver
como está estructurado (título,
autor, cuerpo), como se presenta
la información más importante;
tablas, gráficas, imágenes, etc.
Esto nos lleva a establecer
partes del documento que sean
importantes.
Análisis por palabras de las secciones
importantes, tratando de encontrar qué
palabras o frases sean las que
identificaran el documento
estableciendo la mejor respresentación
de los contenidos semánticos
(significado del documento).
Existen diversas formas de hacer el
indexado, las más importantes son:
latent semantic indexing (LSI) que trata
de representar los documentos por su
contenido a diferencia de la
coincidencia de palabras.
El indexado puede ser
totalmente manual como en
yahoo! donde una persona
decide la clasificación por
categorías del documento.
Semi automático: sería cuando
alguien ayuda a un programa a
establecer la indexación.
Totalmente automática, donde
un programa se encarga de
todos los pasos de indexación,
por ejemplo: Google
Representación vectorial de
documentos:
SMART (System for the
Mechanical Análisys and
Retrieval of Text) desarrollado por
Gerald Selton fue el sistema
básico para representar
documentos.
Ejemplos:
Documento 1
La Bamba
Para bailar la bamba
Para bailar la bamba
se necesita una
poca de gracia y
otra cosita......
Documento 2
Sin ti
Sin ti, no podre vivir jamas
y pensar que nunca mas estaras
junto a mi
Sin ti, que me puede ya
importar, si lo que me hace
soñar está lejos de mi
Documento 1 #1854
R1
R2
R3
R4
R5
R6
La Bamba
Para bailar la bamba
Para bailar la bamba
se necesita una
poca de gracia y
otra cosita......
Documento 1 #1854
R1
R2
R3
R4
R5
R6
La Bamba
Para bailar la bamba
Para bailar la bamba
se necesita una
poca de gracia y
otra cosita......
Documento 2
# 7523
R1 Sin ti
R2
Sin ti, no podre vivir jamas
R3 y pensar que nunca mas estaras
R4 junto a mi
R5 Sin ti, que me puede ya
R6 importar, si lo que me hace
R7 sonar está lejos de mi
Documento 2
# 7523
R1 Sin ti
R2
Sin ti, no podre vivir jamas
R3 y pensar que nunca mas estaras
R4 junto a mi
R5 Sin ti, que me puede ya
R6 importar, si lo que me hace
R7 soñar está lejos de mi
¿Qué palabras incluir?
Hay una base de datos de los
términos incluidos en todos los
documentos. Google en 1998,
tenía 14 millones de términos.
Con esta base de datos se
crea una estructura en
memoria de tipo Arbol-B para
procesar todas las palabras de
los documentos.
Base de datos I
Base de datos II
• Lista invertida de términos:
Base de datos III
Frecuencia de palabras en documentos
Procedimiento de consulta
Suponiendo que queremos buscar en los
documentos, los documentos con las
palabras: Sin ti
Se construye el vector W
W = (0, ..., 0, 1,1,0,.....,0)
Sin ti
Que tiene dos componentes iguales
a 1 en los lugares de las palabras
Sin y ti
Resultado:
Si se tiene una consulta representada por
W y un documento representado por U,
entonces
Si U.W = 0
El documento W no tiene ninguna de las
palabras de la consulta W.
Si U.W > 0 entonces el documento U
tiene algunas palabras de la consulta W.
Una mejor aproximación es tener
Cos  = U.W / || U || || W ||
Donde  es el ángulo entre U y V.
Si Cos  > 0.5
Diremos que U es una respuesta de la
consulta W y si
Cos  < 0.5
Entonces U no es una respuesta a la
consulta W.
• Se contruye una estructura de
datos en memoria para calcular
eficientemente los productos
interiores de la consulta por los
documentos y se eligen
documentos que tengan las
palabras de búsqueda.
Ranking de un documento
De entre todos los documentos que
tienen las palabras que se buscan, se
presentan los que tengan ranking de
mayor a menor. Google calcula el
ranking de acuerdo a:
R(i)
N(i)
B(i)
m
d
Ranking de la página i.
Número de enlace salidas de i
Número de enlaces entradas de i
Total de páginas en el sistema
factor que mide la longitud de la
búsqueda
r(i) es la probabilidad de llegar a la
página i a partir de otra d es una
fecha que mide la longitud de la
búsqueda.
Se eligen los documentos de ranking
más grande y a partir de W y las
bases de datos I y II se construyen
las respuestas.
Partes de un motor de búsqueda
(con indexación automática)
Robots: Encargada de traer las
páginas, comprimirlas y guardarlas.
Diccionario: Base de Datos con la
información de todas las palabras a
utilizar.
Procesador de páginas:
Revisa los documentos a partir del
documento y los indexa.
Procesador de consultas:
Dada una consulta construye los
resultados.
Sistema de Rankeo:
Calcula la importancia de cada
página.
Arquitectura de Google
Bibliografia
• S.Brin, L. Page. The anathomy of
a large-scale hipertextual web
search engine. 7th international
world wide web
conference.Brisbane, Australia,
April 1998.
• Michael W. Berry, Murray Boune.
Understanding search engines:
mathematical modeling and text
retrieval. SIAM press 1999.
Descargar

Qué es un motor de búsqueda?