Estructuras de Datos en Recuperación de Información

Para la implementación de **Sistemas de Recuperación de Información (SRI)**, a partir de los conceptos y técnicas de preprocesamiento de texto, es fundamental contar con **estructuras de datos eficientes** que soporten las estrategias de búsqueda, de acuerdo con el modelo de RI adoptado.

Como se ha mencionado, un SRI parte de un conjunto de documentos o una colección, los cuales debe procesar de alguna forma para responder a las 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. Esta técnica se 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 en aquellas de contenido dinámico, o en casos donde no se dispone de recursos para gestionar el espacio de almacenamiento extra que requieren las estructuras auxiliares.

Es importante tener en cuenta que si el sistema realiza operaciones de preprocesamiento, como la **eliminación de palabras vacías (stop words)** y el **stemming**, de 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 *d_j* y las columnas corresponden a los términos *t_i* del vocabulario. La intersección (*d_j*, *t_i*) corresponde al **peso o ponderación** que se le asigna a *t_i* en *d_j*. 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 a los **sistemas de recuperación de datos**, como por ejemplo, los **sistemas de bases de datos**. Estos crean índices con los valores existentes en cada tabla de su **clave primaria** y sus **claves secundarias**. Como se puede deducir, se está aprovechando la estructura para determinar sobre qué atributos se crean índices. Por lo tanto, con estos se optimizan las búsquedas, permitiendo un **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 las cuales buscar. 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 debe contener **todo el vocabulario**.

Por supuesto, el vocabulario estará formado por los términos que surgieron de las decisiones tomadas 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, la puntuación interna (ej. *gen-10* o *gen10*) y el uso de mayúsculas/minúsculas (ej. *la plata* o *La Plata*).

Otra cuestión importante a tener en cuenta para la **creación de índices** es que su contenido varía de acuerdo con el **modelo de RI** que debe soportar. De manera simple, la presencia de pares **término/documento** es suficiente para el **modelo booleano**. Sin embargo, otros modelos requieren **información estadística** de la colección, como la **frecuencia del término (tf)**, la **frecuencia en documentos (df)**, la **frecuencia en la colección (ctf)**, la **longitud de los documentos (doclen)**, entre 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 el denominado **“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 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érmino-documento** (Figura 2). A partir de esta, 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 es la lista de documentos donde este 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:

• **Vocabulario**: conjunto de términos distintos del texto.
• **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:

Construcción de un Índice Invertido

• 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* a la lista de posteo de *t*.
  • Sino:
    • Agregar *t* al vocabulario.
    • Agregar *d* a la lista de posteo de *t*.
• Grabar a disco el índice invertido.

La Figura 4 refleja el **ciclo habitual** a través del cual se construye 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 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 se 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 (Figura 5) 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 el **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.

Construcción de Índices Distribuidos:

• 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 RAM como una gran **memoria distribuida**.
• Dos medidas de interés para las consultas:
  • **Throughput**: Cantidad de consultas respondidas por segundo.
  • **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 descrito 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 características de la Web, Sección 1.1). En su mayoría, la literatura se aboca 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 mencionó, las **listas de posteo** son generalmente almacenadas en **memoria secundaria**.

Debido a las caracterí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 de 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 **reconstruir periódicamente 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.

Etiquetas: búsqueda de información, estructuras de datos, Indexación, Índices Invertidos, Preprocesamiento de Texto, recuperación de información, Sistemas de información