Wie dokumentiert Lucene Dokumente?

95

Ich habe ein Dokument über Lucene gelesen. Ich habe auch das Dokument in diesem Link gelesen ( http://lucene.sourceforge.net/talks/pisa ).

Ich verstehe nicht wirklich, wie Lucene Dokumente indiziert, und verstehe nicht, welche Algorithmen Lucene für die Indizierung verwendet.

Auf dem obigen Link steht, dass Lucene diesen Algorithmus zur Indizierung verwendet:

  • inkrementeller Algorithmus:
    • einen Stapel von Segmentindizes pflegen
    • Erstellen Sie einen Index für jedes eingehende Dokument
    • Schieben Sie neue Indizes auf den Stapel
    • sei b = 10 der Zusammenführungsfaktor; 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;
    }
}

Wie bietet dieser Algorithmus eine optimierte Indizierung?

Verwendet Lucene einen B-Tree-Algorithmus oder einen ähnlichen Algorithmus für die Indizierung - oder hat er einen bestimmten Algorithmus?

Mehdi Amrollahi
quelle
Die meisten Antworten hier sind richtig, dass Lucene zuerst einen invertierten Index erstellt, aber das erklärt nicht den entscheidenden Punkt, wie dieser Begriff Index anschließend durchsucht wird (und ich glaube, was das OP tatsächlich verlangt hat). Nachfolgend finden Sie eine neue Antwort auf diese ziemlich alte Frage, die hoffentlich einen besseren Einblick bietet.
Fnl
1
Ich habe meine Antwort noch einmal aktualisiert, da die aktuellen Antworten (einschließlich meiner!) Nicht wirklich zufriedenstellend sind, um die beiden Hauptfragen des OP zu beantworten (wie bietet Lucene eine optimierte Indizierung und nach welchem ​​bestimmten Algorithmus - eine Überspringliste, kein B-Baum, Übrigens). Hoffe, meine letzten Updates beantworten jetzt die eigentliche Frage richtig!
fnl

Antworten:

54

Hier gibt es einen ziemlich guten Artikel: https://web.archive.org/web/20130904073403/http://www.ibm.com/developerworks/library/wa-lucene/

Bearbeiten 12/2014: Aufgrund des Löschens des Originals auf eine archivierte Version aktualisiert. Die wahrscheinlich aktuellste Alternative ist http://lucene.apache.org/core/3_6_2/fileformats.html

Es gibt eine noch neuere Version unter http://lucene.apache.org/core/4_10_2/core/org/apache/lucene/codecs/lucene410/package-summary.html#package_description , aber es scheint weniger Informationen zu enthalten als der ältere.

Kurz gesagt, wenn Lucene ein Dokument indiziert, zerlegt es es in eine Reihe von Begriffen. Anschließend werden die Begriffe in einer Indexdatei gespeichert, in der jeder Begriff den Dokumenten zugeordnet ist, die ihn enthalten. Man könnte es sich ein bisschen wie eine Hashtabelle vorstellen.

Begriffe werden mit einem Analysator generiert, der jedes Wort in seine Grundform bringt. Der beliebteste Stemming-Algorithmus für die englische Sprache ist der Porter-Stemming-Algorithmus: http://tartarus.org/~martin/PorterStemmer/

Wenn eine Abfrage ausgegeben wird, wird sie über denselben Analysator verarbeitet, der zum Erstellen des Index verwendet wurde, und dann zum Nachschlagen der übereinstimmenden Begriffe im Index. Dadurch wird eine Liste der Dokumente bereitgestellt, die der Abfrage entsprechen.

Darren
quelle
Vielen Dank für Ihre Antwort und Links. Aber ich habe gehört, dass das Lucene-Projekt einen speziellen Stemmer namens "Schneeball" hat? Hast du etwas davon gehört?
Mehdi Amrollahi
Dies ist eine andere Frage: Siehe lucidimagination.com/search/… Abgesehen davon empfehle ich Ihnen, angesichts Ihres Fragenmusters das Buch 'Lucene in Action' zu lesen: manning.com/hatcher2 (Die erste Ausgabe ist etwas veraltet, kann es aber sein gefunden in einer toten Baumversion. Die zweite Ausgabe kann als E-Book gekauft werden).
Yuval F
5
Mögen Sie Ihre Antwort ändern, der erste Link, der ein IBM-Link ist, wurde nicht gefunden :)
Adelin
Wie geben Felder das gesamte Bild ein? Wenn sich eine Abfrage in einem bestimmten Feld befindet, woher und an welchem ​​Punkt weiß Lucene, dass sich der Begriff, der auf das Dokument verweist, nicht im Dokument befindet, sondern in einem angeforderten Feld?
Levon Tamrazov
44

Kurz gesagt, Lucene erstellt mithilfe von Überspringlisten auf der Festplatte einen invertierten Index und lädt dann mithilfe eines Finite State Transducer (FST) eine Zuordnung für die indizierten Begriffe in den Speicher . Beachten Sie jedoch, dass Lucene nicht (notwendigerweise) alle indizierten Begriffe in den Arbeitsspeicher lädt , wie von Michael McCandless, dem Autor des Indexierungssystems von Lucene selbst, beschrieben. Beachten Sie, dass durch die Verwendung von Überspringlisten der Index von einem Treffer zum anderen durchlaufen werden kann, wodurch beispielsweise Abfragen zum Festlegen und insbesondere zum Bereich möglich werden (ähnlich wie bei B-Bäumen). Der Wikipedia-Eintrag zur Indizierung von Überspringlisten erklärt auch, warum die Implementierung der Überspringliste von Lucene als mehrstufig bezeichnet wirdSkip-List - im Wesentlichen, um O(log n)Nachschlagen zu ermöglichen (ähnlich wie bei B-Trees).

Sobald der invertierte (Term-) Index - der auf einer Skip-List-Datenstruktur basiert - aus den Dokumenten erstellt wurde, wird der Index auf der Festplatte gespeichert. Lucene lädt dann (wie bereits gesagt: möglicherweise nur einige) dieser Begriffe in einen Finite-State-Transducer in einer FST-Implementierung, die lose von Morfologick inspiriert ist .

Michael McCandless erklärt (auch) ziemlich gut und knapp , wie und warum Lucene eine (minimale azyklische) FST verwendet, um die Begriffe zu indizieren, die Lucene im Speicher speichert, im Wesentlichen als SortedMap<ByteSequence,SomeOutput>, und gibt eine grundlegende Vorstellung davon, wie FSTs funktionieren (dh wie die FST die Byte-Sequenzen (dh die indizierten Terme) komprimiert, damit der Speicher, der diese Zuordnung verwendet, sublinear wird). Und er verweist auf das Papier, das auch den speziellen FST-Algorithmus beschreibt, den Lucene verwendet.

Für diejenigen, die neugierig sind, warum Lucene Überspringlisten verwendet, während die meisten Datenbanken (B +) - und / oder (B) -Bäume verwenden, werfen Sie einen Blick auf die richtige SO-Antwort zu dieser Frage (Überspringlisten vs. B-Bäume). Diese Antwort liefert eine ziemlich gute, tiefgreifende Erklärung - im Grunde genommen machen gleichzeitige Aktualisierungen des Index nicht so sehr "zugänglicher" (weil Sie sich entscheiden können, einen B-Baum nicht sofort neu auszugleichen, wodurch Sie ungefähr die gleiche gleichzeitige Leistung wie ein erhalten Skip-List), sondern Skip-Lists ersparen Ihnen die Arbeit am (verzögerten oder nicht verzögerten) Ausgleichsvorgang (letztendlich) von B-Trees benötigt (Wie die Antwort zeigt / verweist, gibt es wahrscheinlich nur einen sehr geringen Leistungsunterschied zwischen B-Trees und [mehrstufigen] Skip-Lists, wenn beide "richtig gemacht" werden.)

fnl
quelle
1
Afaik sie verwenden Skip List anstelle von B-Tree, um die Anzahl der Festplattensuchen zu reduzieren, da sich der Teil der Skip List im Speicher befindet und nur sehr wenige Festplatten-E / A erforderlich sind, wenn der Index durchlaufen wird
Anton
24

Ihre Frage scheint mehr über das Zusammenführen von Indizes als über das Indizieren selbst zu sein.

Der Indizierungsprozess ist recht einfach, wenn Sie Details auf niedriger Ebene ignorieren. Lucene bildet aus Dokumenten einen sogenannten "invertierten Index". Wenn also ein Dokument mit dem Text "Sein oder Nichtsein" und id = 1 eingeht, sieht der invertierte Index folgendermaßen aus:

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

Dies ist im Grunde genommen der Index vom Wort zur Liste der Dokumente, die ein bestimmtes Wort enthalten. Jede Zeile dieses Index (Wortes) wird als Buchungsliste bezeichnet. Dieser Index bleibt dann bei Langzeitspeicherung erhalten.

In Wirklichkeit sind die Dinge natürlich komplizierter:

  • Lucene kann einige Wörter überspringen, die auf dem jeweiligen Analysator basieren.
  • Wörter können unter Verwendung eines Stemming-Algorithmus vorverarbeitet werden, um die Flexia der Sprache zu verringern;
  • Die Buchungsliste kann nicht nur Kennungen der Dokumente enthalten, sondern auch den Versatz des angegebenen Wortes im Dokument (möglicherweise mehrere Instanzen) und einige andere zusätzliche Informationen.

Es gibt viele weitere Komplikationen, die für das Grundverständnis nicht so wichtig sind.

Es ist jedoch wichtig zu verstehen, dass der Lucene-Index nur angehängt wird . Zu einem bestimmten Zeitpunkt beschließt die Anwendung, alle Änderungen im Index festzuschreiben (zu veröffentlichen). Lucene beendet alle Servicevorgänge mit dem Index und schließt ihn, damit er für die Suche verfügbar ist. After-Commit-Index grundsätzlich unveränderlich. Dieser Index (oder Indexteil) wird als Segment bezeichnet . Wenn Lucene die Suche nach einer Abfrage ausführt, wird in allen verfügbaren Segmenten gesucht.

Es stellt sich also die Frage, wie wir bereits indizierte Dokumente ändern können .

Neue Dokumente oder neue Versionen bereits indizierter Dokumente werden in neuen Segmenten indiziert und alte Versionen in früheren Segmenten mithilfe der sogenannten Kill-Liste ungültig gemacht . Die Kill-Liste ist der einzige Teil des festgeschriebenen Index, der sich ändern kann. Wie Sie vielleicht erraten haben, nimmt die Indexeffizienz mit der Zeit ab, da alte Indizes möglicherweise größtenteils entfernte Dokumente enthalten.

Hier kommt das Zusammenführen ins Spiel. Zusammenführen - ist der Prozess des Kombinierens mehrerer Indizes, um insgesamt einen effizienteren Index zu erhalten. Grundsätzlich werden beim Zusammenführen Live-Dokumente in das neue Segment kopiert und alte Segmente vollständig entfernt.

Mit diesem einfachen Verfahren kann Lucene den Index in Bezug auf die Suchleistung in einem guten Zustand halten.

Hoffe es wird helfen.

Denis Bazhenov
quelle
1
Würde eine Suche zunächst nach den neuesten Segmenten beginnen, um zuerst die aktuellsten Ergebnisse zu finden? Zur Verdeutlichung: Angenommen, ein Dokument wird aktualisiert. Die ältere Version des Dokuments wird zur Kill-Liste hinzugefügt. Alle Übereinstimmungen, die in älteren Segmenten gefunden wurden, werden aus den Suchergebnissen entfernt, wenn ihre Dokument-ID mit einer ID in der Kill-Liste übereinstimmt.
Joel B
2
Ja du hast Recht. Das einzige, was zu erwähnen ist, ist, dass die endgültige Reihenfolge mithilfe von Sortierregeln definiert wird (Relevanzindex im trivialen Fall). Daher ist die Reihenfolge, in der Segmente durchsucht werden, nicht relevant.
Denis Bazhenov
12

Es ist ein invertierter Index , der jedoch nicht angibt, welche Struktur verwendet wird. Das Indexformat in Lucene enthält vollständige Informationen.
Beginnen Sie mit 'Zusammenfassung der Dateierweiterungen'.

Sie werden zuerst feststellen, dass es sich um verschiedene Indizes handelt. Soweit ich feststellen konnte, verwendet keiner von diesen streng genommen einen B-Baum , aber es gibt Ähnlichkeiten - die obigen Strukturen ähneln Bäumen.

Unvernunft
quelle
1
Der invertierte Index von Lucene basiert auf einer Sprungliste, nicht auf einem B-Baum. Immer noch eine baumartige Struktur im weitesten Sinne, aber nur um vollständig zu sein - siehe z. B. diese SO-Frage zu. Lucene verwendet eine Überspringliste und diese SO-Frage, warum Überspringlisten B-Bäumen vorzuziehen sind .
fnl