Ein Kurzporträt der Suchtechnologie von Doug Cutting

Was ist eigentlich Apache Lucene?

Uwe Schindler

© Shutterstock.com/vs148

Spricht man von Lucene, ist oft die Java-Bibliothek gemeint. Die meisten nutzen aber wohl einen der Suchserver, die auf Lucene basieren: Apache Solr und Elasticsearch. Beide erleichtern das Deployment sowie die Integration von Lucene, indem sie die Suchmaschine als unabhängigen Server zur Verfügung stellen und die Skalierbarkeit durch einen verteilten Ansatz ermöglichen.

Jeder Internetnutzer hat sie schon mal verwendet. Selbst aus dem Desktop- und Mobilebereich ist sie inzwischen nicht mehr wegzudenken: die Suchfunktion, die das Auffinden von Dokumenten oder Textschnipseln in Dokumentensammlungen zum Kinderspiel macht. In kürzester Zeit werden mit einer Desktopsuchmaschine Dokumente zu einem bestimmten Thema hervorgezaubert, die schon lange in den Untiefen des Dateisystems verschollen schienen. Auf Webseiten hilft die Site-eigene Suche, schnell Inhalte zu finden, die über die Navigation vielleicht nur über lange Click-Sessions erreicht worden wären.

Oft basiert die Funktionalität hinter den so vertrauten Suchboxen auf der Arbeit des Entwicklerteams von Apache Lucene und den Partnerprojekten Apache Solr und Elasticsearch: Bei GitHub wird der Indexer für die Suche im Quellcode ebenso eingesetzt wie von Twitter, SoundCloud, Zalando, ImmobilienScout24, LinkedIn oder XING. Selbst Wikipedia verwendet Apache Lucene für die Recherche von Artikeln. Entwickler, die JIRA als Issue Tracker einsetzen, verwenden Lucene, sobald sie nach Tickets suchen. Spricht man von Lucene, ist oft die Java-Bibliothek gemeint. Die meisten nutzen aber wohl einen der Suchserver, die auf Lucene basieren: Apache Solr und Elasticsearch. Beide erleichtern das Deployment sowie die Integration von Lucene, indem sie die Suchmaschine als unabhängigen Server zur Verfügung stellen und die Skalierbarkeit durch einen verteilten Ansatz ermöglichen. In den letzten Jahren sind vor allem Features wie Echtzeitsuche (NRT) und Analysefunktionen mit funktionalen Abfragen hinzugekommen.

Background

1999 kündigte Doug Cutting Lucene erstmals bei SourceForge an. Das erste Release 0.01 erblickte am 30.03.2000 das Licht der Welt. Sie war auch das Ergebnis von Cuttings Arbeit mit Volltextmaschinen bei Excite. Die Programmiersprache Java war gerade neu, Suchmaschinen waren grundsätzlich in C oder gar Assembler geschrieben. Cutting probierte in dieser neuen Programmiersprache einige neue Algorithmen aus, die den damaligen Stand der Volltextsuche revolutionierten, unter anderem inkrementelles Indexing (Hinzufügen/Löschen von Dokumenten zu/von einem bestehenden Index) – vorher war nur Batch-Indexing möglich. Und er hatte mit Java nicht auf das falsche Pferd gesetzt: Auch wenn immer noch manche Leute behaupten, Java sei zu langsam, trifft dies auf Lucene nicht zu, wie zahlreiche Benchmarks zeigen.

Ein Beispiel

Typischerweise wird Apache Lucene auf Webseiten mit viel textuellem Inhalt verwendet, den ein User durchsuchen können soll. Das können gescannte PDF-Bibliotheken aus der Zeitschriften-/Artikeldatenbank eines Verlags sein oder die Dokumentation im Firmenarchiv. Aber auch die Suche in kleineren Textsammlungen, wie die in einem Web-Content-Management-System oder dem E-Mail-Ordner in einer Smartphone-App, kann mit Lucene implementiert werden. Durch den feldbasierten Dokumentansatz lassen sich hervorragend auch strukturierte Daten durchsuchen, etwa Produkte in einem Onlineshop. Man kann sich einen Volltextindex, in der Fachsprache „Inverted Index“, wie den Index in einem Buch vorstellen (Abb. 1). Er enthält alle Terme, die in den indexierten Dokumenten vorkommen, als alphabetische Liste. Durch eine „binäre Suche“ findet man schnell den gesuchten Term (rot) im Index. Die Seitenzahlen (grün), in denen ein Wort vorkommt, sind gleichbedeutend mit den Dokument-IDs in einem Inverted Index. Dies wird in der Fachsprache „Postings List“ genannt. Lucene speichert neben den Dokument-IDs in der Postings List zusätzlich noch andere Metadaten wie die Position des Terms in jedem Dokument. Dies wird benötigt, um Suchen nach Wortphrasen unterstützen zu können.

Abb. 1: Man kann sich den Volltextindex wie den Index in einem Buch vorstellen

Abb. 1: Man kann sich den Volltextindex wie den Index in einem Buch vorstellen

Zur Erstellung des Indexes muss zusätzlich noch einiges an Arbeit geleistet werden: Zunächst müssen die Terme aus dem Text extrahiert werden. Die Konfiguration, wie dies geschieht, lässt sich mit Apache Lucene beliebig zusammenstellen (Abb. 2).

Abb. 2: Die Konfiguration lässt sich beliebig zusammenstellen

Abb. 2: Die Konfiguration lässt sich beliebig zusammenstellen

Die Auftrennung in Terme erfolgt in der „Tokenization“, was im einfachsten Fall durch Trennung an Leerzeichen oder einem regulären Ausdruck erfolgen kann (ähnlich einem String.split() in Java-Code). Bei Sprachen, die keine Leerzeichen enthalten (Chinesisch, Japanisch), ist das jedoch leider nicht ganz so einfach. Hier müssen Wörterbücher und statistische Ansätze benutzt werden. Nachfolgend werden über mehrere „Tokenfilter“ die Einzelwörter normalisiert (Verwandlung in Kleinbuchstaben, Plural entfernen, Synonyme hinzufügen). Da die gleichen Schritte auch auf die Suchanfrage des Benutzers angewandt werden, ist es möglich, im Index auch andere Schreibweisen als im Originaldokument zu finden. Lucene stellt für eine Vielzahl von Sprachen passende „Analyzer“ zur Verfügung, die bereits optimal aus Tokenizern und Tokenfiltern zusammengestellt werden.

Nachdem die Dokumente passend zu einer Suchanfrage im Index gefunden wurden, müssen die Ergebnisse noch sortiert werden, sodass die „relevantesten“ Dokumente zuerst auftauchen. Dazu verwendet Lucene verschiedene Rankingalgorithmen: Der einfachste ist das TF-IDF-Maß (Term Frequency – Inverse Document Frequency, deutsch: Termvorkommenshäufigkeit – inverse Dokumenthäufigkeit). Hierbei wird die Häufigkeit eines Terms in einem gefundenen Dokument (TF) ins Verhältnis zur Gesamtmenge an Dokumenten gesetzt (IDF). Ein Term, der in fast jedem Dokument vorkommt (z. B. Artikel), trägt weniger zur Relevanz bei als ein Term, der im gesamten Korpus nur ein- oder zweimal vorkommt. Ein Dokument, in dem dieser seltene Term zudem dann auch noch mehrfach vorkommt, ist wohl am relevantesten.

Ausblick

Seit der Version 4 von Apache Lucene ist es möglich, das Indexformat beliebig anzupassen (Index Codecs). Hier wird derzeit viel Arbeit hineingesteckt, um für bestimmte Datentypen (u. a. numerische Werte, versionierte Dokument-IDs) noch schnelleres Indexing und Retrieval anzubieten. Kurz gesagt: Performanz, Performanz, Performanz!

Außerdem wird die Unterstützung für Sprachen stetig verbessert. Derzeit ist z. B. ein Analyzer für die koreanische Sprache in Arbeit, was sich jedoch aufgrund der schlechten Qualität des gesponserten Codes etwas hinauszögert. Nach der Einführung von Finite State Transducern (FST) in das Indexformat der Version 4 bietet jedes weitere Release auch neue Algorithmen für hoch performante Eingabevervollständigung (Query Suggestion). In naher Zukunft wird Version 5.0 herauskommen, die neben zahlreichen Änderungen im API dann voll die neuen Dateisystemfeatures von Java 7 unterstützt. Auch der gesamte Legacy-Code wird darin entfernt worden sein. Diese Version wird keine alten Lucene-3-Indizes mehr lesen können, da die entsprechende Unterstützung zu zahlreichen Problemen, bis hin zu Datenverlust, geführt hat. Lucene Trunk (geplante Lucene-Version 6) wird dann Java 8 als Minimum voraussetzen.

Aufmacherbild: Concept for New Technology Corporate Business & development background von Shutterstock / Urheberrecht: vs148

Geschrieben von
Uwe Schindler
Uwe Schindler
Uwe Schindler ist Mitglied des Project Management Committee im Apache-Lucene-Projekt. Er ist mit seiner Consulting-Firma SD DataSolutions GmbH in Bremen ansässig und kümmert sich am Zentrum für Marine Umweltwissenschaften (MARUM) um die Suche nach geowissenschaftlichen Daten in der Umweltdatenbank PANGAEA.Blog: http://blog.thetaphi.deTwitter: @ThetaPh1
Kommentare

Hinterlasse einen Kommentar

Hinterlasse den ersten Kommentar!

avatar
400
  Subscribe  
Benachrichtige mich zu: