algorithm - fulltext - Uso de índices para consultas de varias palabras en la búsqueda de texto completo(por ejemplo, búsqueda web)

match against mysql ejemplo (4)

Entiendo que un aspecto fundamental de la búsqueda de texto completo es el uso de índices invertidos . Entonces, con un índice invertido, una consulta de una sola palabra se vuelve trivial para responder. Suponiendo que el índice está estructurado de esta manera:

some-word -> [doc385, doc211, doc39977, ...] (ordenados por rango, descendiendo)

Para responder a la consulta de esa palabra, la solución es encontrar la entrada correcta en el índice (que toma el tiempo O (log n)) y presentar un número dado de documentos (por ejemplo, los primeros 10) de la lista especificada en el índice.

¿Pero qué pasa con las consultas que devuelven documentos que coinciden, digamos, con dos palabras? La implementación más directa sería la siguiente:

configure A para que sea el conjunto de documentos que tienen la palabra 1 (buscando en el índice).
configure B para que sea el conjunto de documentos que tienen la palabra 2 (ídem).
calcular la intersección de A y B.

Ahora, el paso tres probablemente toma el tiempo O (n log n) para funcionar. Para A y B muy grandes que pueden hacer que la consulta sea lenta para responder. Pero los motores de búsqueda como Google siempre devuelven su respuesta en unos pocos milisegundos. Entonces esa no puede ser la respuesta completa.

Una optimización obvia es que, dado que un motor de búsqueda como Google no devuelve todos los documentos coincidentes, no tenemos que calcular toda la intersección. Podemos comenzar con el conjunto más pequeño (por ejemplo, B) y encontrar suficientes entradas que también pertenecen al otro conjunto (por ejemplo, A).

Pero, ¿no podemos seguir teniendo el siguiente peor caso? Si tenemos el conjunto A como el conjunto de documentos que coinciden con una palabra común, y el conjunto B como el conjunto de documentos que coincide con otra palabra común, puede haber casos en los que A ∩ B sea muy pequeño (es decir, la combinación es rara). Eso significa que el motor de búsqueda tiene que pasar linealmente por todos los elementos x miembros de B, verificando si también son elementos de A, para encontrar los pocos que coincidan con ambas condiciones.

Lineal no es rápido. Y puede tener más de dos palabras para buscar, de modo que simplemente emplear el paralelismo seguramente no es la solución completa. Entonces, ¿cómo se optimizan estos casos? ¿Los motores de búsqueda de texto a gran escala usan algún tipo de índices compuestos? ¿Filtros Bloom? ¿Algunas ideas?

Como dijo alguna palabra -> [doc385, doc211, doc39977, ...] (ordenado por rango, descendiendo) , creo que el motor de búsqueda puede no hacer esto, la lista de documentos debe ordenarse por documento de identidad , cada documento tiene un rango según la palabra.
Cuando llega una consulta, contiene varias palabras clave. Para cada palabra, puede encontrar una lista de documentos. Para todas las palabras clave, puede hacer operaciones de combinación y calcular la relevancia de doc para consultar. Finalmente, devuelve el documento de relevancia mejor clasificado al usuario.
Y el proceso de consulta se puede distribuir para obtener un mejor rendimiento.

La mayoría de los sistemas implementan TF-IDF de alguna manera u otra. TF-IDF es un producto de la frecuencia de los términos de las funciones y la frecuencia de los documentos inversos.

La función IDF relaciona la frecuencia del documento con la cantidad total de documentos en una colección. La intuición común para esta función dice que debería dar un mayor valor a los términos que aparecen en pocos documentos y de menor valor para los términos que aparecen en todos los documentos que los hacen irrelevantes.

Menciona a Google, pero Google optimiza la búsqueda con PageRank (enlaces entrantes / salientes), así como con la frecuencia y la proximidad de los términos. Google distribuye los datos y usa Map / Reduce para paralelizar operaciones: para calcular PageRank + TF-IDF.

Hay una gran explicación de la teoría detrás de esto en Recuperación de información: Implementación de motores de búsqueda capítulo 2. Otra idea para investigar más a fondo es también ver cómo Solr implementa esto.

Incluso sin clasificación, me pregunto cómo la intersección de dos conjuntos se computa tan rápido por google.

Obviamente, el peor de los escenarios para calcular la intersección de algunas palabras A, B, C es cuando sus índices son muy grandes y la intersección muy pequeña. Un caso típico sería una búsqueda de palabras muy comunes ("populares" en términos de DB) en diferentes idiomas.

Probemos "concreto" y 位置 ("sitio", "ubicación") en chino y 極端な ("extremo") en japonés.

La búsqueda de Google para 位置 devuelve "Aproximadamente 1,500,000,000 de resultados (0,28 segundos)" La búsqueda de Google para "concreto" arroja "Aproximadamente 2,020,000,000 resultados (0.46 segundos)" Búsqueda en Google de "極端About " Aproximadamente 7,590,000 resultados (0.25 segundos)

Es extremadamente improbable que los tres términos aparezcan alguna vez en el mismo documento, pero vamos a buscarlos en Google: la búsqueda en Google de "concreto 位置極端 returns" arroja " Alrededor de 174,000 resultados (0,13 segundos)"

Agregar una palabra en ruso "игра" (juego) Buscar en el juego: aproximadamente 212,000,000 de resultados (0,37 segundos)

Busque todos ellos: "игра concrete 位置極端 returns" devuelve unos 12.600 resultados (0.33 segundos)

Por supuesto, los resultados de búsqueda devueltos no tienen sentido y no contienen todos los términos de búsqueda.

Pero mirando el tiempo de consulta para los compuestos, me pregunto si hay alguna intersección calculada en los índices de palabras en absoluto. Incluso si todo está en RAM y muy fragmentado, el cálculo de la intersección de dos conjuntos con 1,500,000,000 y 2,020,000,000 entradas es O (n) y apenas se puede hacer en <0,5 seg, ya que los datos están en máquinas diferentes y tienen que comunicarse.

Debe haber algún cálculo de unión, pero al menos para palabras populares, seguramente esto no se hace en el índice de palabras completas. Agregando el hecho de que los resultados son borrosos, parece evidente que Google usa una optimización de tipo "devuelve algunos resultados de alto rango, y se detiene después de 0,5 segundos".

Cómo se implementa esto, no sé. ¿Algunas ideas?

Google no necesita encontrar realmente todos los resultados, solo los mejores. El índice se puede ordenar por grado primero y solo luego por id. Como la misma ID siempre tiene la misma calificación, esto no perjudica a los tiempos de intersección.

Entonces Google comienza la intersección hasta que encuentra 10 resultados, y luego hace una estimación estadística para decirle cuántos resultados más encontró.

Un peor caso es casi imposible. Si todas las palabras son "comunes", la intersección dará los primeros 10 resultados muy rápido. Si hay una palabra rara, entonces la intersección es rápida porque la complejidad es O (N largo M) donde N es el grupo más pequeño.

Debes recordar que Google mantiene sus índices en la memoria y usa la computación paralela. Por ejemplo, U puede dividir el problema en dos búsquedas, cada una de las cuales busca solo la mitad de la web, y luego marge el resultado y toma el mejor. Google tiene millones de cómputos