¿Qué es el índice invertido? Es un hecho bien conocido que necesita crear índices para implementar búsquedas eficientes. ¿Cuál es la diferencia entre el índice y el índice invertido, y cómo se construye el índice invertido?


Respuesta 1:

Índice invertido

La búsqueda elástica utiliza una estructura llamada índice invertido, que está diseñada para permitir búsquedas de texto completo muy rápidas. Un índice invertido consiste en una lista de todas las palabras únicas que aparecen en cualquier documento, y para cada palabra, una lista de los documentos en los que aparece.

Por ejemplo, supongamos que tenemos dos documentos, cada uno con un campo de contenido que contiene lo siguiente:

  1. El rápido zorro marrón saltó sobre el perro perezoso Los zorros marrones rápidos saltaron sobre los perros perezosos en verano

Para crear un índice invertido, primero dividimos el campo de contenido de cada documento en palabras separadas (que llamamos términos o tokens), creamos una lista ordenada de todos los términos únicos y luego enumeramos en qué documento aparece cada término. El resultado se parece a esto:

Término Doc_1 Doc_2
-------------------------
Rápido | El | X
El | X |
marrón | X | X
perro | X |
perros | El | X
zorro | X |
zorros | El | X
en | El | X
saltó | X |
perezoso | X | X
salto | El | X
sobre | X | X
rápido | X |
verano | El | X
el | X |
------------------------

Ahora, si queremos buscar marrón rápido, solo necesitamos encontrar los documentos en los que aparece cada término:

Término Doc_1 Doc_2
-------------------------
marrón | X | X
rápido | X |
------------------------
Total | 2 | 1

Ambos documentos coinciden, pero el primer documento tiene más coincidencias que el segundo. Si aplicamos un ingenuo algoritmo de similitud que solo cuenta el número de términos coincidentes, entonces podemos decir que el primer documento es una mejor coincidencia (es más relevante para nuestra consulta) que el segundo documento.

Pero hay algunos problemas con nuestro índice invertido actual:

  • Rápido y rápido aparecen como términos separados, mientras que el usuario probablemente piensa en ellos como la misma palabra. Zorro y zorros son bastante similares, al igual que perro y perros; Comparten la misma palabra raíz. Saltar y saltar, aunque no son de la misma palabra raíz, tienen un significado similar. Son sinónimos

Con el índice anterior, una búsqueda de + Quick + fox no coincidiría con ningún documento. (Recuerde, un signo + anterior significa que la palabra debe estar presente). Tanto el término rápido como el término zorro tienen que estar en el mismo documento para satisfacer la consulta, pero el primer documento contiene rápido zorro y el segundo documento contiene rápido zorros

Nuestro usuario podría esperar razonablemente que ambos documentos coincidan con la consulta. Podemos hacerlo mejor.

Si normalizamos los términos en un formato estándar, entonces podemos encontrar documentos que contienen términos que no son exactamente los mismos que el usuario solicitó, pero que son lo suficientemente similares como para ser relevantes. Por ejemplo:

  • Rápido se puede poner en minúsculas para convertirse en rápido. Los zorros se pueden detener, reducir a su forma raíz, para convertirse en zorro. Del mismo modo, los perros podrían derivarse de dog.jumped y leap son sinónimos y se pueden indexar como el salto de término único.

Ahora el índice se ve así:

Término Doc_1 Doc_2
-------------------------
marrón | X | X
perro | X | X
zorro | X | X
en | El | X
saltar | X | X
perezoso | X | X
sobre | X | X
rápido | X | X
verano | El | X
el | X | X
------------------------

Pero aún no hemos llegado. Nuestra búsqueda de + Quick + fox todavía fallaría, porque ya no tenemos el término exacto Quick en nuestro índice. Sin embargo, si aplicamos las mismas reglas de normalización que utilizamos en el campo de contenido a nuestra cadena de consulta, se convertiría en una consulta para + quick + fox, ¡que coincidiría con ambos documentos!

Nota: - Esto es muy importante. Solo puede encontrar términos que existan en su índice, por lo que tanto el texto indexado como la cadena de consulta deben normalizarse en la misma forma.

Referencia: La guía definitiva [2.x] | Elástico


Respuesta 2:

En palabras simples, es un hashmap como estructura de datos que lo dirige de una palabra a un documento o una página web.

Miremos el problema desde otra dirección. Tiene millones de documentos, páginas web o imágenes, todo lo que necesitemos recuperar más tarde. Para ayudar más a su intuición sobre la indexación y la recuperación de información al usarla, le recordaré que ha visto el índice invertido anteriormente.

Este es un ejemplo de un libro de texto aleatorio. Si necesita información sobre algún tema, por ejemplo, energías de activación, abrirá el índice y descubrirá si esa palabra. El índice invertido le dirá los números de página donde se explica esa palabra en una gran cantidad de mil páginas.

¡Lo ves! Si realizara una búsqueda lineal regular, tardaría horas en llegar a esa página. Pero ahora apenas era cuestión de segundos.

Entonces, ¿cómo se ve un índice regular?

Por supuesto, justo enfrente de él. Asigna el número de página a los temas. Y puede decir fácilmente que no son tan útiles en el área de búsqueda y extracción de información. (Quizás tengan buena suerte en otro lugar). En el caso de la búsqueda de Facebook, se utilizan para fines de clasificación (puntuación) para que obtenga los resultados más relevantes más altos.

Cómo construir un índice invertido La construcción de un índice invertido para mantener cualquier tipo de sistema de búsqueda requiere que realice una serie de pasos mientras analiza las páginas o documentos. Hagamos un recorrido mientras construimos nuestro propio motor de búsqueda.

Quiero crear un motor de búsqueda para todos los documentos en mi computadora. Sé lo que busco. Así que ejecutaré un programa que recorrerá todo el árbol en mis discos duros y recogeré las páginas que quiero. Sé que los archivos mp3 y jpegs no me sirven. Le pediré a mi programa que recupere los archivos txt, doc y pdf. Entonces, una vez que obtengo un documento, procedo al siguiente paso.

1. Obtención del documento El trabajo es realmente simple si obtengo un archivo de texto (.txt). Pero si era un documento o un pdf, tendré que analizarlos usando algunas bibliotecas para recuperar su texto. Digamos que tengo éxito en leer el texto. ¿Qué sigue?

2. Eliminando las palabras de detención Considere el último párrafo. ¿Cuáles fueron las palabras importantes que podríamos estar buscando? "texto", "bibliotecas", "doc", "pdf", "recuperar", "exitoso". Pero la mayoría de las otras palabras son solo un desperdicio. Denotamos las palabras más frecuentes como "palabras de detención" y las eliminamos para que no obtenga índices de palabras como "I", "the", "we", "is", "an". En uso regular, tenemos una lista de 500-1000 palabras. Pero puede diferir según el uso.

3. Stem to the Root Word Luego viene Stemming. Ahora, cada vez que quiero buscar "recuperación", quiero ver un documento que tenga información al respecto. Pero la palabra presente en el documento se llama "recuperar" en lugar de "recuperar". Para relacionar ambas palabras, cortaré una parte de cada una de las palabras que leí para poder obtener la "palabra raíz". Recuperar puede convertirse en "retriev". Así será "recuperación". Tenemos que estar seguros de las reglas que usamos para cortar las palabras. Existen herramientas estándar para realizar esto como "Porter's Stemmer". Puedes jugar con un porter stemmer aquí: Porter Stemmer Online

4. Registre las identificaciones de los documentos Ahora prepárese para la tarea principal: indexación. Cada documento que tengo tiene una identificación de documento única. Cuando encuentro una palabra ininterrumpida que se deriva ahora, la guardo en mi memoria en la forma: retriev ==> docID104007

Si recibo la misma palabra en algún otro documento, puedo escribirretriev ==> docID104007retriev ==> docID154033

Pero muy pronto tengo que combinarlos en una sola listaretriev ==> docID104007 y docID154033

Puedo mejorar aún más escribiendo cuántas veces se produjo la palabra en el documento para que podamos clasificar los documentos más importantes durante la recuperación. retriev ==> docID104007 | 5 | & docID154033 | 2 |

5. Combinar y almacenar los términos Finalmente, los guardamos en archivos de disco. Es genial si clasificamos el índice en función de las palabras para una recuperación rápida y fácil.

Obviamente, todo esto necesita algunas estructuras de datos específicas que simplifiquen su trabajo.

Podemos construir más índices secundarios para mejorar la recuperación. También hay muchos problemas relacionados con la clasificación.

Espero que esto te haya explicado cómo se crean los índices invertidos. Si desea leer más, puede consultar un impresionante libro Introducción a la recuperación de información escrito por Chris Manning, disponible en línea de forma gratuita.