Índice invertido

En Ciencias de la computación, un Índice invertido (también conocido como archivo de anuncios o archivo invertido) es un estructura de datos de índice almacenar una asignación de contenido, como palabras o números, a sus localizaciones en un archivo de base de datos, o en un documento o un conjunto de documentos. El propósito de un índice invertido es permitir el rápido búsquedas de texto completo, a un costo de procesamiento mayor cuando un documento se agrega a la base de datos. El archivo invertido sea el archivo de base de datos, en lugar de su Índice. Es la estructura de datos más popular utilizada en recuperación de documentos sistemas, utilizado en gran escala por ejemplo en motores de búsqueda. Varios importantes generales mainframe-base sistemas de gestión de base de datos han utilizado las arquitecturas lista invertida, incluyendo ADABAS, DATACOM/DB, y Modelo 204.

Hay dos variantes principales de índices invertidos: A nivel récord invertida Índice (o Índice de archivo invertido o simplemente archivo invertido) contiene una lista de referencias a los documentos de cada palabra. A nivel de palabra invertida Índice (o completo índice invertido o lista invertida) además contiene las posiciones de cada palabra dentro de un documento. La última forma ofrece más funcionalidad (como frase búsquedas), pero necesita más potencia de procesamiento y espacio para crear.

Ejemplo

Dado los textos

T [0] = "es lo que es" T [1] = "¿Qué es" T [2] = "es una banana"

Tenemos el siguiente índice de archivo invertido (donde los enteros en los soportes del sistema de notación se refieren a los índices (o llaves) de los símbolos de texto, T [0], T [1] etc.):

"a": {2} "banana": {2} "es": {0, 1, 2} "it": {0, 1, 2} "qué": {0, 1}

Búsqueda de un término para los términos "qué", "es" y "eso" daría el conjunto $\{0,1\} \cap \{0,1,2\} \cap \{0,1,2\} = \{0,1\}$.

Con los mismos textos, obtenemos el siguiente índice invertido completo, donde los pares son números de documento y palabra local. Como los números de documento, números locales palabra también comienzan con cero. Así que, "banana": {(2, 3)} significa que la palabra "banana" está en el tercer documento (T [2]), y es la cuarta palabra en ese documento (posición 3).

"a": {(2, 2)} "banana": {(2, 3)} "es": {(0, 1), (0, 4), (1, 1)(2, 1)} "it": {(0, 0), (0, 3), (1, 2)(2, 0)} "qué": {(0, 2), (1, 0)}

Si corremos la búsqueda de una frase para "¿Qué es" conseguir éxitos para todas las palabras en tanto el documento 0 y 1. Pero los términos consecutivamente ocurren solamente en documento 1.

Aplicaciones

El índice invertido estructura de datos es un componente central de un típico algoritmo de búsqueda del motor de indexación. Una meta de una implementación del motor de búsqueda es optimizar la velocidad de la consulta: encontrar los documentos donde se produce la palabra X. Una vez un Índice de avance es desarrollada, que almacena las listas de palabras por cada documento, a continuación se invierte para desarrollar un índice invertido. Consultar el índice de avance requeriría iteración secuencial a través de cada documento y cada palabra para verificar un documento coincidente. El tiempo, la memoria y recursos de procesamiento para realizar estas consultas no siempre son técnicamente realistas. En lugar de la lista de las palabras por cada documento en el índice de avance, se desarrolla la estructura de datos índice invertido que enumera los documentos por palabra.

Con el índice invertido creado, la consulta ahora puede resolverse por saltar a la identificación de la palabra (a través de acceso aleatorio) en el índice invertido.

En tiempos de la computadoras, concordancias libros importantes fueron montadas manualmente. Estos fueron los índices efectivamente invertidos con una pequeña cantidad de comentario de acompañamiento que requiere una enorme cantidad de esfuerzo para producir.

En Bioinformática, índices invertidos son muy importantes en la Asamblea de secuencia de fragmentos cortos de ADN secuenciado. Una manera de encontrar la fuente de un fragmento es buscar contra una secuencia de ADN de referencia. Un pequeño número de desajustes (debido a las diferencias entre el ADN y referencia ADN secuenciado, o errores) puede ser contabilizado dividiendo el fragmento en fragmentos más pequeños — por lo menos un subfragment es probable que coincida con la referencia de secuencia de ADN. El juego requiere construir un índice invertido de todos subcadenas de una cierta longitud de la secuencia de ADN de referencia. Puesto que el ADN humano contiene más de 3 billones de pares de bases, y tenemos que guardar una subcadena de ADN para cada índice y un entero de 32 bits para índice de sí mismo, el requisito de almacenamiento para este índice invertido probablemente sería de decenas de gigabytes.

Véase también

• Índice (buscador)
• Índice inverso
• Modelo de espacio vectorial

Bibliografía

• Knuth, D. E. (1997) [1973]. "6.5. recuperación de claves secundarias". The Art of Computer Programming (Tercera Ed.). Reading, Massachusetts: Addison-Wesley. ISBN0-201-89685-0.
• Zobel, Justin; Moffat, Alistair; Ramamohanarao, Kotagiri (diciembre de 1998). "Archivos invertidos versus archivos de firma para la indización de texto". ACM Transactions on Database Systems (Nueva York: Association for Computing Machinery) 23 (4): págs. 453 – 490. Doi:10.1145/296854.277632.
• Zobel, Justin RMIT University, Australia; Moffat, Alistair la Universidad de Melbourne, Australia (julio de 2006). "Archivos invertidos para motores de búsqueda de texto". ACM Computing Surveys (Nueva York: Association for Computing Machinery) 38 (2): 6. Doi:10.1145/1132956.1132959.
• Baeza-Yates, Ricardo; Ribeiro-Neto, Berthier (1999). Recuperación de información moderna. Reading, Massachusetts:: Addison-Wesley Longman. p. 192. ISBN0-201-39829-X.
• Luk, Robert; W el. lam (2007). "Eficiente en memoria extensible invertida file". Sistemas de información 32 (5): 733-754. Doi:10.1016/j.is.2006.06.001.
• Salton, Gerard; Fox, Edward A.; Wu, Harry (1983). "Recuperación de datos booleana extendida". Commun. ACM (ACM) 26 (11): 1022. Doi:10.1145/182.358466.
• Recuperación de información: Ejecución y evaluación de los motores de búsqueda. Cambridge, Massachusetts: MIT Press. 2010. ISBN978-0-262-02651-2.

Referencias

• Knuth 1997, págs. 560 – 563 de la sección 6.5: Recuperación de claves secundarias

Enlaces externos

• Diccionario de los algoritmos y estructuras de datos del NIST: índice invertido
• Gestión de Gigabytes para Java un motor de búsqueda de texto completo libre para las colecciones de gran documento escrito en Java.
• Lucene -Apache Lucene es una biblioteca de motor de búsqueda completa de texto escrita en Java.
• Búsqueda de esfinge -Alto rendimiento, completa el texto búsqueda motor biblioteca de código abierto usado por craigslist y otros empleando un índice invertido.
• Implementaciones de ejemplo en Código de Rosetta
• Caltech gran escala Image Search Toolbox:: una aplicación de archivo invertido de MATLAB bolsa-de-palabras búsqueda de la imagen.

Otras Páginas

• Lista de jefes de estado en 1774
• Complejo de Frankenstein
• JStik
• Hookflash
• Cosmesis
• Plataforma como servicio (redireccion de FCA)
• Graydon K. cocinas Jr.
• Live2support