En informática , un índice invertido (también conocido como lista de publicaciones, archivo de publicaciones o archivo invertido ) es un índice de base de datos que almacena una asignación del 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 directo , que se asigna de documentos a contenido). 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. 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 ensistemas de recuperación de documentos , [1] utilizados a gran escala, por ejemplo, en motores de búsqueda . Además, varios sistemas importantes de gestión de bases de datos basados en mainframe de propósito general han utilizado arquitecturas de lista invertida, incluidos ADABAS , DATACOM/DB y Model 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 funciones (como búsquedas de frases ), pero necesita más capacidad 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 directo , que almacena listas de palabras por documento, luego se invierte para desarrollar un índice invertido. Consultar el índice directo 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 una consulta de este tipo no siempre son técnicamente realistas. En lugar de enumerar las palabras por documento en el índice directo, 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 a la palabra ID (a través de acceso aleatorio ) en el índice invertido.
En la época anterior a la informática, las concordancias de libros importantes se recopilaban manualmente. Estos eran índices efectivamente invertidos con una pequeña cantidad de comentarios adjuntos que requerían una enorme cantidad de esfuerzo para producir.
En bioinformática, los índices invertidos son muy importantes en el ensamblaje de secuencias.de fragmentos cortos de ADN secuenciado. Una forma de encontrar el origen de un fragmento es buscarlo en una secuencia de ADN de referencia. Una pequeña cantidad de discrepancias (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 de ADN de referencia. La coincidencia requiere la construcción de un índice invertido de todas las subcadenas de 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 número entero de 32 bits para el índice en sí, el requisito de almacenamiento para dicho índice invertido probablemente sería de decenas de gigabytes.