Frage Wie dokumentiert Lucene Dokumente?


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

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

Auf dem obigen Link heißt es, dass Lucene diesen Algorithmus für die Indizierung verwendet:

  • inkrementeller Algorithmus:      
    • Pflegen Sie einen Stapel von Segment-Indizes
    • Erstellen Sie einen Index für jedes eingehende Dokument
    • Schiebe neue Indizes auf den Stapel
    • Sei b = 10 der Verschmelzungsfaktor; 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 Indexierung?

Verwendet Lucene den B-Tree-Algorithmus oder einen anderen Algorithmus wie diesen für die Indexierung - oder hat es einen bestimmten Algorithmus?


75
2018-04-08 17:51


Ursprung


Antworten:


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

Edit 12/2014: Aufgrund des ursprünglichen Löschens auf eine archivierte Version aktualisiert, ist wahrscheinlich die beste neuere Alternative http://lucene.apache.org/core/3_6_2/fileformats.html

Es gibt eine noch neuere Version bei 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 haben als die ältere.

Kurz gesagt, wenn Lucene ein Dokument indiziert, wird es in mehrere Begriffe unterteilt. Anschließend speichert es die Begriffe in einer Indexdatei, wobei jeder Begriff den Dokumenten zugeordnet ist, die ihn enthalten. Man könnte es sich wie eine Hashtable vorstellen.

Begriffe werden unter Verwendung eines Analysators erzeugt, der jedes Wort in seiner Wurzelform hält. Der populärste 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 den gleichen Analysator verarbeitet, der zum Erstellen des Index verwendet wurde, und dann zum Suchen der übereinstimmenden Begriffe im Index verwendet. Dies bietet eine Liste von Dokumenten, die der Abfrage entsprechen.


49
2018-04-09 13:22



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

Indizierungsprozess ist ziemlich einfach, wenn Sie Details auf niedriger Ebene ignorieren. Lucene-Form, was aus Dokumenten "invertierter Index" genannt wird. Wenn also ein Dokument mit dem Text "Zu sein oder nicht" und id = 1 erscheint, würde der umgekehrte Index wie folgt aussehen:

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

Das ist es im Grunde - der Index vom Wort zum Liste von Dokumenten, die ein gegebenes Wort enthalten. Jede Zeile dieses Indexes (Wortes) wird als Buchungsliste bezeichnet. Dieser Index wird dann für den Langzeitspeicher beibehalten.

In Wirklichkeit sind die Dinge natürlich komplizierter:

  • Lucene kann einige Wörter basierend auf dem jeweiligen Analyzer überspringen;
  • Wörter können unter Verwendung des Stammbildungsalgorithmus vorverarbeitet werden, um Flexia der Sprache zu reduzieren;
  • Die Buchungsliste kann nicht nur die Bezeichner der Dokumente enthalten, sondern auch den Offset des gegebenen Wortes innerhalb des Dokuments (möglicherweise mehrere Instanzen) und einige andere zusätzliche Informationen.

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

Es ist jedoch wichtig zu verstehen, dass Lucene Index ist nur anhängen. Zu einem bestimmten Zeitpunkt entscheidet die Anwendung, alle Änderungen im Index zu übernehmen (zu veröffentlichen). Lucene beendet alle Serviceoperationen mit Index und schließt es, damit es für die Suche zur Verfügung steht. Nach dem Commit-Index grundsätzlich unveränderbar. Dieser Index (oder Indexteil) wird aufgerufen Segment. Wenn Lucene die Suche nach einer Abfrage ausführt, sucht es in allen verfügbaren Segmenten.

So stellt sich die Frage - wie können wir? Ändern Sie bereits indizierte Dokumente?

Neue Dokumente oder neue Versionen von bereits indexierten Dokumenten werden in neuen Segmenten indiziert, und alte Versionen werden in früheren Segmenten mit Hilfe von sog. Liste töten. Die Kill-Liste ist der einzige Teil des Committed-Index, der sich ändern kann. Wie Sie sich denken können, sinkt die Effizienz des Index mit der Zeit, da alte Indizes meist entfernte Dokumente enthalten.

Hier kommt die Zusammenführung ins Spiel. Zusammenführen - ist der Prozess der Kombination mehrerer Indizes, um insgesamt einen effizienteren Index zu erhalten. Was während der Zusammenführung grundsätzlich passiert, ist, dass Live-Dokumente in das neue Segment kopiert und alte Segmente vollständig entfernt werden.

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

Ich hoffe es hilft.


21
2017-10-01 01:58



Kurz gesagt, Lucene erstellt einen invertierten Index mit Überspringen-Listen  auf der Festplatteund lädt dann eine Zuordnung für die indizierten Terme in Erinnerung Verwendung einer Endlicher Zustandswandler (FST). Beachten Sie jedoch, dass Lucene lädt (notwendigerweise) nicht alle indizierten Ausdrücke in den RAM, wie Michael McCandless, der Autor von Lucenes Indexsystem selbst, beschrieben hat. Beachten Sie, dass bei Verwendung von Skip-Listen der Index von einem Treffer zu einem anderen durchlaufen werden kann einstellen und insbesondere Bereichsabfragen möglich (ähnlich wie B-Trees). Und das Wikipedia-Eintrag zur Indizierung von Skip-Listen erklärt auch, warum Lucenes Skip-List-Implementierung als a bezeichnet wird mehrstufig Skip-List - im Wesentlichen, zu machen O(log n) Nachschlagen möglich (wieder ähnlich wie B-Trees).

Also einmal der invertierte (Term) Index - der auf a basiert Skip-List-Datenstruktur - wird aus den Dokumenten erstellt, der Index wird auf der Festplatte gespeichert. Lucene lädt dann (wie bereits gesagt: möglicherweise nur einige von) diese Begriffe in ein Endlicher Zustandswandler, in einer FST-Implementierung locker inspiriert durch Morfologick.

Michael McCandless (auch) macht einen ziemlich guten und knappen Job Erklären, wie und warum Lucene ein (minimal acyclisches) FST verwendet die Begriffe Lucene speichern im Speicher, im Wesentlichen als a SortedMap<ByteSequence,SomeOutput>und gibt eine Grundidee für die Funktionsweise von FSTs (d. h. wie die FST die Byte-Sequenzen [d. h. die indizierten Terme] komprimiert, um die Speicherverwendung dieser Abbildung sub-linear zu machen). Und er zeigt auf das Papier, das den bestimmten FST-Algorithmus beschreibt Lucene verwendet auch.

Für diejenigen, die neugierig sind, warum Lucene Skip-Listen verwendet, während die meisten Datenbanken (B +) - und / oder (B) -Tees verwenden, werfen Sie einen Blick darauf das Recht SO Antwort bezüglich dieser Frage (Skip-Lists vs. B-Trees). Diese Antwort gibt eine ziemlich gute, tiefe Erklärung - im Wesentlichen, nicht so sehr machen gleichzeitige Aktualisierungen des Index "zugänglicher" (weil Sie entscheiden können, einen B-Baum nicht sofort wieder auszugleichen, wodurch ungefähr die gleiche gleichzeitige Leistung wie eine Skip-Liste erhalten wird), sondern Skip-Listen ersparen Ihnen die Arbeit an der (verzögert oder nicht) Auswuchtvorgang (Letztendlich) benötigt von B-Trees (tatsächlich, wie die Antwort zeigt / Referenzen, gibt es wahrscheinlich sehr geringe Leistungsunterschiede zwischen B-Trees und [mehrstufigen] Skip-Listen, wenn beide "richtig gemacht" werden.)


16
2018-04-04 09:30



Es ist invertierter Index, aber das gibt nicht an, welche Struktur es verwendet. Indexformat in Lucene hat vollständige Informationen.
Beginnen Sie mit 'Zusammenfassung der Dateierweiterungen'.

Sie werden zuerst bemerken, dass es über verschiedene Indizes spricht. Soweit ich feststellen konnte, verwendet keiner von diesen streng genommen a B-Baum, aber es gibt Ähnlichkeiten - die obigen Strukturen ähneln Bäumen.


12
2018-04-09 08:36