© ace03/Shutterstock.com
Grundfunktionen der Apache-Lucene-Bibliothek

Wie funktioniert eine Volltextsuchmaschine?


Apache Lucene ist inzwischen nicht mehr jedem in der Softwarebranche ein Begriff. Heutzutage benutzen viele Leute einfach Apache Solr oder Elasticsearch, um im Unternehmen die Recherche über die Datenbestände anzubieten, also etwa Produkte in Shops, Firmendokumente im Enterprise CMS oder auch Aggregationen des Datenbestands nach Kategorien (Facetting). Hinter den beiden Suchservern Apache Solr und Elasticsearch steckt jedoch dieselbe Technik: Apache Lucene. Bevor wir daher im zweiten Artikel dieses Schwerpunkts den Einsatz dieser Systeme im Enterprise-Umfeld durchleuchten und die Vor- und Nachteile beider Systeme darlegen, geht dieser Artikel auf die Bibliothek Apache Lucene und die dahinterstehenden Konzepte ein.

Viele Entwickler, die sich zum ersten Mal mit Volltextsuche beschäftigen, haben zuvor mit relationalen Datenbanken und Indizes gearbeitet und wissen, warum diese wichtig sind. In relationalen Datenbanken werden Daten in Tabellen gespeichert, zu deren Spalten sich Indizes hinzufügen lassen. Diese ermöglichen die Suche nach Werten oder helfen, Joins (Verknüpfungen) zwischen Tabellen durchzuführen. Schließlich wird bei relationalen Datenbanken viel Wert darauf gelegt, die Daten zu normalisieren: Es geht darum, möglichst wenige Redundanzen in Tabellenspalten zu haben und daher Attribute der Haupttabelle in beigeordnete Tabellen zu verlagern, wo diese unique sind.

Volltextsuche – was passiert da eigentlich?

Im Gegensatz dazu wird bei Volltextsuchmaschinen ein ganz anderer Ansatz gewählt: Man betrachtet nur einen Typ von Entität (Dokumente) und packt alle Attribute in diese Dokumente hinein. Diese wiederum bestehen aus teilweise strukturierten, oftmals aber auch aus unstrukturierten Textschnipseln, die in Felder gesteckt werden. Vereinfacht gesagt ist ein solches Dokument vergleichbar mit einem JSON-Dokument: Felder sind in diesem Vergleich die Keys, die Values der JSON-Dokumente sind die zu durchsuchenden Inhalte. Letztere sind dabei überhaupt nicht normalisiert, oftmals wird sogar der gesamte Volltext zusätzlich ebenfalls in ein Extrafeld gesteckt, sodass er schneller durchsuchbar ist.

Man stelle sich also eine Datenbank in Apache Lucene als eine Sammlung von Dateien im JSON-Format vor. Das Schema dieser Dateien ist ähnlich, aber nicht zwangsläufig identisch. Felder wie Titel, Autor oder Zusammenfassung gibt es bei allen Dokumenten. Manche können optional noch über weitere durchsuchbare Eigenschaften wie beispielweise Kategorien, Preise bei Produkten oder eben Veröffentlichungsjahr, Hersteller oder Kontaktmailadressen verfügen. Im Gegensatz zu relationalen Datenbanken ist bei Volltextsuchmaschinen auch die Möglichkeit wichtig, mehrere Werte pro Feldnamen abzulegen. So könnte das Feld Kategorien im fiktiven Dokumenten-JSON durchaus auch aus einem Array aus Kategorienamenelementen bestehen.

Eine typische Suchanfrage an eine Volltextsuchmaschine wäre nun beispielsweise: „Gib mir alle Dokumente, bei denen im Titel oder in der Zusammenfassung das Wort ‚Waschmaschine‘ vorkommt.“ Möchte man diese Begriffe in der Sammlung von JSON-Dateien finden, kann man natürlich zuerst mit dem UNIX-Tool grep suchen. Eine alternative Variante wäre, alle Dokumente in eine einfache Tabelle einer relationalen Datenbank zu kippen (pro JSON-Feld eine Spalte). Das funktioniert erst einmal ganz gut, aber das eigentliche Problem beider Möglichkeiten ist: Es handelt sich um eine langsame contains-Suche (grep geht jede Zeile durch und sucht nach dem Teilstring; die Datenbank benötigt ein like mit %Waschmaschine%). So etwas skaliert überhaupt nicht, denn es kann auch keiner der normalen Datenbankindizes benutzt werden. Des Weiteren sucht man nicht nach sogenannten Tokens (ganze Wörter), sondern nach Teilstrings. Die klassische SQL-Like- bzw. grep-Suche nach „schlecht“ würde beispielsweise auch „Geschlecht“ finden, was rein gar nichts miteinander zu tun hat.

Mit Apache Lucene baut man eine ganz andere Art von Index, der speziell für die Tokensuche entwickelt wurde. So manch einer kennt es noch aus dem Studium, vom Aufschlagen eines Fachbuchs: Auf den letzten Seiten findet man einen sogenannten Index (Abb. 1). In der IT-Fachsprache nennt man dies einen Inverted Index. Er enthält alle Terme oder Tokens, die in den indexierten Dokumenten vorkommen, als alphabetische Liste. Durch eine binäre Suche findet man schnell den gesuchten Term (blau) im Index. Die Seitenzahlen (rot), in denen ein Wort vorkommt, sind gleichbedeutend mit den Dokument-IDs in einem Inverted Index. Dies wird in der Fachsprache Postings List genannt. Der Index heißt „inverted“, weil er im Gegensatz zu dem klassischen Index einer Datenbanktabelle nicht basierend auf den Zeilen der Tabelle aufgebaut ist. Vielmehr ist es umgekehrt: Er zeigt von den Inhalten (Tokens) auf die Zeilen (unsere Dokumente), wobei auch mehrere Tokens auf das gleiche Dokument zeigen können.

schindler_lucene_1.tif_fmt1.jpgAbb. 1: Das Vorbild für den Lucene-Index: eine sortierte Liste von Termen mit Seitenzahlen (Postings)

In Apache Lucene wird der alphabetischen Liste mit den Tokens für den schnellen Look-up zusätzlich ein Finite State Transducer (FST) zur Seite gestellt, denn eine binäre Suche ist bekanntlich O(log n), wobei n die Anzahl der Terme ist. Obwohl natürliche Sprache einen begrenzten Umfang von Worten hat, ist das jedoch in der Praxis zu langsam: Oftmals können bei fehlerhaften Daten (versehentlich indexierte binäre Dokumente, gescannte Inhalte) oder gar bei Verwendung anderer Datentypen wie numerischen Werten zahlreiche Terme auftreten. Ein Finite State Transducer ist ähnlich gebaut wie ein regulärer Ausdruck. Der Input (Term) wird über ein finites Automaton Zeichen für Zeichen analysiert, dabei werden im Graphen zusätzliche Zeiger ins Term-Dictionary gespeichert. Beim Traversal durch den Automaton-Graphen werden die Werte an den Kanten des Graphen aufsummiert und anschließend als Zeiger auf den ersten Term im Dictionary benutzt, der mit dem gesuchten Präfix beginnt. In der Anfangszeit von Lucene war das durch eine einfache Look-up-Tabelle auf zwei Buchstaben begrenzt, ab dann musste mit binärer Suche ausgehend von der Position weitergesucht werden. Durch Einführung des FST-Ansatzes in Lucene 4 wurde dies dynamischer gestaltet – je nach Speicherbedarf und Verteilung der Terme wird dynamisch gearbeitet. Außerdem kann mit diesem Ansatz auch sehr schnell festgestellt werden, ob ein Term überhaupt im Index vorhanden ist.

Sobald man im Index den gewünschten Token gefunden hat, erhält man einige Metadaten übe...

Neugierig geworden? Wir haben diese Angebote für dich:

Angebote für Teams

Für Firmen haben wir individuelle Teamlizenzen. Wir erstellen Ihnen gerne ein passendes Angebot.

Das Library-Modell:
IP-Zugang

Das Company-Modell:
Domain-Zugang