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 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 directo , que asigna los documentos al 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 archivo de la base de datos en sí, 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 importantes sistemas 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. [4] La última forma ofrece más funcionalidad (como búsquedas de frases ), pero necesita más potencia de procesamiento y espacio para ser creada.
La estructura de datos de índice invertido es un componente central de un algoritmo de indexación de motor de búsqueda típico . [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, a continuación 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 necesarios para realizar dicha consulta 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 se puede resolver saltando a la palabra ID (mediante acceso aleatorio ) en el índice invertido.
En la época anterior a las computadoras, las concordancias con libros importantes se recopilaban manualmente. Se trataba efectivamente de índices invertidos con una pequeña cantidad de comentarios adjuntos que requirieron un enorme 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 en una secuencia de ADN de referencia. Un pequeño número de discrepancias (debido a diferencias entre el ADN secuenciado y el ADN de referencia, o errores) se pueden 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 una determinada 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 un índice invertido de este tipo 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 sólo más tarde se reconoció que resolvían esencialmente el mismo problema. [7]