Índice invertido

Un  índice invertido es una estructura de datos en la que, para cada palabra de una colección de documentos, la lista correspondiente enumera todos los documentos de la colección en la que aparece. El índice invertido se utiliza para buscar a través de los textos.

Hay dos variantes del índice invertido:

Aplicación

Describamos cómo resolvemos el problema de encontrar documentos que contengan todas las palabras de la consulta de búsqueda . Al procesar una consulta de búsqueda de una sola palabra, la respuesta ya está en el índice invertido; simplemente tome la lista correspondiente a la palabra de la consulta. Al procesar una consulta de varias palabras, se toma la intersección de las listas correspondientes a cada una de las palabras de la consulta.

Por lo general, en los motores de búsqueda , después de crear una lista de documentos que contienen palabras de una consulta utilizando un índice invertido, los documentos de la lista se clasifican . El índice invertido es la estructura de datos más popular utilizada en la recuperación de información [2] .

Ejemplo

Tengamos un corpus de tres textos , y , luego el índice invertido se verá así: "it is what it is""what is it""it is a banana"

"un": {2} "plátano": {2} "es": {0, 1, 2} "eso": {0, 1, 2} "qué": {0, 1}

Aquí los números indican los números de los textos en los que aparece la palabra correspondiente. Luego, procesar la consulta de "what is it"búsqueda dará el siguiente resultado .

Características de la aplicación en motores de búsqueda reales

En la lista de ocurrencias de una palabra en los documentos, además del id de los documentos, se suelen indicar también factores ( TF-IDF , factor binario: “ya sea que la palabra toque el título o no”, otros factores) que son utilizado en la clasificación. El índice se puede construir no según todas las formas de las palabras , sino según los lemas (según las formas canónicas de las palabras). Las palabras vacías pueden excluirse y no construirse un índice para ellas, asumiendo que cada una de ellas aparece en casi todos los documentos del corpus. Para acelerar el cálculo de las intersecciones se utilizan heurísticas de skip-pointers . Cuando se procesan solicitudes que contienen muchas palabras, se utiliza la función de quórum, que salta a la siguiente etapa de clasificación de la parte de los documentos en la que no se encontraron todas las palabras de la solicitud.

Véase también

Notas

  1. ↑ Baeza-Yates, 1999 .
  2. ↑ Zobel, Moffat, Ramamohanarao, 1998 .

Literatura