L'algorithme de Lucene
j'ai lu le papier par Doug Cutting; " optimisation de L'espace pour le classement total".
Puisqu'il a été écrit il y a longtemps, je me demande quels algorithmes lucene utilise (concernant la liste de messages transversal et le calcul de score, le classement).
en particulier, l'algorithme de classement total décrit ici implique de parcourir toute la liste des messages pour chaque terme de requête, donc en cas de termes de requête très communs comme "Yellow dog", l'un ou l'autre des 2 Termes peut avoir un très très longue liste de messages en cas de recherche sur le web. Sont-ils tous réellement traversés dans le courant Lucene/Solr? Ou y a-t-il une heuristique pour tronquer la liste employée?
dans le cas où seuls les résultats du top k sont retournés, je peux comprendre que la distribution de la liste de diffusion sur plusieurs machines, puis la combinaison du top-k de chacune fonctionnerait, mais si nous sommes tenus de retourner "la 100ème page de résultat", c.-à-d. les résultats classés de 990--1000ème, alors chaque partition serait encore trouver le top 1000, de sorte le partitionnement n'aiderait pas beaucoup.
dans l'ensemble, Existe-t-il une documentation détaillée à jour sur les algorithmes internes utilisés par Lucene?
1 réponses
Je ne suis pas au courant d'une telle documentation, mais comme Lucene est open-source, je vous encourage à lire le code source. En particulier, la version trunk actuelle inclut indexation flexible, ce qui signifie que la traversée de la liste de stockage et de publication a été découplée du reste du code, ce qui permet d'écrire des codecs personnalisés.
vos suppositions sont correctes en ce qui concerne l'affichage de liste transversale, par défaut (cela dépend de votre buteur mise en œuvre) Lucene parcourt toute la liste de diffusion pour chaque terme présent dans la requête et place les documents correspondants dans un tas de taille k pour calculer les premiers docs (voir TopDocsCollector). Ainsi le retour des résultats de 990 à 1000 rend Lucene instantiate un tas de taille 1000. Et si vous partitionnez votre index par document( une autre approche pourrait être de diviser par terme), chaque fragment devra envoyer les 1000 meilleurs résultats au serveur qui est responsable de la fusion des résultats (Voir Solr QueryComponent par exemple, ce qui se traduit par une requête à partir de N pour P>N à plusieurs fragment demandes de 0 à P sreq.params.set(CommonParams.START, "0");). C'est pourquoi Solr peut-être plus lent en mode distribué qu'en mode autonome en cas d'extrême pagination.
Je ne sais pas comment Google parvient à marquer des résultats efficacement, mais Twitter a publié un feuille de papier sur leur moteur de recherche Earlybird où ils expliquent comment ils ont patché Lucene pour faire efficace l'ordre chronologique inverse traversée des listes de diffusion, ce qui leur permet de retourner les tweets les plus récents correspondant à une requête sans traverser toute la liste de diffusion pour chaque terme.
mise à Jour: J'ai trouvé ce présentation à partir de Googleurs Jeff Dean, ce qui explique comment Google a construit son système de recherche d'informations à grande échelle. En particulier, il parle de stratégies de partage et d'encodage de liste de publication.