Índice invertido

En ciencias de la información , un índice invertido (también conocido como lista de entradas , archivo de entradas o archivo invertido ) es un índice de base de datos que almacena una correspondencia entre el contenido, como palabras o números, y sus ubicaciones en una tabla , o en un documento o conjunto de documentos (en contraste con un índice directo , que asigna de documentos a contenido). ^{[ 1 ]} El propósito de un índice invertido es permitir búsquedas rápidas de texto completo , a costa de un mayor procesamiento cuando se agrega un documento a la base de datos. ^{[ 2 ]} El archivo invertido puede ser el propio archivo de la base de datos, en lugar de su índice. Es la estructura de datos más popular utilizada en sistemas de recuperación de documentos , ^{[ 3 ]} utilizada a gran escala, por ejemplo, en motores de búsqueda . Además, varios sistemas de gestión de bases de datos importantes de propósito general basados ​​en mainframes han utilizado arquitecturas de lista invertida, incluidos ADABAS , DATACOM/DB y Model 204 .

Existen dos variantes principales de índices invertidos: un índice invertido a nivel de registro (o índice de archivo invertido o simplemente archivo invertido ) contiene una lista de referencias a documentos para cada palabra. Un índice invertido a nivel de palabra (o índice invertido completo o lista invertida ) contiene además las posiciones de cada palabra dentro de un documento. ^{[ 4 ]} Esta última forma ofrece más funcionalidad (como búsquedas de frases ), pero requiere mayor potencia de procesamiento y espacio para su creación.

La estructura de datos del índice invertido es un componente central de un algoritmo de indexación típico de un motor de búsqueda . ^{[ 5 ]} Un objetivo de la implementación de un motor de búsqueda es optimizar la velocidad de la consulta: encontrar los documentos donde aparece la palabra X. ^{[ 6 ]} Una vez que se desarrolla un índice directo , que almacena listas de palabras por documento, se invierte para desarrollar un índice invertido. Consultar el índice directo requeriría una iteración secuencial a través de cada documento y a cada palabra para verificar un documento coincidente. El tiempo, la memoria y los recursos de procesamiento para realizar dicha consulta no siempre son técnicamente realistas. En lugar de listar las palabras por documento en el índice directo, se desarrolla la estructura de datos del índice invertido que lista los documentos por palabra.

Una vez creado el índice invertido, la consulta se puede resolver saltando al ID de palabra (mediante acceso aleatorio ) en el índice invertido.

En la época anterior a la informática, las concordancias de libros importantes se elaboraban manualmente. Se trataba, en esencia, de índices invertidos con un breve comentario explicativo, cuya producción requería un enorme esfuerzo.

En bioinformática, los índices invertidos son fundamentales para el ensamblaje de secuencias de fragmentos cortos de ADN secuenciado. Una forma de determinar el origen de un fragmento es compararlo con una secuencia de ADN de referencia. Un pequeño número de discrepancias (debido a diferencias entre el ADN secuenciado y el de referencia, o a errores) se pueden corregir dividiendo el fragmento en subfragmentos más pequeños; es probable que al menos uno de ellos coincida con la secuencia de ADN de referencia. Esta comparación requiere la construcción de un índice invertido con todas las subcadenas de una longitud determinada a partir de la secuencia de ADN de referencia. Dado que el ADN humano contiene más de 3 mil millones de pares de bases, y necesitamos almacenar una subcadena de ADN para cada índice y un entero de 32 bits para el índice en sí, el espacio de almacenamiento necesario para dicho índice invertido probablemente sería de decenas de gigabytes.

Por razones históricas, la compresión de listas invertidas y la compresión de mapas de bits se desarrollaron como líneas de investigación separadas, y solo más tarde se reconoció que resolvían esencialmente el mismo problema. ^{[ 7 ]}

• Índice (motor de búsqueda)
• Índice inverso
• modelo de espacio vectorial

• Diccionario de algoritmos y estructuras de datos del NIST: índice invertido
• Managing Gigabytes for Java es un motor de búsqueda de texto completo gratuito para grandes colecciones de documentos escrito en Java.
• Lucene - Apache Lucene es una biblioteca de motor de búsqueda de texto con todas las funciones escrita en Java.
• Sphinx Search : biblioteca de motor de búsqueda de texto de código abierto, de alto rendimiento y con todas las funciones, utilizada por Craigslist y otros sitios que emplean un índice invertido.
• Ejemplos de implementación en Rosetta Code
• Caja de herramientas de búsqueda de imágenes a gran escala de Caltech : una caja de herramientas de Matlab que implementa la búsqueda de imágenes mediante el método de bolsa de palabras de archivos invertidos.