Domina cómo crear un "índice invertido"
Según los diferentes estándares de clasificación, existen muchos tipos de índices, y hay más de cuatro tipos de uso común, y el más crítico es la tecnología de "índice invertido".
Este artículo es un artículo que presenta el método de creación de un índice invertido.
Matriz de documentos de Word
Un modelo conceptual para expresar la relación entre ellos
Archivo
Objetos de almacenamiento de texto, incluidos Word, Archivos; en diferentes formatos como PDF, html, XML, etc., así como mensajes de texto, Weibo, etc.;
Colección de literatura
Colección de varios documentos, como por ejemplo un gran cantidad de páginas web, gran cantidad de correos electrónicos, etc.
Número de documento
En la colección de documentos del buscador, a cada documento se le asigna un número interno único y diferente al resto de documentos, generalmente representado por DocID;
Word
La unidad de indexación de un motor de búsqueda;
Diccionario de palabras
Una colección de cadenas que consta de todas las palabras que aparecen en una colección de documentos que registra un; palabra La información de posición de la lista de inversión correspondiente en el archivo de inversión
Número de palabras
En el diccionario de palabras dentro del motor de búsqueda, a cada palabra se le asigna un número único que es diferente. de otras palabras: un número interno único;
Tabla de clasificación invertida
Un conjunto de elementos invertidos que registra "todos los documentos en los que aparece una palabra" y "la información de posición de la palabra en el documento". ";
Archivo invertido
Un archivo físico que almacena secuencialmente la lista invertida de todas las palabras;
Índice invertido
Está compuesto de diccionario de palabras y lista invertida La composición de archivos organizados es una forma de almacenamiento específica de la matriz de documentos de palabras y es la mejor manera de realizar la relación de mapeo entre palabras y documentos (según la palabra, puede obtener rápidamente una lista de documentos que contienen la palabra ).
Por ejemplo, para la siguiente colección de documentos
Para crear un índice invertido:
1. El sistema de segmentación de palabras divide automáticamente el documento en secuencias de palabras. y cada documento se convierte en un flujo de datos compuesto por secuencias de palabras;
2. Asigne un número de palabra único (ID) a cada palabra diferente y registre la frecuencia del documento correspondiente a cada palabra (en el documento). colección, incluya un cierto El número de documentos que contienen una palabra (como proporción del número total de documentos), incluido el número de documento (DocID) correspondiente a la palabra, la frecuencia de palabras (TF) en cada documento correspondiente (el número de veces que aparece la palabra en un documento) y el número de veces que aparece la palabra en un documento. La posición (POS) donde aparece en un documento.
3. Los resultados del índice invertido son los siguientes:
Interpretación: tome la palabra "salto de trabajo" como ejemplo. Su recuento de palabras es 4 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 {(1;1;& lt4 & gt),(4; 1;& lt4 & gt)}, es decir, esta palabra aparece en los archivos 1 y 4, y la frecuencia de la palabra es 1. La palabra "salto de trabajo" aparece en la posición 4 en ambos archivos, que es la cuarta posición en el archivo. La primera palabra es "salto de trabajo".
Diccionario de palabras
Registra la información de posición de la lista invertida correspondiente a una palabra en el archivo invertido y admite la presentación de listas invertidas basadas en palabras de consulta en las búsquedas.
Para grandes colecciones de documentos que contienen miles de palabras, es necesario crear y buscar diccionarios basados en estructuras de datos eficientes, y "hash más lista enlazada" y "diccionario de árbol" son representantes de este tipo de estructura de datos. .
¿A.? Estructura del diccionario Hash plus lista enlazada
Hash plus lista enlazada: consta de una "tabla hash" y una "lista enlazada en conflicto", de las cuales la tabla hash es el cuerpo principal. Cada tabla hash almacena un puntero a una lista de conflictos; cada lista de conflictos consta de palabras con el mismo valor hash y un grupo de palabras con el mismo valor hash se denomina conflicto.
El proceso de creación del diccionario: primero use la función hash para obtener el valor hash de la palabra t que aparece en el proceso de análisis del nuevo documento y luego lea el puntero en la tabla hash correspondiente de acuerdo con el hash; valor y busque el correspondiente de acuerdo con el puntero Lista vinculada de conflictos, y la palabra que no existe en la lista vinculada de conflictos se agrega a la lista vinculada de conflictos como la primera palabra. A medida que se analizan los documentos, se construyen los diccionarios correspondientes.
Proceso de respuesta a consulta: similar al proceso de creación de diccionario, excepto que no se agregan palabras que no están en el diccionario.
B.? Estructura de diccionario de árbol
La estructura de diccionario de árbol (también llamada árbol B o árbol B+) consta de nodos intermedios y el nodo hoja más bajo. Es una estructura de consulta jerárquica eficiente.
Requiere que los elementos del diccionario se ordenen por tamaño. El nodo medio indica en qué subárbol se almacenan los elementos del diccionario de un determinado rango de clasificación, y la navegación se basa en el tamaño comparativo de los elementos del diccionario más bajos; El nodo hoja almacena información de direcciones de palabras. Las cadenas de palabras se pueden extraer en función de las direcciones.
Lista invertida
Como mencionamos anteriormente, la lista invertida es una colección de elementos de índice invertidos (una matriz unidimensional de "un documento de texto") que almacena todas las palabras y Número de documento, frecuencia de palabras, ubicación y otra información.
Sin embargo, en los motores de búsqueda reales, para facilitar la compresión, el espacio del número de documento (D-Gap) a menudo se utiliza para reemplazar el número de documento real para garantizar que el número de documento en la tabla invertida sea mayor. que el primero. Por lo tanto, la diferencia del número de documento suele ser un número entero mayor que 0. Por ejemplo, correspondientes a los números de documento originales 187, 196 y 199, las diferencias numéricas podrían ser 187, 9 y 3.
1. Método de recorrido de documentos de dos pasadas
Dos recorridos de documentos, es decir, dos escaneos de documentos, y el proceso de creación depende completamente de la memoria.
Primer recorrido del documento
El primer escaneo tiene dos propósitos: primero, obtener estadísticas globales (el número de documentos n contenidos en el conjunto de documentos, el número de palabras diferentes contenidas en el conjunto de documentos m, la información DF en cuántos documentos aparece cada palabra, el tamaño de memoria requerido obtenido sumando los valores DF de todas las palabras) y, en segundo lugar, asigne espacio de almacenamiento, establezca una tabla de inversión correspondiente a la palabra en; la memoria La información de ubicación (según el valor DF de cada palabra, el área de almacenamiento se divide en segmentos de diferentes tamaños, y diferentes palabras corresponden a las posiciones inicial y final de los segmentos de memoria a los que pertenecen mediante punteros).
Después del primer análisis, prepare los recursos para el segundo análisis.
El segundo recorrido del documento
El segundo recorrido del documento establece formalmente la información de la lista invertida para cada palabra. Mientras escanea, el espacio de memoria asignado simplemente se llena. El segmento de memoria correspondiente a cada palabra se ha creado como una lista invertida de esa palabra.
Después de dos escaneos, se puede crear el índice y escribir en el disco la lista invertida de información de memoria y diccionario.
Ventajas y desventajas: depende completamente de la memoria y requiere suficiente espacio de memoria; leer y analizar documentos desde el disco lleva mucho tiempo y es muy lento.
2. Método de clasificación
A "durante el proceso de creación del índice, siempre se asigna un tamaño fijo de espacio en la memoria para almacenar información del diccionario e indexar resultados intermedios. Cuando el espacio asignado Cuando se agota, el método de "escribir los resultados intermedios en el disco y borrar la memoria para una nueva ronda de almacenamiento de índice intermedio" es una mejora con respecto a atravesar el índice dos veces.
Clasificación de almacenamiento de resultados intermedios
A. Leer el documento y asignarle una ID de documento única
b. Analizar el contenido del documento y proporcionar la información en el; documento. A la palabra que aparece se le asigna un ID de palabra único (la palabra que aparece por primera vez debe insertarse después de asignar el ID
c. ID de palabra", "ID de documento" y "frecuencia de palabra" La entrada de la lista invertida de la información se agrega al final del área de almacenamiento de resultados intermedios; el procesamiento anterior se realiza en todos los documentos por turno hasta que se procesen todos los documentos.
d. A medida que la memoria que almacena los resultados intermedios se llena gradualmente, ordene los resultados intermedios de los triples, cambie los elementos del índice invertido correspondientes a cada palabra en una forma ordenada y cambie la tabla de inversión ordenada. escrito en el disco. Principio de clasificación: la clave principal es la ID de la palabra, es decir, la ID de la palabra se ordena de pequeña a grande; la clave secundaria es la ID del documento, es decir, bajo la misma ID de palabra, la ID del documento se ordena de pequeña a grande; .
e. Repita el proceso de procesamiento anterior. Después de procesar todos los archivos, combine los archivos de resultados intermedios generados en cada ronda en el disco.
Fusión de archivos de resultados intermedios
Fusiona los datos ordenados de cada búfer almacenando los resultados intermedios en el orden de ID de palabra para formar una tabla invertida y escribirla en el índice final. Al mismo tiempo, se borra cada búfer y se realiza una nueva ronda de operaciones de lectura triple. Cuando todos los archivos de resultados intermedios se han leído en el búfer, se genera el archivo de índice final.
Ventajas y desventajas: Sólo los resultados intermedios se escriben en el disco y la información del diccionario siempre se mantiene en la memoria. A medida que la memoria continúa ocupada, cada vez habrá menos memoria disponible para resultados intermedios posteriores.
3. Método de combinación
El método de combinación es una mejora del método de clasificación. Cada vez que se escriben datos de la memoria en el disco, la información del resultado intermedio, incluido el diccionario, también se escribe en el disco, borrando así la memoria y estableciendo una cuota de memoria para el procesamiento posterior.
Subíndice de inversión
Crea un índice invertido completo establecido en la memoria para el subconjunto de documentos actualmente procesados;
Escribe el índice invertido en un archivo temporal
Cuando la memoria está llena, se escribe un conjunto de índices invertidos en el archivo temporal en el orden "primero el diccionario, último la lista invertida" y se borra la memoria.
Fusionar listas invertidas parciales
Fusionar las listas invertidas parciales correspondientes a cada palabra para formar la lista invertida de palabras final; al mismo tiempo, se forma el diccionario final durante el proceso de fusión.