Comment fonctionne Lucene

J’aimerais savoir comment lucene search fonctionne si vite. Je ne trouve aucun document utile sur le Web. Si vous avez quelque chose (à court de code source lucene) à lire, faites le moi savoir.

Une requête de recherche de texte utilisant la recherche de texte mysql5 avec index prend environ 18 minutes dans mon cas. Une recherche lucene pour la même requête prend moins d’une seconde.

Lucene est un index de texte intégral inversé. Cela signifie qu’il prend tous les documents, les divise en mots, puis crée un index pour chaque mot . Étant donné que l’index est une correspondance de chaîne exacte, non ordonnée, il peut être extrêmement rapide. En théorie, un index SQL non ordonné sur un champ varchar pourrait être tout aussi rapide et, en fait, je pense que vous trouverez que les grandes bases de données peuvent effectuer une requête simple d’égalité de chaînes très rapidement dans ce cas.

Lucene n’a pas à optimiser pour le traitement des transactions. Lorsque vous ajoutez un document, il n’est pas nécessaire que les requêtes le voient instantanément . Et il n’est pas nécessaire d’optimiser les mises à jour des documents existants.

Cependant, en fin de compte, si vous voulez vraiment savoir, vous devez lire la source. Après tout, les deux choses que vous référencez sont open source.

Lucene crée un gros index. L’index contient l’identifiant du mot, le nombre de documents où le mot est présent et la position du mot dans ces documents. Donc, lorsque vous donnez une requête de mot unique, elle recherche uniquement l’index (complexité temporelle O (1)). Ensuite, le résultat est classé en utilisant différents algorithmes. Pour les requêtes multi-mots, il suffit de prendre l’intersection de l’ensemble des fichiers où les mots sont présents. Ainsi, Lucene est très très rapide.

Pour plus d’informations, lisez cet article par les développeurs de Google: http://infolab.stanford.edu/~backrub/google.html

En un mot: l’indexation.

Lucene crée un index de votre document qui lui permet d’effectuer des recherches beaucoup plus rapidement.

C’est la même différence entre une structure de données de liste O (N) et une structure de données de table de hachage O (1). La liste doit parcourir toute la collection pour trouver ce que vous voulez. La table de hachage a un index qui lui permet de déterminer exactement où se trouve l’élément souhaité et de le récupérer simplement.

Mettre à jour:

Je ne suis pas certain de ce que vous entendez par “les recherches d’index Lucene sont beaucoup plus rapides que les recherches d’index mysql.”

Je suppose que vous utilisez MySQL “WHERE document LIKE ‘% phrase%'” pour rechercher un document. Si cela est vrai, alors MySQL doit faire une parsing de table sur chaque ligne, qui sera O (N).

Lucene peut parsingr le document en jetons, les regrouper en n-grammes dans votre direction et calculer des index pour chacun d’entre eux. C’est O (1) pour trouver un mot dans un document Lucene indexé.

Lucene fonctionne avec la fréquence des termes et la fréquence des documents inverses . Il crée un index mappant chaque mot avec le document et son compte de fréquence qui n’est rien d’autre qu’un index inverse sur le document.

Exemple :

Fichier 1: La mémoire vive est la mémoire principale.

Fichier 2: Les disques durs sont des mémoires secondaires.

Lucene crée un index inverse quelque chose comme

Fichier 1:

Terme: Aléatoire

Fréquence: 1

Position: 0

Terme: mémoire

Fréquence: 2

Position: 3

Position: 6

Il est donc capable de rechercher et de récupérer rapidement le contenu recherché. Lorsqu’il y a trop de correspondances pour la requête de recherche, le résultat est généré en fonction du poids. Considérons la requête de recherche “Mémoire principale” qui recherche les 4 mots individuellement et le résultat serait comme,

Principale

Dossier 1: Fréquence – 1

Mémoire

Fichier 1: Fréquence – 2

Fichier 2: Fréquence – 1

Le résultat serait File1 suivi de File2 . Pour cesser de se laisser emporter par les poids des mots les plus courants tels que ‘et’, ‘ou’, le ‘considère la fréquence inverse du document (c.-à-d.