Índices y Buscadores
En este proyecto vamos analizar cuáles son los mecanismos esenciales con los que un buscador pueden duplicar el tamaño de su índice, y cómo afectará a la rapidez con que se devuelven resultados en promedio.
1. Índice
Un índice es una estructura de datos que mejora la velocidad de las operaciones de acceso a la información, permitiendo un rápido acceso a los registros almacenados. Dado que las consultas están compuestas por palabras, una consulta la podremos analizar y descomponer para obtener como resultado las unidades clave que nos permitan recuperar los documentos.
Por ejemplo, supongamos que un almacén de datos contiene N objetos y queremos obtener el objeto X. Una primera aproximación sería utilizar un algoritmo directo (naive) que nos obligaría a analizar todos los objetos uno por uno si es el correcto o no para esta consulta. Por supuesto para un almacén con infinidad de datos no es realmente rentable. En ese caso el índice podría ser la solución. Como hemos dicho antes podemos considerar un índice a cualquier estructura de datos que mejore el rendimiento de la búsqueda y, por lo tanto, existe una gran diversidad de estructuras diferentes usadas para este propósito, de hecho una parte sustancial de la Informática se dedica al diseño y análisis de estructuras de índices de datos. Hay diseños complejos que contemplan variables como el rendimiento de las búsquedas, el tamaño del índice y el rendimiento de actualización del índice o otros simplemente que son estructuras HashMap.
Respecto al análisis temporal es muy simple, el primer algoritmo sin índice tiene un coste de O(N) que es muy elevada comparado con la utilización de un índice, donde normalmente se calcula un coste temporal logarítmicos (O(log(N)) y en algunos casos es posible alcanzar rendimiento “plano” O(1).
Todo el software de bases de datos incluye tecnología de indexación para mejorar el rendimiento. Una aplicación específica y muy común se da en el dominio de Recuperación de la Información donde la aplicación de un índice de texto completo permite una rápida identificación de los documentos basados en su contenido textual.
2. Índice invertido
Es una estructura de índice que almacena un trazado de palabras en sus localizaciones, es decir, en qué documento o conjunto de documentos se encuentran, lo que permite una búsqueda total de texto. Esta estructura de datos es la más popular entre los sistemas de recuperación de documentos.
Existe dos variantes de índice invertido:
- Índice de fichero invertido: que contiene una lista de referencias a los documentos por cada palabra.
- Completamente invertido: Contiene
adicionalmente las posiciones de cada palabra dentro de un documento
. El índice completamente invertido ofrece más funcionalidad (Como búsqueda de proposiciones) pero requiere más tiempo y espacio para ser creado
2.1 Funcionamiento
La mejor forma de conocer su funcionamiento es mediante un ejemplo. Por ejemplo tenemos los siguientes documentos :
- D0 : it is what it is
- D1 : what is it
- D2 : it is a banana
Dados los textos , tenemos el siguiente índice invertido:
- a: {2}
- banana: {2}
- is: {0, 1, 2}
- it: {0, 1, 2}
- what: {0, 1}
Una búsqueda de términos para what, is e it nos devolverán el siguiente conjunto:
Con los mismos documentos, vamos a construir otro índice pero en este caso un índice total, donde relacionamos los documentos con el número de veces que contiene la palabra. Por ejemplo podemos analizar que la palabras what se encuentra en DO exactamente en la posición 2 (empezamos por 0) y {(0,2)}. Aplicando esta filosofía obtenemos :
- a: {(2, 2)}
- banana: {(2, 3)}
- is: {(0, 1), (0, 4), (1, 1), (2, 1)}
- it: {(0, 0), (0, 3), (1, 2), (2, 0)}
- what: {(0, 2), (1, 0)}
Si hacemos una búsqueda de what is it tenemos resultados para todas las palabras tanto en el documento 0 como en el 1. Pero los términos solo ocurren consecutivamente en el documento 1.
2.2 Implementación
La estructura de datos de índice invertido es un componente central de un algoritmo de indexación de un motor de búsqueda típico ya que su objetivo principal es optimizar la velocidad de la consulta.
Una vez que se desarrolla un índice directo, que almacena listas de palabras por documento, seguidamente se invierte para desarrollar un índice invertido. ¿Por qué? Porqué realizar la consulta en el índice directo requeriría una iteración secuencial a través de cada documento y de cada palabra para verificar un documento que correspondiese. Los recursos de tiempo, memoria, y procesado para realizar tal consulta no son siempre técnicamente realistas. En vez de listar las palabras por documento en el índice directo, se desarrolla la estructura de índice inverso, que lista los documentos por palabra.
Con el índice invertido creado, la consulta puede ahora ser resuelta saltando al identificador de la palabra (vía acceso aleatorio) en el índice invertido. Estadísticamente se contempla generalmente el acceso aleatorio como más rápido que el acceso secuencial. El proceso de búsqueda es laborioso debido a la gran cantidad de datos. Los documentos comprenden varias decenas de terabytes de datos sin comprimir, y el índice invertido resultante de estos datos es en sí mismo de muchos terabytes de datos. Afortunadamente la búsqueda es paralelizable dividiendo el índice en fragmentos. Un conjunto de máquinas proporcionan respuestas por cada fragmento, y el cúmulo de índice total contiene un conjunto de máquinas para cada fragmento. Si la réplica de un fragmento se cae, el equilibrador de carga evitará usarlo para consultas. Durante el tiempo de caída , la capacidad del sistema se reduce en proporción a la fracción total de capacidad que esta máquina representa. Sin embargo, el servicio se mantiene ininterrumpido y todas las partes del índice siguen disponibles.