Apache Lucene 4.0

Neue Scoring-Algorithmen

Lange Zeit wurde Lucene und Solr vorgeworfen, dass es lediglich das sehr einfache TF-IDF Model für das Scoring implementiert und es nicht möglich ist, dieses anzupassen ohne die Query-Engine komplett umzuschreiben. Dieser Vorwurf führte auch dazu, dass Lucene im wissenschaftlich/universitären Bereich oft nicht eingesetzt wurde. Glücklicherweise hatten Benutzer von Solr noch die Möglichkeit, über Funktionsaufrufe (Function Queries) das Scoring zu beeinflussen, jedoch nicht die Konzepte komplett umzustellen. So war es möglich, zumindest weitere einfache Faktoren in die Formel mit einzubauen, um – wie zum Beispiel bei einer geografischen Suche – die Entfernung vom Suchenden als Faktor in das Ranking mit einzubauen. Das normale TF-IDF Vektormodell konnte jedoch nicht verlassen werden.

Lucene 4.0 ermöglicht es nun, nachdem die API der „Similarity“ Klasse angepasst wurde, vielfältige Anpassungen durchzuführen. In der alten Similarity Klasse konnten bisher nur einige Faktoren ausgetauscht werden, wie beispielsweise zur Berechnung von Norms. Mit Lucene 4.0 kommt jetzt aber die Möglichkeit hinzu, auf fast den kompletten Scoring-Workflow einzuwirken. Als Beispiel hierfür finden sich neue Klassen für bekannte Algorithmen/Modelle wie“Okapi BM25″ [4], „Divergence from Randomness“ (DFR) [5] oder „Language Modelling Similaritiesa“ [6]. Selbstverständlich ist die bereits aus vorherigen Versionen bekannte TF-IDF Similarity unter dem Namen TFIDFSimilarity (früher DefaultSimilarity) ebenfalls auswählbar (und ist auch weiterhin der Standard-Algorithmus).

Um diese neuen Modelle umsetzen zu können, müssen auch neue Statistiken während des Indexings erhoben werden. Bisher gab es neben der per-Dokument Norm (welche Faktoren wie Boost, Länge, o.ä. umfasste) nur noch Term- und Dokumentfrequenz als Statistiken. Lucene 4.0 fügt denen zahlreiche neue hinzu. Bei der Implementierung eigener Similarities stehen diese nun als CollectionStatistics und TermStatistics-Objekte zur Verfügung und sind natürlich in das Indexformat mit aufgenommen worden. Allerdings muss man beachten, dass für Indizes aus vorherigen Lucene-Versionen diese leider nicht zur Verfügung stehen. Das stört aber nicht weiter, da man beim Wechsel der Similarity sowieso alle Dokumente neu indexieren muss, weil einige von der Similarity-Implementation abhängige Faktoren (wie die Dokument-Norm) mit im Index gespeichert werden. Benötigt man für eigene Similarities weitere Faktoren pro Dokument, kann man diese in einem neuen Feldtyp „DocValues“ speichern. Faktoren pro Termposition kann man, wie schon in vorherigen Lucene-Versionen, über Payloads ablegen.

DocValues / Column-Stride-Fields

Jeder Lucene-Anwender kennt ihn, jeder hasst ihn und bei den meisten Committern verursacht er Bauchschmerzen: der FieldCache. Eingeführt wurde er in frühen Lucene Versionen, um eine Sortierung der Suchresultate nach anderen Kriterien als dem Score zu ermöglichen. Der große Nachteil dieses Caches ist seine Funktionsweise.

Er soll für schnellen Zugriff pro Dokument einen numerischen Wert (oder String) zu Verfügung stellen, so dass Suchresultate schnell danach sortiert werden können. Dazu ist es notwendig, diese Werte im wahlfreien Zugriff zur Verfügung zu stellen. Eine Art von Feldern, die einen solchen Zugriff erlauben, sind die sogenannten „Stored Fields“, die üblicherweise für die Präsentation von Suchergebnissen verwendet werden (zum Beispiel den Titel des Dokuments und eine kurze Zusammenfassung). Da diese Felder von variabler Länge sind und diese für jedes Dokument auch immer alle auf einmal gelesen werden müssen, ist der Einsatz für die Sortierung von Resultaten gleich Null: Zum Vergleich zweier Suchergebnisse müssen mindestens vier Disk-Seeks gemacht werden. Da alle Stored Fields eines Dokuments in einem Block abgelegt sind, müssen diese dabei jedes Mal als Ganzes neu eingelesen und dekodiert werden, da nicht für alle Dokumente alle Felder im Speicher gehalten werden können.

Der FieldCache, der in Lucene 1.4 eingeführt wurde, verwendete einen anderen Ansatz, um den schnellen wahlfreien Zugriff zu ermöglichen: Es wurde das Term Dictionary als Datenquelle benutzt und anschließend für jeden Term alle Dokumentnummern aus der Posting-Liste eingelesen. Anschließend wurde ein Zeiger auf den Term am Array-Index des Dokuments im RAM abgelegt. Durch einen einfachen Array-Access war es dann möglich, den Wert des Feldes (der Term) durch einen Lookup nach der Dokumentnummer zu finden. Bei primitiven Datentypen wie Integern oder Fließkommawerten konnten diese auch sofort im Array abgelegt werden. Der Nachteil dieses Cache war der Aufwand ihn zu bauen: Es musste für ein ganzes Feld das Term Dictionary und alle Postings gelesen werden (Un-Inverting des Index).

Neu in Lucene 4.0 ist jetzt ein „materialisierter“ FieldCache: Es wird nun das Array mit einem Wert pro Dokument direkt in ein separates File geschrieben und kann beim Öffnen des Index wahlweise wie der FieldCache direkt ins RAM geladen werden oder via Memory Mapping verfügbar gemacht werden. Der Index wird dadurch zwar größer, man spart sich aber das sonst notwendige Un-Inverting.

Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.