Índice invertido

Un índice invertido es una estructura de datos de índice que almacena una asignación del contenido, como palabras o números, a sus ubicaciones en un documento o conjunto de documentos. En palabras simples, es una estructura de datos similar a un hashmap que lo dirige de una palabra a un documento o una página web. 

Hay dos tipos de índices invertidos: Un índice invertido a nivel de registro contiene una lista de referencias a documentos para cada palabra. Un índice invertido a nivel de palabra contiene además las posiciones de cada palabra dentro de un documento. La última forma ofrece más funcionalidad, pero necesita más potencia de procesamiento y espacio para ser creado. 

Supongamos que queremos buscar los textos «hola a todos», «este artículo se basa en un índice invertido», «que es una estructura de datos tipo hashmap». Si indexamos por (texto, palabra dentro del texto), el índice con ubicación en el texto es: 
 

 hello                (1, 1)
 everyone             (1, 2)
 this                 (2, 1)
 article              (2, 2)
 is                   (2, 3); (3, 2)
 based                (2, 4)
 on                   (2, 5)
 inverted             (2, 6)
 index                (2, 7)
 which                (3, 1)
 hashmap              (3, 3)
 like                 (3, 4)
 data                 (3, 5)
 structure            (3, 6)

La palabra «hola» está en el documento 1 («hola a todos») a partir de la palabra 1, por lo que tiene una entrada (1, 1) y la palabra «es» está en los documentos 2 y 3 en las posiciones ‘3ra’ y ‘2da’ respectivamente (aquí la posición se basa en la palabra). 
El índice puede tener pesos, frecuencias u otros indicadores. 

Pasos para construir un índice invertido:

• Obtener el documento 
  Eliminación de palabras vacías: las palabras vacías son las palabras más frecuentes e inútiles en documentos como «yo», «el», «nosotros», «es», «un».
• Derivación de la raíz de la palabra 
  Cada vez que quiero buscar «gato», quiero ver un documento que tenga información al respecto. Pero la palabra presente en el documento se llama “cats” o “catty” en lugar de “cat”. Para relacionar las dos palabras, cortaré una parte de todas y cada una de las palabras que leo para poder obtener la «palabra raíz». Existen herramientas estándar para realizar esto como «Porter’s Stemmer».
• Registrar ID de documento 
  Si la palabra ya está presente, agregue la referencia del documento al índice; de ​​lo contrario, cree una nueva entrada. Agregue información adicional como la frecuencia de la palabra, la ubicación de la palabra, etc.

Ejemplo:

Words                 Document
ant                   doc1
demo                  doc2
world                 doc1, doc2

Las ventajas del índice invertido son: 

• El índice invertido es para permitir búsquedas rápidas de texto completo, a costa de un mayor procesamiento cuando se agrega un documento a la base de datos.
• Es fácil de desarrollar.
• Es la estructura de datos más popular utilizada en los sistemas de recuperación de documentos, utilizada a gran escala, por ejemplo, en los motores de búsqueda.

El índice invertido también tiene desventajas: 

• Grandes gastos generales de almacenamiento y altos costos de mantenimiento en la actualización, eliminación e inserción.