Índices Invertidos

Un índice invertido asigna cada término de una colección a una lista de ocurrencias de los documentos que lo contienen, lo que permite a un sistema de búsqueda encontrar documentos coincidentes sin escanear cada documento.

Definition

Un índice invertido es una estructura de datos que consiste en un diccionario de términos indexados, cada uno apuntando a una lista de ocurrencias que enumera los documentos que contienen el término, a menudo anotada con frecuencias y posiciones de términos, de modo que la recuperación se puede realizar intersecando o fusionando listas de ocurrencias.

Scope

Este tema cubre la estructura y construcción del índice invertido: el diccionario de términos, las listas de ocurrencias que registran los identificadores de documentos, las frecuencias de términos y las posiciones, y los algoritmos que construyen y actualizan los índices en grandes colecciones, incluyendo la indexación basada en clasificación por bloques y la indexación en memoria de una sola pasada. Aborda la información posicional para las consultas de frases y la ingeniería del mantenimiento del índice, dejando la compresión y la estrategia de evaluación de consultas para temas adyacentes.

Core questions

• ¿Qué contiene una entrada de diccionario y su lista de ocurrencias?
• ¿Cómo se almacenan las posiciones para admitir consultas de frases y de proximidad?
• ¿Cómo se construye un índice invertido cuando la colección es demasiado grande para la memoria?
• ¿Cómo se actualiza un índice a medida que se añaden, modifican o eliminan documentos?
• ¿Cómo admiten las listas de ocurrencias una intersección eficiente para consultas conjuntivas?

Key concepts

• diccionario de términos
• lista de ocurrencias
• identificadores de documentos
• índice posicional
• almacenamiento de frecuencia de términos
• indexación basada en clasificación por bloques (BSBI)
• indexación en memoria de una sola pasada (SPIMI)
• fusión y actualizaciones de índices

Key theories

Organización del diccionario y las ocurrencias

Separar un diccionario de términos compacto de las listas de ocurrencias de longitud variable permite al sistema buscar un término rápidamente y luego transmitir solo los documentos relevantes, lo que constituye la base estructural de toda recuperación de índice invertido.

Construcción de índices escalables

Los métodos basados en disco, como la indexación basada en clasificación por bloques y la indexación en memoria de una sola pasada, construyen archivos invertidos para colecciones mucho más grandes que la memoria mediante la acumulación y fusión de índices parciales.

Clinical relevance

El índice invertido es la estructura de datos central de prácticamente todos los sistemas de búsqueda de texto, incluyendo los motores de búsqueda web, las plataformas de búsqueda de código abierto como Lucene y sus derivados, y la búsqueda de texto completo de bases de datos. Su diseño rige qué tipos de consultas son compatibles y con qué rapidez y a qué costo se pueden responder.

History

Los archivos invertidos se utilizaron en los primeros sistemas de recuperación bibliográfica y se convirtieron en la estructura estándar para la búsqueda de texto completo a medida que las colecciones crecían. La investigación en las décadas de 1990 y 2000, incluyendo métodos de construcción escalables como la indexación en memoria de una sola pasada, hizo práctico indexar corpus a escala web, y la estructura ahora sustenta bibliotecas de búsqueda de código abierto ampliamente utilizadas.

Key figures

• Justin Zobel
• Alistair Moffat
• Steffen Heinz

Seminal works

• zobel2006
• heinz2003
• manning2008

Frequently asked questions

¿Por qué se llama índice 'invertido'?

Un índice normal (directo) enumera, para cada documento, los términos que contiene. El índice invertido invierte este mapeo para listar, para cada término, los documentos que lo contienen. Esta inversión es precisamente lo que hace que la búsqueda basada en términos sea rápida.

¿Para qué se utiliza un índice posicional?

Un índice posicional almacena las posiciones en las que aparece cada término dentro de cada documento. Esto permite al sistema responder a consultas de frases y consultas de proximidad, donde el orden o la cercanía de los términos importa, en lugar de solo si los términos aparecen en algún lugar del documento.