Índice invertido

Índice invertido:

El índice invertido es muy simple en términos de estructura lógica e ideas básicas. A continuación lo explicaremos mediante ejemplos específicos para que todos puedan entender la Indexación invertida. Tiene un sentimiento macro y directo.

A diferencia de idiomas como el chino y el inglés, no existen delimitadores claros entre palabras, por lo que primero se debe utilizar un sistema de segmentación de palabras para dividir automáticamente el documento en una secuencia de palabras, de modo que cada documento se convierte en datos compuestos por una secuencia de palabras.

Para facilitar el procesamiento posterior del sistema, es necesario asignar un número de palabra único a cada palabra diferente y registrar qué documentos contienen esta palabra. Una vez completado el procesamiento, podemos obtener el. índice invertido más simple (consulte la Figura 4).

En la Figura 4, la columna "ID de palabra" registra el número correspondiente a cada palabra, la segunda columna es la palabra correspondiente y la tercera columna es la lista invertida correspondiente a cada palabra. Por ejemplo: la palabra "Google", donde el número de palabra es 1 y la lista invertida es {1, 2, 3, 4, 5}, lo que indica que todos los documentos de la colección de documentos contienen esta palabra.

La razón por la cual el índice invertido en la Figura 4 es el más simple es porque este sistema de índice solo registra qué documentos contienen una determinada palabra. De hecho, el sistema de indexación también puede registrar más información además de esto.

La Figura 5 es un índice invertido relativamente complejo. En comparación con el sistema de índice básico que se muestra en la Figura 4, la lista invertida correspondiente a una palabra no solo registra el número de documento, sino que también registra la frecuencia de la palabra. es decir, la cantidad de veces que aparece esta palabra en un documento. La razón por la que se registra esta información es porque la información de frecuencia de palabras es un factor de cálculo muy importante al calcular la similitud de consultas y documentos al ordenar los resultados de la búsqueda, por lo que se registra en la lista invertida para facilitar el cálculo de la puntuación durante la clasificación posterior.

En el ejemplo que se muestra en la Figura 5, el número de palabra de la palabra "fundador" es 7 y el contenido de la lista invertida correspondiente es (3; 1), donde 3 representa el documento con el número de documento 3. contiene Para esta palabra, el número 1 representa información de frecuencia de palabras, es decir, esta palabra solo aparece una vez en el documento No. 3, y las listas invertidas correspondientes a otras palabras tienen el mismo significado.

Los índices invertidos prácticos también pueden registrar más información. Además de registrar números de documentos e información de frecuencia de palabras, el sistema de índice que se muestra en la Figura 6 también registra dos tipos adicionales de información, es decir, cada palabra corresponde a The. información de frecuencia del documento (columna 3 de la Figura 6) y la información sobre la posición de aparición de la palabra en un documento.

La información de frecuencia de documentos representa cuántos documentos en la colección de documentos contienen una determinada palabra. La razón por la que se registra esta información es la misma que la información de frecuencia de palabras. Esta información es un factor importante en la clasificación de los resultados de búsqueda. Cálculo. Factor muy importante.

La información sobre la posición de una palabra en un documento no necesariamente es registrada por el sistema de indexación. El sistema de indexación real puede incluir o optar por no incluir esta información. no es necesario para el sistema de búsqueda, la información de ubicación solo es útil cuando admite consultas de frases.

Tome la palabra "Las" como ejemplo: su número de palabra es 8 y su frecuencia de documento es 2, lo que significa que hay dos documentos en toda la colección de documentos que contienen esta palabra y la lista invertida correspondiente. es {(3; 1;lt;4gt;), (5;1;lt;4gt;)}, lo que significa que esta palabra aparece en el documento 3 y en el documento 5, la frecuencia de la palabra es 1 y la palabra "Las" aparece en estos dos documentos Las posiciones de aparición son las 4, es decir, la cuarta palabra en el documento es "Las".

El índice invertido que se muestra en la Figura 6 ya es un sistema de índice muy completo. La estructura de índice del motor de búsqueda real es básicamente la misma. La diferencia no es más que qué estructuras de datos específicas se utilizan para implementarlo. encima de la estructura lógica.

Con este sistema de indexación, los motores de búsqueda pueden responder fácilmente a las consultas de los usuarios. Por ejemplo: el usuario ingresa el término de consulta "Facebook" y el sistema de búsqueda busca en el índice invertido, desde donde puede leer los documentos que contienen esta palabra. Estos documentos son los resultados de la búsqueda proporcionados al usuario.

Utilizando la información de frecuencia de palabras y la información de frecuencia de documentos, estos resultados de búsqueda de candidatos se pueden ordenar, se calcula la similitud entre documentos y consultas y el resultado se ordena de mayor a menor según la puntuación de similitud. el sistema de búsqueda algunos procesos internos.

El diccionario de palabras es una parte muy importante del índice invertido. Se utiliza para mantener la información relevante de todas las palabras que aparecen en la colección de documentos y también se utiliza para registrar la lista invertida correspondiente a un. determinada palabra. Información de posición en el archivo. Al admitir la búsqueda, de acuerdo con las palabras de consulta del usuario, vaya al diccionario de palabras para realizar la consulta y podrá obtener la lista invertida correspondiente, que puede usarse como base para la clasificación posterior.

Para una colección de documentos a gran escala, que puede contener cientos de miles o incluso millones de palabras diferentes, el hecho de que una palabra se pueda localizar rápidamente afecta directamente la velocidad de respuesta durante la búsqueda, por lo que es necesario disponer de datos eficientes. Las estructuras se utilizan para crear y buscar diccionarios de palabras. Las estructuras de datos más utilizadas incluyen estructuras de lista enlazada más hash y estructuras de diccionario de árbol.

El árbol B (o árbol B) es otra estructura de búsqueda eficiente. La Figura 8 es un diagrama esquemático de una estructura de árbol B. La búsqueda de árbol B es diferente de la búsqueda con el método hash, que requiere que los elementos del diccionario se ordenen por tamaño (orden numérico o de caracteres), mientras que el método hash no requiere datos para cumplir con este requisito.

El árbol B forma una estructura de búsqueda jerárquica. Los nodos intermedios se utilizan para indicar en qué subárbol se almacena un determinado rango de secuencia de elementos del diccionario y desempeñan un papel en la navegación basada en la comparación de tamaños del diccionario. elementos Los nodos de hoja más bajos almacenan la información de dirección de la palabra y la cadena de palabras se puede extraer en función de esta dirección.

Para más detalles, puedes echar un vistazo [ /hackerose1994/article/details/50933396?locationNum=11amp fps=1 )