En informática , un índice invertido (también conocido como archivo de publicaciones o archivo invertido ) es un índice de base de datos que almacena un mapeo de contenido, como palabras o números, a sus ubicaciones en una tabla , o en un documento o un conjunto de documentos (nombrados en contraste con un índice de avance , que se asigna de los documentos al contenido). El propósito de un índice invertido es permitir búsquedas rápidas de texto completo , a un costo de mayor procesamiento cuando se agrega un documento a la base de datos. El archivo invertido puede ser el archivo de la base de datos en sí, en lugar de su índice. Es la estructura de datos más popular utilizada en los sistemas de recuperación de documentos ,[1] utilizado a gran escala, por ejemplo, en motores de búsqueda . Además, varias significativa de propósito general de mainframe basada en sistemas de gestión de bases de datos han utilizado arquitecturas lista invertidos, incluyendo ADABAS , DATACOM / DB y Modelo 204 .
Hay 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. [2] La última forma ofrece más funcionalidad (como búsquedas de frases ), pero necesita más potencia de procesamiento y espacio para crearse.
La estructura de datos de índice invertido es un componente central de un algoritmo de indexación de motor de búsqueda típico . 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. Una vez que se desarrolla un índice hacia adelante , que almacena listas de palabras por documento, luego se invierte para desarrollar un índice invertido. Consultar el índice de reenvío requeriría una iteración secuencial a través de cada documento y 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 enumerar las palabras por documento en el índice de avance, se desarrolla la estructura de datos del índice invertido que enumera los documentos por palabra.
Con el índice invertido creado, la consulta ahora se puede resolver saltando al ID de la palabra (mediante acceso aleatorio ) en el índice invertido.
En tiempos anteriores a la informática, las concordancias con libros importantes se ensamblaban manualmente. Estos eran índices efectivamente invertidos con una pequeña cantidad de comentarios que los acompañaban y que requerían una enorme cantidad de esfuerzo para producirlos.
En bioinformática, los índices invertidos son muy importantes en el ensamblaje de secuencias.de fragmentos cortos de ADN secuenciado. Una forma de encontrar la fuente de un fragmento es buscarlo frente a una secuencia de ADN de referencia. Un pequeño número de desajustes (debido a diferencias entre el ADN secuenciado y el ADN de referencia, o errores) se puede explicar dividiendo el fragmento en fragmentos más pequeños; es probable que al menos un subfragmento coincida con la secuencia del ADN de referencia. El emparejamiento requiere construir un índice invertido de todas las subcadenas de una cierta longitud 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 requisito de almacenamiento para tal índice invertido probablemente sería de decenas de gigabytes.