Recuperación de información (information retrieval) y búsqueda en la Web: consultas sobre Indices invertidos

En el post anterior vimos como crear un índice invertido, ahora voy a explicar como realizar una consulta sobre ese tipo de índice.

Supónganse que queremos obtener todos los documentos en donde aparecen las palabras: "Brutus" y "Cesar"

1. Obtenemos la lista de documentos en donde aparece la palabra "Brutus"
2. Obtenemos la lista de documentos en donde aparece la palabra "Cesar"
3. Realizamos una intersección de ambas listas mediante un algoritmo de merge

Algoritmo de merge:

Imaginemos que la lista de documentos, para ambos términos es la siguiente:

Brutus: 2->4->8->16->32->64->128

Cesar:  1->2->3->5->8->13->21->34

NOTA: es importante que las listas estén ordenadas por docId

1. Creamos un conjunto intersección originalmente vacío: I={}
2. Generamos dos punteros que apuntan respectivamente al primer elemento de cada una de las listas: p1, p2 tal que p1=2 y p2=1 originalmente.
3. Si el docId al que apunta p1 es igual al docId al que apunta p2, agrego ese docId en I.
1.  avanzo los dos punteros una posición.
2. vuelvo a 3.
4. Sino son iguales avanzo una posición al puntero cuyo docId apuntado es más chico. 
1. Vuelvo a 3
5. Si la lista termino, finalizo.

Para el ejemplo anterior la secuencia paso a paso sería:

1. p1=2, p2=1
2. p1=2, p2=2  => I={2}
3. p1=4, p2=3
4. p1=4, p2=5
5. p1=8, p2=5
6. p1=8, p2=8  => I={2,8}
7. p1=16, p2=13
8. p1=16, p2=21
9. p1=32, p2=21
10. p1=32, p2=34
11. p1=64, p2=34
12. =>FIN (se acabó la lista para p2)

Este algoritmo tarda O(x+y), es decir  un tiempo logarítmico: cuanto más crezcan las listas X e Y los pasos aumentarán logarítmicamente, muy poco. 

Algoritmo de merge en pseudocódigo:

 aquí está la función en un pseudocódigo un poco parecido a Java


function Set intersec(Iterator p1, Iterator p2){ 
          //Devuelve un tipo de dato Set
          // que será un conjunto de docId
Set result = create();

while(p1!= NULL && p2!= NULL){  //se supone que más allá del  
                               //último elemento apuntan a NULL

  if(p1.getElement()==p2.getElement()) then{
   result.add(p1.getElement());
   p1.next();
   p2.next();
 }else if(p1.getElement()>p2.getElement()) then{ 
   p2.next();
 }else{
   p1.next();
 }
}
return result;
}