Recuperación de información (information retrieval) y búsqueda en la Web: Índices invertidos

Los índices invertidos son la estructura de datos más utilizada en los sistemas de recuperación de información, en particular en aquellos con grandes volúmenes de datos a manejar como los motores de búsqueda; hacen uso eficiente de la idea principal de la matriz de incidencias vista previamente.

Índice invertido:

• Para cada término t, tenemos que guardar todos los documentos que contienen t
• Identificar cada documento por un docId, que es un número incremental

Tendremos dos partes bien definidas: el diccionario y las listas de postings, que son básicamente una serie de listas, una por cada término, donde iremos insertando los docIds de los documentos. 

Veamos un ejemplo:

diccionario                 postings

Brutus         => 1, 2 , 4 , 11 , 45 , 113 , 124

Caesar        => 1, 2 , 4 , 5,6 ,110,174

Calpurnia    => 2, 31, 54

el diccionario es siempre mucho más chico en espacio y suele estar en memoria mientras que las listas están en disco, cuando las listas son traídas a memoria pueden ser implementadas con listas enlazadas. 

Construcción paso a paso de un índice invertido:

El siguiente esquema 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

Supongamos que tengo dos documentos:

doc 1:
    Insoportablemente soñé con un exiguo y  nítido laberinto: en el centro había un cántaro.

doc 2:
    Repechando colinas arenosas, habían llegado al laberinto.


Identificamos las palabras, las listamos e indicamos a que documento pertenecen:

Palabras	Documento
Insoportablemente	1
soñé	1
con	1
un	1
exiguo	1
y	1
nítido	1
laberinto	1
en	1
el	1
centro	1
había	1
un	1
cántaro	1
Repechando	2
colinas	2
arenosas	2
habían	2
llegado	2
al	2
laberinto	2

Ordenamos la lista alfabéticamente:

Palabras	Documento
al	2
arenosas	2
cántaro	1
centro	1
colinas	2
con	1
el	1
en	1
exiguo	1
había	1
habían	2
Insoportablemente	1
laberinto	1
laberinto	2
llegado	2
nítido	1
Repechando	2
soñé	1
un	1
un	1
y	1

Luego eliminamos los duplicados pero guardamos la frecuencia de cada término y vamos insertando los distintos docsIds en las listas de postings. Al crear las listas indicamos con un puntero en el índice la ubicación de esta.

Palabras	Frecuencia	puntero	Listas enlazadas
al	1	->	2
arenosas	1	->	2
cántaro	1	->	1
centro	1	->	1
colinas	1	->	2
con	1	->	1
el	1	->	1
en	1	->	1
exiguo	1	->	1
había	1	->	1
habían	1	->	2
Insoportablemente	1	->	1
laberinto	2	->	1->2
llegado	1	->	2
nítido	1	->	1
repechando	1	->	2
soñé	1	->	1
un	2	->	1->2
y	1	->	1

NOTA: Para calcular el espacio total que necesitaremos para el índice en sí debemos tener en cuenta el espacio que ocupan las palabras, el campo de la frecuencia y el puntero a la lista.

Más adelante veremos como optimizar estos espacios, incluyendo el tamaño de las listas.