Índice invertido

El índice invertido es muy simple en términos de estructura lógica e idea básica. Permítanme explicarlo con un ejemplo específico, para que todos puedan tener una idea macroscópica y directa sobre el índice invertido.

El chino se diferencia del inglés en que no hay separadores claros entre las palabras. Por lo tanto, primero debemos utilizar un sistema de segmentación de palabras para segmentar automáticamente un documento en secuencias de palabras, de modo que cada documento pueda convertirse en un flujo de datos compuesto por secuencias 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. Después del procesamiento, podemos obtener el índice invertido más simple (ver 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 de inversión es {1, 2, 3, 4, 5}, significa que todos los documentos de la colección de documentos contienen esta palabra.

La razón más simple para el índice invertido en la Figura 4 es porque este sistema de indexación solo registra qué documentos contienen una determinada palabra. De hecho, los sistemas de indexación pueden registrar mucha más información.

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

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

El práctico índice invertido también puede registrar más información. Además del número de documento y la información de frecuencia de palabras, el sistema de índice que se muestra en la Figura 6 también registra dos tipos de información, a saber, la información de frecuencia de documentos correspondiente a cada palabra (la tercera columna en la Figura 6) y la posición de la palabra en un documento.

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

Sin embargo, la información de posición de una palabra en un documento no necesariamente se registra en el sistema de indexación, sino que puede o no incluirse en el sistema de indexación real. La razón de esto es que esta información no es necesaria para el sistema de búsqueda y la información de ubicación solo puede resultar útil si admite consultas de frases.

Tome la palabra "Lars" como ejemplo: su recuento de palabras es 8 y su frecuencia de documentos 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; lt4 gt), (5; 1; lt4 gt)}, lo que indica que la palabra aparece tanto en el documento 3 como en el documento 5, la frecuencia de la palabra es 1 y la posición de aparición de la palabra "Lars" en ambos documentos es 4 , es decir, la cuarta palabra del documento es "Lars".

El índice invertido que se muestra en la Figura 6 ya es un sistema de índice muy completo, y la estructura de índice del motor de búsqueda real es básicamente la misma. La única diferencia es qué estructura de datos específica se utiliza para implementar la estructura lógica anterior.

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

Utilizando la información de frecuencia de términos y la información de frecuencia de documentos, estos resultados de búsqueda de candidatos se pueden ordenar, se calcula la similitud del documento con la consulta y el resultado se ordena de mayor a menor según la puntuación de similitud. Esta es la parte del sistema de búsqueda del proceso interno.

El diccionario de palabras es una parte muy importante del índice invertido. Se utiliza para mantener información sobre todas las palabras que aparecen en la colección de documentos y registrar la información de posición de una palabra en la tabla invertida correspondiente. archivo invertido. Cuando se admite la búsqueda, según las palabras de consulta del usuario, la lista invertida correspondiente se puede obtener buscando en el diccionario de palabras, y esto se puede utilizar como base para la clasificación posterior.

Para una colección de documentos a gran escala, puede contener cientos de miles o incluso millones de palabras diferentes. El hecho de que pueda localizar rápidamente una palabra afectará directamente la velocidad de respuesta durante la búsqueda. Por lo tanto, se necesitan estructuras de datos eficientes para crear y buscar diccionarios de palabras. Las estructuras de datos de uso común incluyen hash más estructura de lista vinculada y estructura 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 la estructura del árbol B. Una búsqueda de árbol b se diferencia de una búsqueda hash en que una búsqueda hash requiere que las entradas del diccionario estén ordenadas por tamaño (orden numérico o de caracteres), mientras que una búsqueda hash no requiere que los datos cumplan este requisito.

El árbol b es una estructura de búsqueda jerárquica. El nodo intermedio se utiliza para indicar en qué subárbol se almacenan los elementos del diccionario dentro de un cierto rango de clasificación y desempeña una función de navegación basada en el tamaño comparativo de los elementos del diccionario. El nodo hoja más bajo almacena 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 obtener más información, consulte [/hackerose 1994/article/details/5093396? número de ubicación = 11 amperios fps = 1)