Apache Lucene 4.0

Endliche Automaten und Transduktoren

Bei der Abfrage macht Lucene 4.0 nun an zahlreichen Stellen Gebrauch von finiten Automaten. Dies begann mit einer Optimierung von Wildcard-Queries, dann kamen auch reguläre Ausdrücke auf Terme hinzu und schließlich wurden auch die in vorherigen Versionen sehr langsamen Fuzzy-Queries um den Faktor 100 bis 200 verschnellert [2]. All diese vorher genannten Abfrage-Typen haben etwas gemeinsam: Sie müssen aus dem Term Dictionary eine Reihe von Termen heraussuchen, die das Kriterium erfüllen und anschließend für alle diese Terme die Dokumenttreffer finden. Die Basisklasse all dieser Queries ist MultiTermQuery. Das Term Dictionary ist in Unicode Reihenfolge sortiert, so dass zum Beispiel einfache PrefixQuery lediglich zum ersten Term mit diesem Prefix springen müssen (das ist ein einfacher Lookup, der sehr effizient ist) und dann alle Terme solange einsammeln, bis der letzte Term erreicht ist, bevor das Prefix wechselt. Das reduziert die Anzahl an Termen, die betrachtet werden müssen, erheblich. Bei den anderen Queries, wie zum Beispiel einem Wildcard- oder RegexQuery kann es jedoch sein, dass es kein gemeinsames Prefix gibt, so dass dann das gesamte Term Dictionary von vorne bis hinten gescannt werden musste, um alle treffenden Terme zu finden. Bei großen Índizes mit zahlreichen Termen wird das schnell sehr langsam.

Lucene 4.0 betrachtet nun sowohl das Term Dictionary als auch das Query an sich als finiten Zustandsautomaten (FSA) und kann über einen effektiv implementierten „intersect“-Algorithmus schrittweise alle Zustände beider Automaten betrachten und sich so von einem Zustand zum nächsten hangeln. Das läuft darauf hinaus, dass nicht nur anfänglich mit dem Prefix durch ein Lookup der erste Term gefunden werden kann, sondern auch während der Auflistung weitere „Seeks“ (Lookups) durchführen kann. Die bahnbrechende Neuerung im FuzzyQuery is nun, dass die dafür verwendete Levenshtein-Distanz auch durch einen solchen Zustandsautomaten formuliert werden kann [3], so dass genau der gleiche Algorithmus dafür genutzt werden kann. Zuvor war es nötig, dass alle Terme im Dictionary auf die passende Levenshtein-Distanz zum Query-Term geprüft werden mussten (da es hier kein Prefix gibt).

Wie man erwarten kann, ist das eigentliche Term Dictionary in Lucene 4.0 ebenfalls mit einem verwandten Konzept implementiert, nämlich als Finite State Transducer (FST). Dies ermöglicht die erwähnte Schnittmenge aller Zustände zwischen Query-FSA und Term-Dictionary-FST schnell zu finden. Das FST (implementiert durch BlockTreeTermsReader im Standard-Codec) ist obendrein kleiner und erlaubt es, nicht im Index vorhandene Terme schnell auszuschließen, so dass komplexe Abfragen mit vielen nicht vorhandenen Termen schneller ausgeführt werden.

Als letzte Komponente wurde der Suggester um eine WFST-Komponente erweitert. Diese erlaubt ein Google-ähnliches Autocomplete zur Verfügung zu stellen. Dieser Suggester ist allerdings auch schon in Lucene 3.6 vorhanden, da hierfür die Codec-API nicht benötigt wird, sei aber hier noch einmal erwähnt.

Kommentare

Schreibe einen Kommentar

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