Comment lucene indexe-t-il les documents?

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 il semble y avoir moins d’informations que le plus ancien.

En bref, 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 penser à un peu comme une hashtable.

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

Lorsqu’une requête est émise, elle est traitée via le même parsingur que celui utilisé pour générer l’index, puis utilisée pour rechercher les termes correspondants dans l’index. Cela fournit une liste de documents correspondant à la requête.

Il semble que votre question porte davantage sur la fusion d’index que sur l’indexation proprement dite.

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

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

Ceci est fondamentalement – l’index du mot à la liste des documents contenant un mot donné. Chaque ligne de cet index (word) s’appelle la liste de publication. Cet index est conservé sur le stockage à long terme.

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

• Lucene peut ignorer certains mots basés sur l’parsingur donné;
• les mots peuvent être prétraités en utilisant l’algorithme de stemming pour réduire la flexibilité de la langue;
• La liste de diffusion peut contenir non seulement des identifiants des documents, mais aussi des décalages 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 que l’index Lucene est ajouté uniquement . À un certain moment, l’application décide de valider (publier) tous les changements dans l’index. Lucene termine toutes les opérations de service avec index et le ferme, il est donc disponible pour la recherche. Index après validation essentiellement immuable. Cet index (ou partie d’index) est appelé segment . Lorsque Lucene exécute une recherche, il recherche tous les segments disponibles.

Donc, 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 les nouveaux segments et les anciennes versions sont invalidées dans les segments précédents à l’aide de ce que l’on appelle la liste morte . Kill list est la seule partie de l’index engagé qui peut changer. Comme vous pouvez le deviner, l’efficacité des index diminue avec le temps, car les anciens index peuvent contenir principalement des documents supprimés.

C’est là qu’intervient la fusion. La fusion est le processus consistant à combiner plusieurs index pour rendre l’index plus efficace. Ce qui se passe essentiellement lors de la fusion, ce sont les documents en direct copiés sur le nouveau segment et les anciens segments entièrement supprimés.

Grâce à ce processus simple, Lucene est capable de maintenir l’index en bonne forme en termes de performances de recherche.

J’espère que ça va aider.

En résumé, Lucene construit un index inversé en utilisant Skip-Lists sur le disque , puis charge un mappage pour les termes indexés dans la mémoire en utilisant un transducteur à états finis (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 à l’autre, ce qui rend des choses comme set et, en particulier, des requêtes de plage possibles (un peu comme les B-Trees). Et l’entrée de Wikipedia sur l’indexation des Skip-Lists explique également pourquoi l’implémentation de Skip-List de Lucene s’appelle une Skip-List multi-niveaux – essentiellement, pour rendre possible les recherches O(log n) (encore une fois, comme B-Trees).

Ainsi, une fois que l’index (terme) inversé – basé sur une structure de données Skip-List – est créé à partir des documents, l’index est stocké sur le disque. Lucene charge ensuite (comme on l’a déjà dit: peut-être que quelques-uns seulement) ces termes dans un transducteur à états finis , dans une implémentation FST inspirée par Morfologick .

Michael McCandless (aussi) explique très bien comment et pourquoi Lucene utilise un FST (acyclique minimal) pour indexer les termes stockés en mémoire par Lucene, essentiellement comme SortedMap et donne une idée de base pour comment les FST fonctionnent (c.-à-d. comment le FST compresse les séquences d’octets [c.-à-d. les termes indexés] pour que l’utilisation de cette mappe en mémoire devienne sub-linéaire). Et il souligne le papier qui décrit l’algorithme FST particulier que Lucene utilise également.

Pour ceux qui sont curieux de savoir pourquoi Lucene utilise Skip-Lists, alors que la plupart des bases de données utilisent des arborescences (B +) – et / ou (B), jetez un œil à la bonne réponse SO concernant cette question (Skip-Lists vs. B-Trees). Cette réponse donne une explication assez bonne – en gros, pas tellement que les mises à jour simultanées de l’index “se prêtent mieux” (car vous pouvez décider de ne pas rééquilibrer immédiatement un B-Tree, obtenant ainsi à peu près les mêmes performances qu’un Skip-List), mais plutôt, Skip-Lists vous évite de travailler sur l’ opération d’équilibrage (tardive ou non) (en fin de compte) requirejse par B-Trees (en fait, comme la réponse affiche / référence, il y a probablement très peu différence de performance entre les B-Trees et [multi-level] Skip-Lists, si l’un ou l’autre est «fait correctement».)

C’est un index inversé , mais cela ne spécifie pas la structure qu’il utilise. Le format d’index dans lucene a des informations complètes.
Commencez avec ‘Résumé des extensions de fichier’.

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