El proceso de indexación
Introducción
La indexación es un proceso lento y costoso, pero sólo debe ejecutarse en el momento de crear el índice invertido, aunque es muy importante actualizarlo cuando haya modificaciones.
La indexación consta de los siguientes pasos:
- Recorrer todos los documentos sobre los que queremos buscar. Este puede ser un conjunto finito y conocido, por ejemplo: las páginas HTML de una carpeta, o puede ser desconocido: todas las páginas de Internet. En este último caso, los buscadores utilizan los que se denominan robots, crawlers o también spiders: Son pequeños programas que van rastreando la estructura de la web en busca de nuevas páginas. Este tipo de programas van recolectando páginas a través de los enlaces a otras páginas, así en un ciclo interminable. Una vez que el robot localiza una página, puede procesarla a través del siguiente paso.
- Procesar el documento a indexar: Se descompone hasta obtener la lista de palabras que lo forman. Este proceso puede ser muy sencillo, como en los archivos de texto plano, que tiene todas las palabras separadas por espacios u otros caracteres, o muy complejo, como un documento PDF que debe ser decodificado, separando el formato y las imágenes, extrayendo solamente el texto plano.
- Con la lista de palabras de un documento, creamos el índice invertido: Guardamos la lista apuntando en qué documento hemos encontrado cada palabra. Habrá algunas palabras que solo aparezcan en un documento (la búsqueda de esa palabra nos dará un solo resultado), mientras que otras palabras más comunes aparecerán en muchos documentos.
- Opcionalmente podemos almacenar el documento, en su estado actual, en la propia base de datos. De esta forma, podemos consultar cualquier documento aunque el original deje de estar disponible (como hace Google con su caché).
¿Qué se suele indexar?
¿Qué información se suele indexar? Podemos indexar las palabras, su posición relativa dentro del documento, información de relevancia (si está en negrita, si es un título, etc.), e información sobre a qué otros documentos enlaza.
También se suele guardar una breve descripción de cada página: Título, tamaño, peso, fecha, principales palabras o resumen, etc. Hay que tener en cuenta que si el resumen ocupase 500 bytes y tuviésemos cien millones de páginas, sólo esto nos ocuparía 50 Gb.
Se suele estimar que el índice suele ocupar un 30% del texto indexado. Para 100 millones de páginas de 8Kb. tendríamos un índice de 240Gb., aunque con compresión lo podemos reducir hasta un 10%.
Las búsquedas pueden ser directamente de palabras en el índice, literales o de proximidas (hay que guardar más información en el índice: Posición relativa de las palabras dentro del documento), palabras con comodines o con errores comunes (hay que buscar secuencialmente en el índice).
Índices distribuidos
Podemos tener dos tipos de índices, respecto a su gestión:
- Centralizados: Tienen bastantes inconvenientes: Escalabilidad limitada, el servidor se sobrecarga, tolerancia a fallos mala.
- Distribuidos: Tenemos servidores de consulta, cada uno ejecutándose en un servidor
Arquitectura
En una arquitectura distribuida, se suelen tener los servidores de consultas y un broker de consultas que se encargará de:
- Aceptar las peticiones de los usuarios
- Distribuir las peticiones a los servidores
- Recibir y combinar los resultados parciales
- Enviar el resultado final al usuario
Si dividimos la colección de documentos entre los servidores y cada colección se gestiona independientemente, tendríamos lo que se llama un metabuscador.
Pero si se decide centralizar la gestión, tenemos varias alternativas:
- Replicar la colección en los servidores: Sirve para colecciones pequeñas. Mejora el throughput. El broker se encarga de dirigir y balancear las consultas.
- Distribuir el vocabulario: Cada servidor almacenaría una parte disjunta del vocabulario y la lista de documentos asociada. El broker debe decidir los servidores que son relevantes y enviarle su parte de la consulta.
- Distribuir los documentos de forma aleatoria: Adecuado para grandes colecciones, pues al tener una visión global de los documentos se obtiene un mayor rendimiento. Aquí el broker envía la consulta a todos, y agrega los resultados de cada uno.
- Distribuir los documentos de forma semántica: Los documentos se agrupan por temática, con lo cual el broker debe seleccionar a qué servidores le envía la consulta (dependiendo de si es o no relevante su temática para la consulta).
Para los buscadores modernos es mejor la opción de distribución aleatoria de los documentos, porque se evita así la selección de colecciones relevantes, y la combinación de resultados es trivial. Además, hace buen uso de los recursos y tiene tolerancia a fallos. Por contra, los cuellos de botella están en el broker y en la red que comunica los servidores.
![[Recuperacion Organizacion Informacion. Valid RSS1.0]](img/valid-rss1.png "Recuperacion Organizacion Informacion Validate my RSS feed")
![[Recuperacion Organizacion Informacion.Valid RSS2.0]](./img/valid-rss2.png "Recuperacion Organizacion Informacion Validate my RSS feed")