Comment lucene indexe-t-il les documents ?

Question

J'ai lu quelques documents sur Lucene ; j'ai également 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 segments
  • créer un index pour chaque document entrant
  • pousser les nouveaux index sur la pile
  • b=10 est 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 un autre algorithme de ce type pour l'indexation ? - ou possède-t-il un algorithme particulier ?

Answer 1

En un mot, Lucene construit un index inversé en utilisant Skip-Lists sur le disque puis charge un mapping pour les termes indexés en mémoire en utilisant un Transducteur à états finis (FST). Notez toutefois que Lucene ne charge pas (nécessairement) tous les termes indexés en RAM tel que décrit par Michael McCandless, l'auteur du système d'indexation de Lucene lui-même. Notez qu'en utilisant les listes de saut, l'index peut être parcouru d'un hit à l'autre, ce qui permet de faire des choses comme set et, en particulier, requêtes sur la gamme possible (un peu comme les B-Trees). Et le Entrée de Wikipedia sur l'indexation des listes de saut explique également pourquoi l'implémentation du Skip-List de Lucene est appelée une multi-niveaux Skip-List - essentiellement, pour faire O(log n) de consultations possibles (à nouveau, un peu comme les B-Trees).

Ainsi, une fois que l'indice 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 : éventuellement, seulement une partie) de ces termes dans un fichier Transducteur à états finis dans une mise en œuvre de la TSF librement inspiré par Morfologick .

Michael McCandless (aussi) fait un travail assez bon et laconique de expliquer comment et pourquoi Lucene utilise une TSF (acyclique minimale) pour indexer les termes que Lucene stocke en mémoire, essentiellement comme une SortedMap<ByteSequence,SomeOutput> Il donne une idée de base du fonctionnement des TSF (c'est-à-dire comment la TSF compacte les séquences d'octets [c'est-à-dire les termes indexés] pour que l'utilisation de la mémoire de ce mappage croisse de façon sous-linéaire). Et il indique l'article qui décrit l'algorithme de TSF particulier Lucene l'utilise aussi.

Pour ceux qui sont curieux de savoir pourquoi Lucene utilise des listes de saut, alors que la plupart des bases de données utilisent des (B+)- et/ou (B)-Trees, jetez un coup d'oeil à le site droite Réponse SO concernant cette question (Skip-Lists vs. B-Trees). Cette réponse donne une explication assez bonne et approfondie - essentiellement, pas 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, ce qui vous permet d'obtenir à peu près les mêmes performances simultanées qu'avec une Skip-List), mais plutôt, Les Skip-Lists vous évitent d'avoir à travailler sur la (retardé ou non) opération d'équilibrage (en fin de compte) nécessaire aux B-Trees (en fait, comme la réponse le montre/réfère, il y a probablement très peu de différence de performance entre les B-Trees et les Skip-Lists [multi-niveaux], si les deux sont "bien faits").

Answer 2

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 : Mis à jour vers une version archivée en raison de la suppression de l'original, probablement la meilleure alternative plus récente est http://lucene.apache.org/core/3_6_2/fileformats.html

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

En bref, lorsque Lucene indexe un document, il le décompose en un certain nombre de termes. Il stocke ensuite les termes dans un fichier d'index où chaque terme est associé aux documents qui le contiennent. On pourrait penser que c'est un peu comme une table de hachage.

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

Lorsqu'une requête est émise, elle est traitée par le même analyseur que celui qui a été utilisé pour construire l'index, puis elle est utilisée pour rechercher le ou les termes correspondants dans l'index. Cela permet d'obtenir une liste de documents qui correspondent à la requête.

Answer 3

Il semble que votre question porte davantage sur la fusion des index que sur l'indexation elle-même.

Le processus d'indexation est assez simple si l'on ignore les détails de bas niveau. Lucene forme ce que l'on appelle un "index inversé" à partir des documents. Ainsi, si un document contenant le texte "To be or not to be" et id=1 arrive, l'index inversé ressemblera à ceci :

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

Il s'agit essentiellement de l'indice du mot à la liste de documents contenant un mot donné. Chaque ligne de cet index (mot) est appelée liste d'affichage. Cet index est ensuite persisté sur un stockage à long terme.

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

• Lucene peut sauter certains mots en fonction de l'analyseur particulier donné ;
• Les mots peuvent être prétraités à l'aide d'un algorithme de stemming afin de réduire la flexion de la langue ;
• La liste d'affichage peut contenir non seulement les identifiants des documents, mais aussi le décalage du mot donné dans le document (potentiellement plusieurs instances) et d'autres informations supplémentaires.

Il existe de nombreuses autres complications qui ne sont pas aussi importantes pour la compréhension de base.

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

La question se pose donc : comment pouvons-nous modifier un document déjà indexé ?

Les nouveaux documents ou les nouvelles versions de documents déjà indexés sont indexés dans les nouveaux segments et les anciennes versions sont invalidées dans les segments précédents à l'aide de ce que l'on appelle le "système d'indexation". liste de mise à mort . La Kill list est la seule partie de l'index engagé qui peut changer. Comme vous pouvez le deviner, l'efficacité de l'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. La fusion est le processus qui consiste à combiner plusieurs index pour obtenir un index plus efficace dans son ensemble. Pendant la fusion, les documents vivants sont copiés dans le nouveau segment et les anciens segments sont entièrement supprimés.

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

J'espère que ça vous aidera.

Answer 4

Il est indice inversé mais cela ne précise pas quelle structure il utilise. Format de l'index dans lucene a des informations complètes.
Commencez par le "Résumé des extensions de fichiers".

Vous remarquerez d'abord qu'il parle de différents indices. D'après ce que j'ai pu constater, aucun d'entre eux n'utilise à proprement parler un indice Arbre B mais il y a des similitudes - les structures ci-dessus ressemblent à des arbres.