Utilisation des index pour les requêtes multi-mots dans la recherche en texte intégral (par exemple, recherche Web)

Question

Je comprends qu'un aspect fondamental de la recherche en texte intégral est l'utilisation de index inversés. Ainsi, avec un index inversé, une requête en un mot devient triviale à répondre. En supposant que l'indice est structuré comme ceci:

quelque mot -> [doc385, doc211, doc39977, ...] (trié par rang, descendant)

Pour répondre à la requête pour ce mot, la solution est juste de trouver la bonne entrée dans l'index (qui prend le temps (log n) du temps) et de présenter un nombre donné de documents (par exemple, les 10 premiers) de la liste spécifiée dans l'index.

Mais qu'en est-il des requêtes qui retournent des documents qui correspondent, disons, deux mots? La mise en œuvre la plus simple serait la suivante:

1. Définissez A pour être l'ensemble des documents qui ont le mot 1 (en recherchant l'index).
2. Définissez B pour être l'ensemble des documents qui ont le mot 2 (idem).
3. Calculez l'intersection de A et B.

Maintenant, l'étape trois prend probablement le temps de l'O (n log n) pour fonctionner. Pour les très grands A et BS qui pourraient rendre la requête lente à répondre. Mais les moteurs de recherche comme Google renvoient toujours leur réponse en quelques millisecondes. Donc, cela ne peut pas être la réponse complète.

Une optimisation évidente est que, puisque un moteur de recherche comme Google ne renvoie pas tous les documents correspondants de toute façon, nous n'avons pas à calculer l'intersection entière. Nous pouvons commencer par le plus petit ensemble (par exemple b) et trouver suffisamment d'entrées qui appartiennent également à l'autre ensemble (par exemple A).

Mais ne pouvons-nous pas encore avoir le pire cas suivant? Si nous avons défini un ensemble de documents correspondant à un mot commun, et que le jeu est l'ensemble des documents correspondant à un autre mot commun, il pourrait encore y avoir des cas où un ∩ b est très petit (c'est-à-dire que la combinaison est rare). Cela signifie que le moteur de recherche doit passer linéairement par un membre de tous les éléments X de B, vérifiant s'il s'agit également d'éléments de A, pour trouver les quelques-uns qui correspondent aux deux conditions.

Linéaire n'est pas rapide. Et vous pouvez avoir beaucoup plus de deux mots à rechercher, donc simplement utiliser le parallélisme n'est sûrement pas toute la solution. Alors, comment ces cas sont-ils optimisés? Les moteurs de recherche en texte complet à grande échelle utilisent-ils une sorte d'index de composés? Filtres de floraison? Des idées?

Answer 1

Comme tu dis quelque mot -> [doc385, doc211, doc39977, ...] (trié par rang, descendant), Je pense que le moteur de recherche peut ne pas le faire, la liste des documents devrait être trié par doc id, chaque doc a un rang selon le mot.
Lorsqu'une requête arrive, elle contient plusieurs mots clés. Pour chaque mot, vous pouvez trouver une liste de doc. Pour tous les mots clés, vous pouvez Faire fusionner les opérations, et calculer la pertinence de Doc à la question. Renvoyez enfin le document de pertinence le mieux classé à l'utilisateur.
Et le processus de requête peut être distribué pour obtenir de meilleures performances.

Answer 2

La plupart des systèmes mettent en œuvre en quelque sorte Tf-idf d'une manière ou d'une autre. TF-IDF est un produit de la fréquence des termes des fonctions et de la fréquence du document inverse.

La fonction IDF relie la fréquence des documents au nombre total de documents dans une collection. L'intuition commune pour cette fonction indique qu'elle devrait donner une valeur plus élevée pour les termes qui apparaissent dans quelques documents et une valeur inférieure pour les termes qui apparaissent dans tous les documents les rendant hors de propos.

Vous mentionnez Google, mais Google optimise la recherche avec PageRank (liens dans / out) ainsi que la fréquence des termes et la proximité. Google distribue les données et utilise la carte / réduction des opérations paralléliques - pour calculer PageRank + TF-IDF.

Il y a une grande explication de la théorie derrière cela Renseignante des informations: implémentation de moteurs de recherche Chapitre 2. Une autre idée pour enquêter davantage est également de voir comment Solr implémente ceci.

Answer 3

Même sans classement, je me demande comment l'intersection de deux ensembles est calculée si rapidement par Google.

De toute évidence, le pire des cas pour calculer l'intersection pour certains mots a, b, c est lorsque leurs index sont très grands et que l'intersection est très petite. Un cas typique serait une recherche de mots très courants («populaires» en termes de base de données) dans différentes langues.

Essayons "Concrete" et 位置 ("Site", "Location") en chinois et 極端 な な な な な な な な な な な な ("Extreme") en japonais.

Recherche Google pour 位置 Renvoie "Environ 1 500 000 000 de résultats (0,28 seconde)"Google Recherche pour "Concrete" Renvoie "Environ 2 020 000 000 de résultats (0,46 seconde)"Google recherche "極端 な" Environ 7 590 000 résultats (0,25 seconde)

Il est extrêmement improbable que les trois termes apparaissent jamais dans le même document, mais Go Google: Google recherche "Concrete 位置 極端 な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な な なEnviron 174 000 résultats (0,13 seconde) "

Ajout d'un mot russe "игра" (jeu) Recherche игра: environ 212 000 000 résultats (0,37 seconde)

Recherchez tous: "игра béton 位置 極端 な な な な な な な な" Environ 12 600 résultats (0,33 seconde)

Bien sûr, les résultats de recherche retournés sont absurdes et ils ne contiennent pas tous les termes de recherche.

Mais en regardant le temps de requête pour les composés, je me demande s'il y a une intersection calculée sur les index de mots. Même si tout est en RAM et fortement fragné, le calcul de l'intersection de deux ensembles avec 1 500 000 000 et 2 020 000 000 entrées est O (n) et peut difficilement être fait dans <0,5 s, car les données sont sur différentes machines et elles doivent communiquer.

Il doit y avoir un calcul de jointure, mais au moins pour les mots populaires, cela ne se fait certainement pas sur l'indice des mots entier. Ajoutant le fait que les résultats sont flous, il semble évident que Google utilise une certaine optimisation de Kind "Giver quelques résultats de haut rang et s'arrêtez après 0,5 sec".

Comment cela est mis en œuvre, je ne sais pas. Des idées?

Answer 4

Google n'a pas besoin de trouver tous les résultats, seulement les meilleurs. L'indice peut être trié par grade d'abord et seulement par ID. Étant donné que le même ID a toujours la même note, cela ne nuit pas au temps d'intersection des ensembles.

Google démarre donc l'intersection jusqu'à ce qu'il trouve 10 résultats, puis fait une estimation statistique pour vous dire combien de résultats il a trouvés.

Un pire cas est presque impossible. Si tous les mots sont "communs", l'intersection donnera les 10 premiers résultats très rapidement. S'il y a un mot rare, alors l'intersection est rapide car la complexité est O (n long m) où n est le plus petit groupe.

Vous devez vous rappeler que Google conserve ses index en mémoire et utilise l'informatique parallèle. Par exemple, vous pouvez diviser le problème en deux recherches à chaque recherche uniquement la moitié du Web, puis sur le résultat et prendre le meilleur. Google a des millions de calculs