© agencyby, 123RF.com

Um die stets wachsenden Datenbestände zu verarbeiten, brauchen auch moderne Rechner clevere Methoden. Das Open-Source-Framework Lucene implementiert die neuesten Such-Algorithmen und macht damit große Textsammlungen zugänglich.

Schon eine handelsüblicheFestplatte speichert heutzutage mehr Text als ganze Büchereien. In der digitalen Welt genügen althergebrachte Mittel wie Karteikartensysteme und ein belesener Bibliothekar daher nicht mehr, um das richtige Regal zu finden. Auch deren Software-Pendants von »find« bis »zgrep« sind nicht immer in der Lage, ein bestimmtes Textstück in Giga- oder Terabytes von Daten in akzeptabler Zeit aufzuspüren.

Suchen mit Methode

Die Wissenschaft, die sich mit der Lösung solcher Suchprobleme befasst, heißt Information Retrieval. Sie hat ausgefeilte Methoden entwickelt, mit denen sie Dateien aufspürt, von denen der Benutzer nicht einmal wusste, dass sie existieren.Die freie Java-Bibliothek Lucene [1] implementiert einige davon. Im Jahr 1999 veröffentlichte Doug Cutting eine erste Version von Lucene. Zwei Jahre später landete das Projekt, das den zweiten Vornamen von Cuttings Ehefrau trägt, im Rahmen des Jakarta-Programms unter der Schirmherrschaft der Apache Foundation. Diese erhob es 2005 in den Status eines Top-Level-Projekts.

Seit Oktober 2012 steht Lucene in Version 4.0 zur Verfügung, deren Entwicklung derzeit noch parallel zur Vorgängerausgabe 3.6 stattfindet. Die Index-Dateistrukturen sind abwärtskompatibel, sodass ein Umstieg von 3.6 auf 4.0 keine Probleme verursacht. Inzwischen gilt Lucene als eine der am weitesten verbreiteten Lösungen für die Indizierung und Suche von Texten.

Karteikarten und Index

Die grundlegende Technik von Lucene wie auch anderer Information-Retrieval-Software gleicht den in Büchereien früher gängigen Karteikartensystemen. Unter den Unix-Tools ist das Verfahren durch »(s)locate« ebenfalls bekannt: Lucene erzeugt zunächst einen so genannten inversen Index über die in einer Sammlung vorhandenen Dokumente. In diesem sucht es bei einer Benutzeranfrage nach passenden Inhalten, statt alle Texte zu durchstöbern.

Ein solcher Index besteht aus einer alphabetisch sortierten Liste aller in der Textsammlung vorkommenden Wörter. Jeder Eintrag in dieser Liste enthält Zeiger auf alle Dokumente, die das besagte Wort enthalten (Abbildung 1). Sucht ein Benutzer das Wort “Linux”, springt der Algorithmus zur entsprechenden Stelle im Index und liefert die dort referenzierten Dokumente zurück, in Abbildung 1 zum Beispiel »Text 78« . Kommt “Linux” in keinem indizierten Text vor, existiert auch kein solcher Eintrag.

Abbildung 1: In einem inversen Index enthält jedes Wort einer Dokumentsammlung Zeiger auf die Dokumente, in denen es vorkommt.

Skalierbarkeit

Dass dieser Trick aus der natürlichen Ordnung der Wörter in Schriftstücken auch bei sehr großen Datenmengen schnell durchsuchbare Indizes produziert, sieht, wer den Aufwand der nötigen Rechenoperationen analysiert: Angenommen eine Textsammlung enthält 1000 Dokumente mit durchschnittlich 200 Wörtern, also insgesamt 200000 Wörter. Würde bei einer Suche nach einem Wort die Sammlung in ihrer natürlichen Ordnung durchsucht, müsste der Algorithmus 200000 Wortvergleiche anstellen.

Der inverse Index hält hingegen für gleiche Wörter nur einen einzigen Eintrag vor. Die Zahl der Einträge hängt von der Textbeschaffenheit ab, liegt aber bei natürlichsprachlichen Texten immer weit unter der Gesamtanzahl. Bei einer Textsammlung mit einer Gesamtlänge von 200000 Wörtern wäre beispielsweise eine Anzahl von 10000 unterschiedlichen Wörtern realistisch.

Der inverse Index skaliert gut, denn die Zahl der unterschiedlichen Wörter, das Vokabular, wächst auf Grund linguistischer Gesetzmäßigkeiten deutlich langsamer als die Gesamtlänge einer Textsammlung (siehe Kasten “Zipf’sches Gesetz”). Zur Sammlung hinzugefügte Dokumente erzeugen irgendwann nur noch sehr wenige oder gar keine neuen Einträge mehr im Index, es werden lediglich an bereits existierende Einträge weitere Zeiger auf Dokumente angehängt.

Wer die Möglichkeiten von Lucene ausprobieren möchte, ohne eine eigene Anwendung zu programmieren, greift auf das Such-Servlet Solr [2] zurück (siehe den Kasten “Lucene in allen Facetten”). Seine Entwicklung findet parallel zur Lucene-Bibliothek statt, daher steht es wie Lucene in den Versionen 3.6 und 4.0 zur Verfügung. Version 4.0 bietet teilweise einfacher nutzbare Schnittstellen, einige optionale experimentelle Features und verwendet leicht veränderte, aber abwärtskompatible Index-Strukturen. Nach Erfahrung des Autors hat sie ihre offizielle Einordnung als stabile Version in der Tat verdient.

Nach dem Entpacken des Archivs findet der angehende Textforscher das Java-Archiv »start.jar« im Unterverzeichnis »examples« . Es enthält einen Jetty-Webserver, der den Zugriff auf den Solr-Index per HTTP ermöglicht. Nach dem Start mit »java -jar start.jar« horcht dieser Server auf dem TCP-Port 8983. Einen leeren Beispielindex namens »collection1« legt die Software automatisch an und verwendet ihn für die weiteren Operationen. Unter »http://localhost:8983/solr/« stellt das Webinterface einem Browser Informationen über System, Java-Umgebung und Index bereit (Abbildung 2).

Abbildung 2: Das Solr-Webinterface gibt Auskunft über den Status des Systems und die vorhandenen Indizes.

Die auf dem Webserver laufende Solr-Installation steuert man über die HTTP-Komandos »POST« und »GET« . Um Dokumente in den Index einzuspeisen, hält Solr im Verzeichnis »examples/examplesdocs« neben einigen Beispieldokumenten das Programm »post.jar« bereit. Es erwartet als Parameter eine oder mehrere Dateien, die es per »POST« an den Server unter der Adresse »http://localhost:8983« weiterreicht.

Die XML-Beispieldateien, die im Verzeichnis »examples/examplesdocs« liegen, folgen einer von Solr festgelegten Konvention: Das »<add>« -Element bildet ihre Wurzel und befiehlt Solr, im Weiteren beschriebene Dokumente dem Index hinzuzufügen. Es folgen eine oder mehrere Dokumentdeklarationen mit »<doc>« . Darin befinden sich die einzelnen Felder des Dokuments, die mit »<field name=”Name“>« definiert sind. Nun folgt der Inhalt des Feldes, das XML-gemäß mit »</field>« abschließt.

Ein Dokument, viele Felder

An dieser Stelle führt Solr ein wichtiges Konzept von Lucene ein: Felder, von denen jedes Dokument im Index eines oder mehrere vorhält. Diese folgen keinem allgemein definierten Schema, jedes Dokument darf auch innerhalb eines Index Felder unterschiedlicher Namen und Inhalte enthalten. In der Praxis dienen die Felder dazu, Inhalte zu kategorisieren und separat durchsuchbar zu machen. Die Dokumente einer indizierten Büchersammlung enthalten zum Beispiel ein Feld namens »Text« mit dem eigentlichen Inhalt, während vom Text unabhängige Meta-Informationen in den Feldern »Autor« und »Jahr« vorliegen.

Das Schema, das der Solr-Beispielserver verwendet, definiert das Feld namens »id« als eindeutigen Schlüssel, sodass immer nur genau ein Dokument mit dem dort angegebenen Wert im Index existiert. Ein neues Dokument mit einem bereits existierenden »id« -Wert überschreibt das bestehende. Über die Datei »conf/schema.xml« im Solr-Verzeichnis, für die sich unter »example/solr/collection1/conf/schema.xml« ein ausführliches Beispiel befindet, lassen sich die XML-Elemente nach Belieben umdefinieren. Die Datei enthält auch die sinnvolle Empfehlung, das XML-Schema nicht nur korrekt, sondern auch kurz, prägnant und umstandslos nutzbar zu gestalten.

Neben XML hält Solr Handler für die Dateiformate Json und CSV vor. Bei ersterem steht jedes Dokument zwischen geschweiften Klammern, in denen jedes Feld-Wert-Paar nach diesem Muster deklariert wird: »”Autor”:”Johann Doe”« . Eine Beispieldatei liegt im »exampledocs« -Verzeichnis unter »books.json« .

In einer CSV-Datei stehen die Feldnamen in der ersten Zeile, jeweils durch Kommata getrennt. Jede weitere Zeile führt je ein Dokument auf, mit den Werten für die Felder in der Reihenfolge der Feldnamen in der ersten Zeile und ebenfalls durch Kommata getrennt. Auch hierfür liefert das Solr-Archiv ein Beispiel in der Datei »books.csv« .

Nachdem der Solr-Index mit Dokumenten gefüllt ist, etwa mit dem Befehl »java -jar post.jar *.xml« , steht dem Schritt zum eigentlichen Zweck der Übung nichts mehr im Wege. Die Suche geschieht direkt über den laufenden Webserver unter Angabe des Indexnamens, für »collection1« ruft man im Browser die Abfrageseite »http://localhost:8983/solr/#/collection1/query« auf (Abbildung 3). Eine Suchanfrage (Query) gibt der Benutzer im Feld »q« in der Syntax der Solr-Abfragesprache [7] ein. Für einen einzelnen Ausdruck in einem bestimmten Feld lautet das passende Format »Feldname:Anfrage« .

Abbildung 3: Die Webschnittstelle der Lucene-Anwendung Solr ermöglicht Suchanfragen im Browser; hier ist die Ausgabe eines Resultats im Json-Format zu sehen.

Erhält Solr mehrere Such-Ausdrücke, die sich auf dasselbe oder auf verschiedene Felder beziehen können, nimmt es ohne nähere Angaben eine Oder-Verknüpfung an. Dann liefert es Dokumente zurück, die mindestens einen der angegebenen Ausdrücke im passenden Feld enthalten. Wer eine Wortfolge sucht, schließt diese mit Anführungszeichen zu einem Ausdruck zusammen. Zum Beispiel führt die Anfrage »text:”das gelbe Haus”« eine solche Phrasensuche aus.

Möchte der Anwender einen Ausdruck als zwingend definieren, setzt er diesem ein »+« -Zeichen vor. Die gleiche Funktionalität bietet auch der Operator »AND« : Zwischen zwei Ausdrücke gesetzt markiert er beide als unverzichtbar. Weitere Suchklauseln ohne »+« helfen Lucene dabei, die Relevanz der Treffer besser zu bemessen.

Abfragesprachen

Die Solr- und Lucene-Query-Sprachen halten zur genaueren Spezifikation von Anfragen die Möglichkeit zur Bereich-Suche mit beispielsweise »[a TO m]« und zur Wildcard-Suche mit Ausdrücken wie »Linu*« parat. Im Unterschied zur nativen Lucene-Abfragesprache [8] erlaubt es Solr dank einer Erweiterung auch, Wildcards am Anfang einer Bereich-Suche zu verwenden, etwa »[* TO m]« . Außerdem kommt analog zum »+« das »-« -Zeichen zum Einsatz, um Dokumente, die bestimmte Ausdrücke enthalten, von der Trefferliste zu streichen.

Solr liefert das Ergebnis in dem Format zurück, das der Benutzer im Browser in der Auswahlliste »wt« festlegt, bevor er die Suche startet. In Frage kommen wie bei der Indizierung XML, CSV und Json. Alternativ generiert die Anwendung direkt PHP-, Ruby- oder Python-Code; letzterer unterscheidet sich allerdings nur im Detail von Json.

Mit Lucene programmieren

Die Lucene-Bibliothek bietet praktisch unbegrenzte Möglichkeiten, um eigene Suchapplikationen für Spezialanwendungen zu entwerfen, die über die Solr-Funktionalität hinausgehen. Bei der Entwicklung liegt der Fokus wiederum auf den beiden zentralen Schritten der Textsuche mittels inverser Indizes: erst indizieren, dann suchen.

Die Java-Klasse »org.apache.lucene.index.IndexWriter« ist dafür zuständig, Indizes zu erstellen und zu verändern (Listing 1). Ihr Konstruktor nimmt zwei Argumente entgegen: ein Verzeichnis in Form eines Objekts der Klasse »org.apache.lucene.store.Directory« und eine Konfiguration mittels »org.apache.lucene.index.IndexWriterConfig« . Dann fügt der Programmierer mit der »IndexWriter« -Methode »addDocument()« ein oder mit »addDocuments()« mehrere Dokumente zum Index hinzu. Mit dem abschließenden »close()« -Aufruf schreibt er die Änderungen auf den Datenträger und schließt geöffnete Dateien.

01 /* Dieses Beispiel ignoriert Exceptions. Sie sind in der Praxis durch die umgebende Funktion mit Throw zu werfen oder mit Try-/Catch-Blöcken abzufangen. */
02
03 /* Den IndexWriter erzeugen */
04 Analyzer analyzer = new GermanAnalyzer(VERSION.Lucene_40);
05 IndexWriterConfig config = new IndexWriterConfig(analyzer);
06 Directory dir = FSDirectory.open(new File("/home/user/lucene/index"));
07 IndexWriter writer = new IndexWriter(dir, config);
08
09 /* Das Dokument */
10 Field textField = new TextField("text", "Otto geht nach Hause.", Field.Store.YES);
11 Document doc = new Document();
12 doc.add(textField);
13
14 /* Dokument zum Index hinzufügen und alle Dateien schreiben und schließen */
15 writer.addDocument(doc);
16 writer.close();

Ein Dokument besteht – wie oben beschrieben – aus einer beliebigen Anzahl von Feldern, die Lucene über die Klasse »org.apache.lucene.document.Field« definiert. Über die »add()« -Methode fügt der Programmierer sie einem »Document« -Objekt hinzu. Für die meisten in der Praxis gängigen Fälle hält Lucene passende Unterklassen bereit, etwa »TextField« , »IntField« und »DoubleField« .

Der Standardkonstruktor »TextField« erwartet wie die meisten anderen Feld-Klassen den Namen und den Inhalt des Feldes in Form von Strings als Argumente sowie eine Angabe darüber, ob der Text auch in seiner originalen Version im Index landen soll. Der zu durchsuchende Text steht in der Praxis meist nicht in einer kurzen Zeichenkette wie in Zeile 10 von Listing 1, sondern wird durch eine String-Variable referenziert. Über eine Liste von Dokumenten kann der Programmierer mittels einer Schleife iterieren.

Anschließend schreibt der Code das neue Dokument in den Index, wobei das erwähnte »IndexWriter« -Objekt zum Zuge kommt. Der Konstruktor benötigt ein »Directory« – und ein »IndexWriterConfig« -Objekt. Für letzteres kommt eine weitere wichtige Komponente zum Tragen, nämlich die Implementierung der abstrakten Klasse »org.apache.lucene.analysis.Analyzer« , die sich um die Analyse der eingespeisten Texte kümmert. Die Analyzer-Implementationen unterscheiden sich unter anderem in der Sprache, für die sie gemacht sind: Für Deutsch stellt Lucene »org.apache.lucene.analysis.de.GermanAnalyzer« bereit.

Tokenisierung

Der »Analyzer« spielt eine zentrale Rolle für die Struktur des Index, denn er sorgt unter anderem für die “Tokenisierung”, also die Aufteilung des Textes in jene Bestandteile, die im inversen Index eigene Einträge darstellen (Tokens). Das ist eine komplexe Aufgabe, beispielsweise muss er Satz- und Sonderzeichen korrekt als Teile eines Token – etwa in einer Web- oder E-Mail-Adresse – von eigenständigen Zeichen wie dem abschließenden Satzpunkt unterscheiden. Des Weiteren bieten sich bei der Analyse zahlreiche Möglichkeiten zur Optimierung des Index, zum Beispiel mit Hilfe von Filtern (bei »org.apache.lucene.analysis.TokenFilter« ) häufige, aber inhaltlich mit wenig Aussagekraft behaftete Funktionswörter wie “und” zu entfernen.

Weitere Analyzer setzen die Suche auf Grundlage anderer Einheiten als der Wörter um. Im Paket »org.apache.lucene.analysis.phonetic« etwa gibt es einige Varianten, die statt auf Orthographie auf phonetische Umschreibungen setzen. So erlaubt etwa der Beider-Morse-Filter die Suche nach ähnlich klingenden Wörtern; der von Lucene mitgelieferte Filter beschränkt sich bislang jedoch auf Englisch. Andere Analyzer unterteilen einen Text beispielsweise nicht in Wörter, sondern in Silben, oder reduzieren die Zahl der unterschiedlichen Wörter und damit die Indexgröße, indem sie jedes Wort auf seinen Stamm reduzieren.

Analyzer und Tokenizer bilden wichtige Bestandteile des Indizierungsprozesses, weil sie darüber entscheiden, wonach ein Benutzer suchen kann. Im Beispiel in Abbildung 1 bildet etwa das Wort »Linux-Magazin« einen Eintrag im Index, ein anderer Tokenizer könnte es aber auch in die drei Tokens »Linux« , »-« und »Magazin« unterteilen. In letzterem Fall hätte eine Suche nach einem zusammenhängenden Wort »Linux-Magazin« keinen Erfolg; erst eine Phrasensuche nach den drei aufeinanderfolgenden Tokens führte zum gewünschten Ergebnis.

Umgekehrt hätte die feingliedrige Aufteilung den Vorteil, dass bei der Suche nach »Linux« ein Dokument, das »Linux-Magazin« enthält, auch ohne den Einsatz von Wildcards gefunden würde.

Auf der Suche

Um eventueller Verwirrung auf Grund unterschiedlicher Analyse- und Tokenisierungsalgorithmen vorzubeugen, durchlaufen eingehende Suchanfragen normalerweise denselben Analyzer wie die indizierten Dokumente. Auch in der sonstigen Vorgehensweise ähnelt die Suche der Indizierung.

Für das Einlesen eines Index zeichnet die abstrakte Klasse »org.apache.lucene.index.IndexReader« verantwortlich, wie in Listing 2 zu sehen ist. Die Methode »open(Directory dir)« der Klasse »org.apache.lucene.index.DirectoryReader« erzeugt ein solches Objekt. Der Konstruktor von »org.apache.lucene.search.IndexSearcher« nimmt den »IndexReader« als Argument entgegen.

01 String queryString = new String("text:Linux-Magazin");
02 int maxHits = 100;
03
04 /* IndexReader und IndexSearcher erzeugen */
05 Analyzer analyzer = new GermanAnalyzer(VERSION.Lucene_40);
06 Directory dir = FSDirectory.open(new File("/home/user/lucene/index"));
07 IndexReader reader = DirectoryReader.open(dir);
08 IndexSearcher searcher = new IndexSearcher(reader);
09
10 /* Query erzeugen und suchen */
11 StandardQueryParser parser = new StandardQueryParser(analyzer);
12 Query query = parser.parse(queryString);
13 TopDocs topdocs = searcher.search(query, maxHits);
14
15 /* Treffer auslesen und ausgeben */
16 ScoreDoc[] docs = topdocs.scoreDocs;
17 for (ScoreDoc doc : doc)
18   System.out.println(doc.doc+"\t"+doc.score);
19
20 reader.close();

Der »IndexSearcher« steht nun bereit, um mittels eines »Query« -Objekts Suchanfragen auszuführen. Ein Objekt der Klasse »org.apache.lucene.queryparser.flexible.standard.StandardQueryParser« erzeugt solche »Query« -Objekte mit der Methode »parse()« aus einem Eingabe-String und einem Analyzer. Alternativ implementiert der Programmierer einen eigenen Query-Parser, der die unterschiedlichen Query-Typen oder wiederum selbst definierte Suchobjekte generiert.

Das Ergebnis übergibt er der »search()« -Methode des »IndexSearcher« . Deren Resultat besteht aus einem »org.apache.lucene.search.TopDocs« -Objekt, das die einzelnen Treffer sowie Angaben über die Trefferanzahl und den höchsten gefundenen Relevanzwert enthält.

Query-Objekte helfen übrigens auch dabei, Dokumente zu löschen. Dazu übergibt der Programmierer ein Query an die Methode »deleteDocuments()« eines »IndexWriter« , der dann passende Dokumente aus dem Index entfernt.

Sieger nach Punkten

Die Disziplin des Information Retrieval beschränkt sich nicht allein auf die Textsuche. Es geht auch darum, die potenziell sehr große Treffermenge nach der Relevanz für die eingegebene Suchanfrage der Benutzers zu sortieren. Lucene verwendet eine Vielzahl von Faktoren, um die Relevanz der Dokumente, die die Abfragebedingungen erfüllen, zu schätzen und in Zahlen auszudrücken. Harte Kriterien sind dabei schnell ausgemacht: Ein Dokument, das nicht alle mit »+« gekennzeichneten Ausdrücke enthält, erhält unverzüglich einen Score (Punktestand) von 0 zugewiesen. Analog gilt das ebenso für jene Dokumente, die einen mit »-« gekennzeichneten Suchausdruck enthalten.

Komplexer verhält es sich mit den Soll-Ausdrücken. Sie erhalten unterschiedlich viel Gewicht, der Faktor lehnt sich an das maßgeblich von der britischen Information-Retrieval-Pionierin Karen Spärck-Jones entwickelte TF-IDF-Maß (Term Frequency – Inverse Document Frequency) an [9]. Danach zählt ein Ausdruck – meist ein Wort oder eine Wortfolge –, der in jedem Text einer Sammlung auftaucht, als wenig bedeutsam für dessen Inhalt, während einer, der nur in einem oder wenigen Dokumenten vorkommt, als wichtiger gilt.

Boost

Auch hier bietet Lucene Möglichkeiten, nach eigenem Gutdünken einzugreifen. Der erste Ansatzpunkt liegt beim Anlegen der Felder eines Dokuments, deren relative Relevanz das Feld »boost« bestimmt. Ohne weitere Angaben liegt dieser Wert bei 1.0, die »Field« -Methode »setBoost()« manipuliert ihn. Je höher der Boost-Wert eines Feldes im Vergleich zu anderen Feldern ausfällt, desto höher bewertet Lucene Treffer darin. Wer ganze Dokumente statt einzelner Felder in der Relevanz-Rangliste nach oben befördern möchte, simuliert einen dokumentbezogenen Boost, indem er für jedes Feld des Dokuments den Boost-Wert erhöht.

Auch bei der Suche lässt sich ein angepasster Boost einrichten, der sich zusätzlich zu den im Index abgespeicherten Eigenheiten auswirkt. Dazu verändert man mit der »setBoost()« -Methode eines »Query« -Objekts den Faktor auf die gleiche Weise wie bei der Indizierung.

Lucene lässt Programmierern zahlreiche Möglichkeiten zu weiteren Eigenentwicklungen. Zusätzliche Informationen über einzelne Tokens oder Wörter speichern sie in einer so genannten Payload. Dort können sie beispielsweise linguistische Informationen über Syntax und Semantik ablegen und über die Query-Klasse »org.apache.lucene.search.payloads.PayloadTermQuery« abfragen.

Flexible Möglichkeiten

Weitere Spezial-Query-Klassen stehen bereit: darunter »PhraseQuery« für die Suche nach aufeinanderfolgenden Wörtern, »BooleanQuery« für die Verknüpfung einzelner Anfragen nach boolescher Logik oder die Klasse »FuzzyQuery« , die ähnliche Wörter wie das in einer Suchanfrage angegebene findet. Auch der »StandardQueryParser« verwendet diese Query-Klassen, doch der fantasievolle Lucene-Nutzer setzt sie für seine Zwecke im eigenen Query-Parser ein.

Wer Lucene mit dessen Standardmitteln nutzen möchte, findet mit Solr eine sofort anwendbare Applikation. Wer eigene Anwendungsfälle umsetzen will, der greift direkt auf das Lucene-API zurück; die eingehende Lektüre der Dokumentation und der Javadocs bietet Einstiegspunkte für die Entwicklung. (mhu)