Recuperación de información (information retrieval) y búsqueda en la Web: consultas de frases e índices posicionales

Hasta ahora hemos visto como recuperar documentos que contienen una o más palabras pero no como recuperar documentos que contienen una frase armada; si yo quisiera recuperar todos aquellos documentos en donde aparece la frase: "facultad de ingeniería", por ejemplo, lo único que podría hacer es recuperar los documentos que contienen las palabras "facultad", "de" e "ingeniería" ("de" podría obviarse porque es una stop word) y luego revisarlos exhaustivamente para encontrar la frase textual, ya que no me interesan los documentos que dicen cosas como: "Pedro estudió ingeniería en la facultad de Salta", estos no deberían ser devueltos.

Hay dos formas de solucionar este problema.



primera aproximación: índices de dos-palabras (biword indexes)

Cada entrada del índice son dos palabras que aparecen de forma consecutiva en un texto.
Ejemplo, el texto: "Repechando, colinas arenosas" generará las siguientes entradas de dos-palabras:

• repechando colinas
• colinas arenosas

De esta forma las frases de dos palabras se obtienen de inmediato, pero ¿qué pasa con las frases de tres o más palabras?

Si quisiera buscar: "Facultad de Ingeniería de la Universidad de Buenos Aires", por ejemplo, tendría que partir la frase en serie de dos-palabras:

• facultad de 
• de ingeniería
• ingeniería de
• de la 
• la universidad 
• universidad de
• de buenos 
• buenos aires

Y luego traer todos aquellos documentos que contengan estos términos de dos-palabras,  por supuesto, eso no me garantiza que tengan la frase armada como yo la quiero pero sí me garantiza un porcentaje de éxito alto, es decir habrá muy pocos falsos positivos. 

problemas con los índices de dos-palabras (biword indexes)

• falsos positivos, como dijimos antes
• el índice ocupa mucho espacio 
• no son la solución estándar para este tipo de problemas (aunque pueden ayudar)

segunda solución: índices posicionales

Retomando la idea previa de los índices invertidos podemos mejorarla agregando a los documentos en los cuales aparece un término, su posición en dicho documento. 

Ahora el índice genéricamente quedará como:

término; cantidad de documentos en donde aparece; --> 

documento 1: pos01, pos02, pos03...; -->

documento 2: pos01, pos02, pos03...; -->

etc..

Con este tipo de índice, para buscar una frase tendremos que realizar dos pasos:

• Obtener todos los documentos que contienen cada uno de los términos de la frase, esto se realizará con el algoritmo de merge visto en el post anterior. 
• Luego recorreremos con un algoritmo similar al anterior las listas de posiciones de cada uno de los términos (para un mismo documento) buscando que las posiciones relativas coincidan como en la frase de consulta.

clarifiquemos lo anterior con un ejemplo:

Supongamos que tengo este índice armado para los términos "facultad" e "ingeniería":

– facultad: 3 documentos

  2:1,17,74,222,551;

  4:8,16,190,429,433;

  7:13,23,191;

– ingeniería: 3 documentos

1:17,19;

4:18,192,291,430,435;

5:14,19,101;

Aplicando el algoritmo de merge explicado en el post anterior, obtendríamos el documento 4.

Luego para el documento 4 aplicamos el siguiente algoritmo de merge:

1. Creamos un conjunto intersección, originalmente vacío: I={}, y para cada elemento un conjunto de posiciones P={}
2. Generamos dos punteros que apuntan respectivamente al primer elemento de cada una de las listas de posiciones: p1, p2 tal que p1=8 y p2=17 al iniciar.
3. Si la posición a la que apunta p1 es igual la de p2 + 2, agrego ese docId en I y la posición de p1 en el conjunto P (del docId previo)
1. Avanzo ambos punteros.
4. Sino se cumple la igualdad:
   si p1>p2+2 => avanzo p1 una posición
   si p2+1>p1 => avanzo p2 una posición
5. Si se terminó alguna lista finalizo, sino vuelvo a 3.

Este algoritmo es para obtener no solo los documentos que contienen la frase sino también las posiciones, si solo quisiera obtener los documentos termino en cuanto encuentro la primer coincidencia. 

La respuesta tendría que ser:

I={4}; P[4]={16,190,433}

NOTA: se habrán dado cuenta que no evalué la palabra "de" que media entre "facultad" e "ingeniería", por supuesto que la forma correcta hubiese sido verificar que la posición de la palabra "de" sea la de "facultad" + 1, pero como "de" es una stop word no suele guardarse en este tipo de índices (ademas así simplificaba el ejemplo) claro que esto podría acarrear el problema de falsos positivos, podrían aparecer documentos que dijesen algo así como: "facultad naranja ingeniería" pero serían casos más bien raros.

consultas de proximidad

Con este tipo de índices se pueden hacer consultas de proximidad, es decir buscar palabras que estén cerca de otras en un texto, en donde cerca es un número arbitrario que definimos nosotros. 

Por ejemplo, podemos definir un limite de 6 palabras, podríamos buscar la palabra: "película" cerca de la palabra: "oscar" y aparecerían frases como:

"película ganadora del oscar" (distancia 3)

"película que no ganó el oscar" (distancia 5)

"el oscar que ganó esa película" (distancia 4)

Habría, claro está, que modificar el algoritmo antes presentado.

tamaño de un índice posicional

Como habrán adivinado este tipo de índice ocupa su buena porción de espacio, sin embargo es el tipo de índice más utilizado para la recuperación de información en la web. 

• un índice posicional es de 2 a 4 veces más grande que un índice no posicional
• el tamaño de un índice posicional suele ser entre un 35 y un 50% del volumen de los textos originales

problemas comunes y esquemas combinados

    Los índices posicionales no son del todo buenos para buscar frases comunes como nombres propios, ejemplo: "Buenos Aires", "San Martín", "Indio Solari" pero son realmente malos para buscar nombres propios que ademas son frases muy utilizadas, por ejemplo si alguien busca la película: "Los otros" está claro que el algoritmo encontrará cientos de miles de coincidencias (haciendo que la búsqueda sea más lenta) pero ademas arrojará muchísimos resultados que son falsos positivos.

    Una solución a este problema es crear un índice combinado, o sea, agregar entradas al índice que sean dos-palabras, de esta forma se reduciría mucho el tiempo de búsqueda para nombres propios como "Buenos Aires". Sin embargo la ganancia en el tiempo de búsqueda se paga con más espacio, un índice combinado puede llegar a ser 4 veces más rápido pero suele ocupar un 26% más de espacio.