Comment lucene indexe-t-il les documents?

J'ai lu un document sur Lucene; aussi j'ai lu le document dans ce lien ( http://lucene.sourceforge.net/talks/pisa ).

Je ne comprends pas vraiment comment Lucene indexe les documents et je ne comprends pas quels algorithmes Lucene utilise pour l'indexation?

Sur le lien ci-dessus, il est dit que Lucene utilise cet algorithme pour l'indexation:

• algorithme incrémental:
  • maintenir une pile d'indices de segment
  • créer un index pour chaque document entrant
  • pousser de nouveaux index sur la pile
  • soit b = 10 le facteur de fusion; M = 8

for (size = 1; size < M; size *= b) {
    if (there are b indexes with size docs on top of the stack) {
        pop them off the stack;
        merge them into a single index;
        push the merged index onto the stack;
    } else {
        break;
    }
}

Comment cet algorithme permet-il une indexation optimisée?

Lucene utilise-t-il l'algorithme B-tree ou tout autre algorithme comme celui-ci pour l'indexation - ou a-t-il un algorithme particulier?

Il y a un assez bon article ici: https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

Edit 12/2014: mise à jour vers une version archivée en raison de la suppression de l'original, probablement la meilleure alternative la plus récente est http://lucene.apache.org/core/3_6_2/fileformats.html

Il existe une version encore plus récente sur http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description , mais elle semble contenir moins d'informations que l'ancien.

En un mot, lorsque lucene indexe un document, il le décompose en plusieurs termes. Il stocke ensuite les termes dans un fichier d'index où chaque terme est associé aux documents qui le contiennent. Vous pourriez y voir un peu comme une table de hachage.

Les termes sont générés à l'aide d'un analyseur qui dérive chaque mot à sa forme racine. L'algorithme de dérivation le plus populaire pour la langue anglaise est l'algorithme de dérivation de Porter: http://tartarus.org/~martin/PorterStemmer/

Lorsqu'une requête est émise, elle est traitée via le même analyseur que celui utilisé pour créer l'index, puis utilisé pour rechercher le ou les termes correspondants dans l'index. Cela fournit une liste de documents correspondant à la requête.

En un mot, Lucene construit un index inversé à l'aide de Skip-Lists sur le disque , puis charge un mappage pour les termes indexés en mémoire à l' aide d'un transducteur à état fini (FST). Notez cependant que Lucene ne charge pas (nécessairement) tous les termes indexés dans la RAM , comme décrit par Michael McCandless, l'auteur du système d'indexation de Lucene lui-même. Notez qu'en utilisant Skip-Lists, l'index peut être parcouru d'un hit à un autre, ce qui rend possible des requêtes telles que set et, en particulier, range (un peu comme les B-Trees). Et l'entrée de Wikipédia sur l'indexation des Skip-Lists explique également pourquoi l'implémentation de Skip-List de Lucene est appelée un multi-niveauSkip-List - essentiellement pour rendre les O(log n)recherches possibles (encore une fois, un peu comme les B-Trees).

Ainsi, une fois que l'index inversé (terme) - qui est basé sur une structure de données Skip-List - est construit à partir des documents, l'index est stocké sur le disque. Lucene charge ensuite (comme déjà dit: peut-être seulement certains) ces termes dans un transducteur à état fini , dans une implémentation FST vaguement inspirée de Morfologick .

Michael McCandless (également) fait un travail assez bon et laconique pour expliquer comment et pourquoi Lucene utilise un FST (acyclique minimal) pour indexer les termes que Lucene stocke en mémoire, essentiellement en tant que SortedMap<ByteSequence,SomeOutput>, et donne une idée de base du fonctionnement des FST (c.-à-d. comment le FST compacte les séquences d'octets [c'est-à-dire les termes indexés] pour faire en sorte que l'utilisation de la mémoire de ce mappage devienne sous-linéaire). Et il renvoie à l'article qui décrit l'algorithme FST particulier que Lucene utilise également.

Pour ceux qui sont curieux de savoir pourquoi Lucene utilise des Skip-Lists, alors que la plupart des bases de données utilisent (B +) - et / ou (B) -Trees, jetez un œil à la bonne réponse SO concernant cette question (Skip-Lists vs. B-Trees). Cette réponse donne une assez bonne explication approfondie - essentiellement, pas tellement de rendre les mises à jour simultanées de l'index "plus faciles" (parce que vous pouvez décider de ne pas rééquilibrer immédiatement un B-Tree, gagnant ainsi à peu près les mêmes performances simultanées qu'un Skip-List), mais plutôt les Skip-Lists vous évitent d'avoir à travailler sur l' opération d'équilibrage (retardée ou non) (en fin de compte) nécessaire aux B-Trees (En fait, comme le montre la réponse / références, il y a probablement très peu de différence de performances entre les B-Trees et les Skip-Lists [à plusieurs niveaux], si l'un ou l'autre est «bien fait»).

Il semble que votre question concerne davantage la fusion d'index que l'indexation elle-même.

Le processus d'indexation est assez simple si vous ignorez les détails de bas niveau. Lucene forme ce qu'on appelle un «index inversé» à partir de documents. Donc, si le document avec le texte «Être ou ne pas être» et id = 1 entre, l'index inversé ressemblerait à:

[to] → 1
[be] → 1
[or] → 1
[not] → 1

C'est fondamentalement ça - l'index du mot à la liste des documents contenant un mot donné. Chaque ligne de cet index (mot) est appelée liste d'affichage. Cet index est alors conservé sur le stockage à long terme.

En réalité, bien sûr, les choses sont plus compliquées:

• Lucene peut sauter certains mots en fonction de l'analyseur donné;
• les mots peuvent être prétraités en utilisant un algorithme de dérivation pour réduire la flexie de la langue;
• La liste de publication peut contenir non seulement les identifiants des documents, mais également le décalage du mot donné à l'intérieur du document (potentiellement plusieurs instances) et d'autres informations supplémentaires.

Il y a beaucoup plus de complications qui ne sont pas si importantes pour la compréhension de base.

Il est important de comprendre cependant que l'index Lucene est uniquement ajouté . À un moment donné, l'application décide de valider (publier) toutes les modifications de l'index. Lucene termine toutes les opérations de service avec l'index et le ferme, il est donc disponible pour la recherche. Après l'index de validation, fondamentalement immuable. Cet index (ou partie d'index) est appelé segment . Lorsque Lucene exécute la recherche d'une requête, il recherche dans tous les segments disponibles.

Alors la question se pose - comment pouvons-nous changer un document déjà indexé ?

Les nouveaux documents ou les nouvelles versions de documents déjà indexés sont indexés dans de nouveaux segments et les anciennes versions invalides dans les segments précédents à l'aide de ce que l'on appelle la liste de mise à mort . La liste d'élimination est la seule partie de l'index validé qui peut changer. Comme vous pouvez le deviner, l'efficacité des index diminue avec le temps, car les anciens index peuvent contenir la plupart des documents supprimés.

C'est là que la fusion entre en jeu. Fusion - est le processus de combinaison de plusieurs index pour rendre l'index plus efficace dans l'ensemble. Ce qui se passe essentiellement lors de la fusion, ce sont les documents en direct copiés dans le nouveau segment et les anciens segments entièrement supprimés.

En utilisant ce processus simple, Lucene est capable de maintenir l'index en bon état en termes de performances de recherche.

J'espère que ça aidera.

C'est un index inversé , mais cela ne précise pas quelle structure il utilise. Le format d'index en lucene contient des informations complètes.
Commencez par «Résumé des extensions de fichier».

Vous remarquerez d'abord qu'il parle de différents index différents. Pour autant que je puisse remarquer, aucun de ceux-ci n'utilise à proprement parler un arbre B , mais il y a des similitudes - les structures ci-dessus ressemblent à des arbres.