Unidad 3: Estructura de datos en RI
Las estructuras de datos básicas para la implementación de sistemas de recuperación de información a partir de los conceptos y las técnicas sobre preprocesamiento de texto, resulta necesario contar con estructuras de datos eficientes que soporten las estrategias de búsquedas, de acuerdo al modelo de RI adoptado.
Como hemos mencionado, el SRI parte de un conjunto de documentos o colección, los cuales tiene que procesar – de alguna forma – para responder a consultas de los usuarios. De la manera más básica, se podría tomar la consulta del usuario y recorrer toda la colección, documento por documento, calculando la relevancia de cada uno. A esta técnica se la conoce como búsqueda secuencial o búsqueda por texto libre. Sin embargo, resulta ineficiente y solo es válida para colecciones textuales pequeñas o – bien – en aquellas que son de contenido dinámico o en casos en que no se dispone de recursos para gestionar el espacio de almacenamiento extra que requieren estructuras auxiliares.
Hay que tener en cuenta que si el sistema realiza operaciones de preprocesamiento como eliminación de palabras vacías y stemming, en la forma más ineficiente, estas tareas se repetirían para cada consulta. Entonces, se podría tener un conjunto de archivos con la representación lógica de los documentos de la colección, por ejemplo una tipo “bolsa de palabras” ya preprocesada por cada documento. Esto permite que las tareas previas se realicen solo una vez, pero el costo computacional de recorrer toda la colección sigue siendo alto (O(n) donde n es la cantidad de documentos que componen el corpus).
Con el objetivo de lograr mayor eficiencia en la tarea de recuperación, se construyen estructuras de datos auxiliares que soportan la representación lógica de todos los documentos de la colección. De forma genérica, estas estructuras reciben el nombre de índices. Como soporte del sistema, los índices permiten el acceso directo a los documentos que contienen los términos de la consulta. Como estructuras de datos, soportan diferentes técnicas de optimización, como por ejemplo la compresión.
El contenido del índice está dado por el conjunto de términos que contienen todos los documentos de la colección, es decir, el vocabulario. Una forma de representación de la información que debe contener un índice es la matriz documento–término (Figura 1).
Sobre las filas se representan los documentos dj y las columnas corresponden a los términos ti del vocabulario. La intersección (dj, ti) corresponde al peso o ponderación que se le asigna a ti en dj. En el caso más simple puede ser un 0 o un 1, denotando ausencia o presencia del término en el documento o bien un valor surgido de un criterio de ponderación.
Una distinción importante surge respecto de los sistemas de recuperación de datos como – por ejemplo – los sistemas de bases de datos. Éstos crean índices con los valores existentes en cada tabla de su clave primaria y sus claves secundarias. Como se puede deducir, se está provechando la estructura para determinar sobre qué atributos se crean índices. Por lo tanto, con éstos se optimizan las búsquedas, permitiendo rápido acceso a los ítems requeridos.
Sin embargo, en un sistema de RI hay un inconveniente adicional. No existe un conjunto a priori de claves por la cuales buscar y – como no se puede saber de antemano cuáles se utilizarán en una búsqueda – todos los términos de todos los documentos son potenciales claves de búsqueda.
De esta circunstancia surge que un índice para un sistema de RI contenga todo el vocabulario.
Por supuesto, el vocabulario estará formado por los términos que surgieron de las decisiones que se tomaron para el preprocesamiento de los documentos (eliminación de palabras vacías, stemming). Pero también hay que tener en cuenta cómo se realiza el proceso de identificación de los términos indexables (tokenización), ya que esto puede derivar en uno o dos términos o en formas modificadas. Por ejemplo, puntuación interna (gen-10 ó gen10) y mayúsculas/minúsculas (la plata ó La Plata).
Otra cuestión importante a tener en cuenta para la creación de índices es que su contenido varía de acuerdo al modelo de RI que debe soportar. De manera simple, la presencia de pares término/documento alcanza para el modelo booleano. Sin embargo, otros modelos requieren información estadística de la colección como frecuencia del término (tf), frecuencia en documentos (df), frecuencia en la colección (ctf), longitud de los documentos (doclen) y otras. Además, es posible que se requiera almacenar información posicional (para búsquedas por cercanía de términos) de cada término dentro del documento.
3.1. Índices Invertidos
Partiendo de la matriz documento–término (Figura 1) se construye un índice que almacena su representación. La estructura de índice básica es la denominada “archivo invertido”. En su forma más simple, es un conjunto de términos donde cada uno tiene asociada una lista de los identificadores de documentos donde cada término aparece. Es decir, cada entrada en el archivo invertido mapea un término con un conjunto de documentos que lo contienen. Esta organización es completamente opuesta a la representación de cada documento como una bolsa de palabras, donde un documento está definido por un conjunto de términos. Entonces, para la construcción del índice, podemos ver la matriz documento–término en forma invertida como matriz términodocumento (Figura 2). A partir de ésta, la construcción del archivo invertido surge de forma directa.
El archivo invertido que soporta tal representación consta de dos partes: la primera es un término y la segunda la lista de documentos donde éste aparece, denominada lista de posteo (posting list). Nótese que el conjunto de todos los términos corresponde al vocabulario de la colección y – por supuesto – no tiene repetidos. En la figura 3 se muestra un ejemplo de una colección (con sus términos indexables por documento) y el archivo invertido resultante de la indexación.
En su versión más básica consta de dos partes:
o Vocabulario: conjunto de términos distintos del texto o Posteo: para cada término la lista de documentos donde aparece
Ejemplo 1:
d1 = {Se hacen soldadura de puertas}
d2 = {Reparo puertas y ventanas}
d3 = {Vendo ventanas usadas}
d4 = {Soldadura de puertas y marcos}
La construcción de este índice es relativamente sencilla. A continuación se muestra el algoritmo básico para esta tarea:
Por cada documento d en la colección
Identificar los términos t en d
Por cada término t en d
Buscar t en el vocabulario
Si existe t
Agregar d la lista de posteo de t
Sino
Agregar t al vocabulario
Agregar d la lista de posteo de t
Grabar a disco el índice invertido
Construcción de un índice invertido
La Figura 4 refleja el ciclo habitual a través del cual tendremos que pasar para construir un índice invertido:
La tokenización es el proceso de separar un documento dado en palabras, pueden ver aquí un post anterior sobre la tokenización. Luego de tener las palabras separadas es lógico pensar en llevarlas todas hacia un estándar, una forma normal o canónica, hay un post anterior sobre la normalización de palabras. Finalmente creamos el índice con las palabras ya identificadas y normalizadas.
NOTA: es muy común que que haya palabras que no nos interese guardar, por lo general no guardamos las palabras que son tan frecuentes que aparecen en todos los documentos, por ejemplo: «a», «por», «el», «la», «los», «y», «o», etc. Estas palabras de llaman: stop words
Debemos considerar a nivel de los SRI una arquitectura en cuanto al Almacenamiento e Indexación de documentos según el índice invertido Figura5 y en la Figura 6 la recuperación de los mismos:
3.2 Índices Distribuidos
En muchos casos, por bueno que sea el algoritmo de indexación o de búsqueda, no es suficiente para cubrir la demanda:
El texto es demasiado grande. La frecuencia de actualización es demasiado alta. Llegan demasiadas consultas por segundo. La velocidad de los discos no está creciendo al ritmo necesario. Una alternativa es utilizar paralelismo. Bien diseñado, puede expandir la capacidad de procesamiento tanto como se quiera. Las redes muy rápidas formadas por unas pocas máquinas muy potentes se han convertido en una alternativa de bajo costo.
Índices Distribuidos construcción:
En estas redes el acceso remoto cuesta aproximadamente lo mismo que el acceso al disco local. Normalmente, todos los procesadores pueden comunicarse de a pares sin causar congestión. Se puede considerar el total de RAMs como una gran memoria distribuida. Dos medidas de interés para las consultas: o Throughput: Cantidad de consultas respondidas por segundo. O Tiempo de respuesta: Tiempo que demora una consulta particular
Generación Distribuida de Índices Invertidos:
Se distribuye el texto entre las máquinas equitativamente. Cada máquina construye su índice invertido local. Se unen de a dos, jerárquicamente, hasta que una sola contiene todo el vocabulario. Esa máquina calcula qué parte del vocabulario será responsabilidad de cada procesador, y distribuye esa información. Los procesadores se aparean todos con todos intercambiando las listas de posteo. Secuencialmente transmiten su parte del índice a un disco central, donde se concatenan para formar un índice centralizado.
3.3 Indexación Incremental
El proceso de construcción del índice descripto previamente asume que los documentos que comprenden la colección nunca cambian. Sin embargo, ciertas colecciones resultan ser dinámicas, hecho que implica que su composición sufre modificaciones con el paso del tiempo, nuevos documentos se agregan, otros se modifican y muchos desaparecen (recuérdese las carácterísticas de la Web, Sección 1.1). En su mayoría, la literatura se avoca a resolver el problema de agregar nuevos documentos.
La indexación dinámica o incremental es también conocida como indexación en-línea, ya que los documentos arriban al sistema una vez que este se encuentra en pleno funcionamiento, es decir disponible para recibir consultas. Como se menciónó, las listas de posteo son generalmente almacenadas en memoria secundaria.
Debido a las carácterísticas físicas que estos dispositivos presentan es conveniente disponer de los datos de forma contigua si se desea maximizar el rendimiento en las operaciones de entrada/salida. Por ello, concretar ciertos cambios sobre las postings involucra extender sus estructuras incurriendo en procesos que consumen gran cantidad de tiempo. Esto puede degradar en gran medida la efectividad del sistema recuperación, ya que ciertos fragmentos del índice no se encuentran disponibles para su consulta mientras dure la correspondiente actualización. La opción más simple para lidiar con esta cuestión consiste en periódicamente re-construir el índice por completo.
Este suele ser un buen enfoque si el número de cambios acumulados en el tiempo resulta relativamente reducido y sobre todo, si el retraso para permitir la búsqueda sobre los nuevos documentos puede admitirse. Asimismo, es necesario contar con los recursos suficientes para construir el nuevo índice mientras el anterior aún se encuentra disponible para servir consultas.