Hispanopedia WikiEn informática , un índice invertido (también denominado 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 (nombrado en contraste con un índice hacia adelante , que asigna 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 archivo de 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 sistemas de gestión de bases de datos importantes basados en mainframe de propósito general 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] La última forma ofrece más funcionalidad (como búsquedas de frases ), pero necesita más potencia de procesamiento y espacio para crearse.
Aplicaciones
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 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 de índice invertido que enumera los documentos por palabra.
Con el índice invertido creado, la consulta 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 armaban manualmente. Se trataba, en realidad, de índices invertidos con una pequeña cantidad de comentarios que requerían un enorme esfuerzo para su elaboración.
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. Una pequeña cantidad de desajustes (debidos 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 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 mismo, el requisito de almacenamiento para un índice invertido de este tipo probablemente sería de decenas de gigabytes.
Compresión
Por razones históricas, la compresión de lista invertida y la compresión de mapa 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]
Véase también
Referencias
- ^ Knuth, DE (1997) [1973]. "6.5. Recuperación de claves secundarias". El arte de la programación informática (tercera edición). Reading, Massachusetts : Addison-Wesley . ISBN 0-201-89685-0.
- ^ Salton, Gerard; Fox, Edward A.; Wu, Harry (noviembre de 1983). "Recuperación de información booleana extendida". Comunicaciones de la ACM . 26 (11): 1022– 1036. doi :10.1145/182.358466. hdl : 1813/6351 .
- ^ Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri (diciembre de 1998). "Archivos invertidos versus archivos de firma para indexación de texto". ACM Transactions on Database Systems . 23 (4). Nueva York: Association for Computing Machinery : 453– 490. doi : 10.1145/296854.277632 . S2CID 7293918.
- ^ Baeza-Yates, Ricardo ; Ribeiro-Neto, Berthier (1999). Recuperación de información moderna . Reading, Massachusetts : Addison-Wesley Longman. p. 192. ISBN 0-201-39829-X.
- ^ Zobel, Justin; Moffat, Alistair (julio de 2006). "Archivos invertidos para motores de búsqueda de texto". Encuestas de informática de la ACM . 38 (2). Nueva York: Association for Computing Machinery : 6. doi :10.1145/1132956.1132959. S2CID 207158957.
- ^ Recuperación de información: implementación y evaluación de motores de búsqueda. Cambridge, Massachusetts: MIT Press. 2010. ISBN 978-0-262-02651-2Archivado desde el original el 5 de octubre de 2020. Consultado el 8 de agosto de 2010 .
- ^ Wang, Jianguo; Lin, Chunbin; Papakonstantinou, Yannis; Swanson, Steven (9 de mayo de 2017). "Un estudio experimental de la compresión de mapas de bits frente a la compresión de listas invertidas". Actas de la Conferencia internacional ACM de 2017 sobre gestión de datos . Association for Computing Machinery. págs. 993– 1008. doi :10.1145/3035918.3064007 . Consultado el 1 de mayo de 2023 .
Enlaces externos
- 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 escritos 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 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 bolsa de palabras de archivo invertido.