Desktop-Suchmaschinen sollen der Kassenschlager im Jahr 2005 werden - haben nicht, aufgeschreckt und initiiert durch Googles Desktop-Search-Betaversion, alle namhaften Suchmaschinenhersteller eine solche als freie Beta bereits verfügbar (Microsoft und seit neuestem auch Yahoo) oder zumindest angekündigt (AOL). Die Festplatten werden immer größer, der Benutzer setzt in immer umfangreicherem Maße den Computer ein und es entstehen ganz schlicht immer mehr Dateien. Da ist es nicht verwunderlich, dass sich der unermüdliche Websurfer auch am heimischen PC die wegweisende Ordnung einer Suchmaschine wünscht. Vor kurzem hörte ich von einem User, der sich darüber beschwerte, dass er binnen zwei Sekunden dank Google die Webwelt überblicken kann, doch am eigenen Computer Stunden mit der Suche nach einer Datei verbringt. Das muss nicht sein, dachten sich die oben genannten Suchmaschinenhersteller (und schon deutlich früher so manche kleinere Firma - aber offensichtlich ohne den Marketingerfolg von Google). Jetzt können wir also mithilfe von Google & Co. Ordnung in unsere Dateienbäume bringen. Doch die Desktop-Suchmaschinen sind meistens noch in der Betaphase und lassen wichtige Features vermissen. Und selbst bei reiferen Produkten wie der Copernic Desktop Search fehlt noch das eine oder andere Detail. Aber das muss nicht sein - schreiben Sie doch einfach selbst eine Suchmaschine! Auch wenn das so entstandene Produkt wohl nicht ganz mit den Profis mithalten kann, lehrreich ist die Arbeit daran allemal. Und auch nicht übermäßig anstrengend. Mit dem Lucene-Framework sind die Grundlagen schnell gelegt; gibt man dann noch einige weitere Open-Source-Zutaten wie Apache POI und PDF Box hinzu, so lassen sich damit schon recht ansehnliche Erfolge erzielen. Im Folgenden werde ich eine kurze Einführung in die Lucene-Programmierung anhand eines solchen Beispieles geben. Zusätzlich zu der hier besprochenen Textversion finden Sie auf der Heft-CD eine schönere Swing-Variante der Suchmaschine (Abb. 1). Obwohl dieser Artikel auch ohne Vorkenntnisse über Lucene lesbar und verständlich ist, sei auf die allgemeineren Lucene-Ressourcen verwiesen [1-4].

Volltextsuchmaschinen haben die Aufgabe, große Datenmengen bestehend aus unstrukturiertem Text zu indexieren, um die anschließende Suche darin nach Wörtern und Termen zu ermöglichen. Obwohl das Grundprinzip - Zerlegen eines oder mehrerer Texte in kleine Einheiten, so genannte Tokens, und anschließendes Abspeichern der Token-Dokument-Beziehung - einfach erscheint, so liegt viel Arbeit versteckt in Details wie Tokenisierung, Indexspeicherung, Anfrageanalyse oder effiziente Suche. All dies nimmt das Suchmaschinen-Framework Lucene aus dem Apache-Jakarta-Projekt [4] dem Entwickler ab. Mit Absicht nicht als vollwertige Suchmaschine, sondern als Framework realisiert, lässt sich Lucene flexibel auf die jeweiligen Gegebenheiten zuschneiden. Lucene stellt dem Entwickler also ausschließlich ein API zur Volltextsuche bereits (Abb. 2). Der Einsatz und das Zusammenspiel dieser Pakete werden in diesem Artikel am Beispiel einer Volltextsuche dargestellt.

Die zu erstellende Beispielanwendung soll als einfache Approximation einer Desktopsuche folgende Eigenschaften besitzen: Mehrere Verzeichnisse sollen rekursiv durchsucht (Crawling) und die darin enthaltenen Dokumente indexiert werden - vorerst wollen wir uns mit der Analyse von Text-, PDF-, Word-, Excel- und OpenOffice-Dokumenten begnügen. Der Index stellt den Inhalt dieser Dokumente in einer einfachen Suchmaske bereit. Für mehr Details, einen größere Dokumentauswahl und komplexere Indexänderungen sei auf unser Lucene-Buch [2] verwiesen. Der Ablauf der Suche lässt sich grob wie folgt aufteilen:

• Indexierung: Realisierung der einzelnen Elemente (Dokumente) des Suchraumes und eigentliche Indexierung
• Suche: Anfragebearbeitung, Nachschlagen im Index sowie Aufbereitung und Anzeige des Ergebnis

Indexierung

Die Indexierung dient der Aufbereitung des Suchraums und wird typischerweise zu Beginn und bei Änderungen des Suchraums durchgeführt. Anhand des erstellten Index kann dann die Volltextsuche, wie später beschrieben, effizient durchgeführt werden. Zunächst zum Begrifflichen: Ein Index mehrerer Dokumente bezeichnet im Allgemeinen eine Abpictureung von Elementen (Tokens oder Terme) dieser Dokumente auf eine Liste der Dokumente, in denen das jeweilige Token vorkommt. Unter der Indexierung versteht man die Generierung eines Index aus einem oder mehreren Texten (oder allgemeiner Dokumenten) (Abb. 3). Der Indexierungsprozess in Lucene benötigt die folgenden Grundkonzepte mit entsprechenden Java-Klassen:

• Dokument: Die von Lucene zu indexierenden Dokumente sind in der Klasse org.apache.lucene.document.Document abstrahiert. Ein Dokument kann hierbei alles von einer Buchseite über eine Text- oder HTML-Datei bis zu einem Datenbankeintrag umfassen.
• Feld: Ein Dokument besteht aus mehreren (benannten) Feldern (org.apache.lucene.document.Field), die auf Wunsch indexiert werden können. Diese Aufteilung ermöglicht eine feiner strukturierte Suche. Beispielsweise könnte man bei einem Word-Dokument neben dem eigentlichen Text als zusätzliche Felder Autor und Beschreibung indexieren.
• Textvorverarbeitung (Analyse): Der zu indexierende Text aus den Feldern der Dokumente wird nicht direkt in den Index geschrieben, sondern zunächst von einem so genannten Analyzer, einem Objekt vom Typ org.apache.lucene.analysis.Analyzer geparst. Dadurch wird der in den Index einzutragende Text vorverarbeitet - das kann von so trivialen Dingen wie Normalisierung auf Kleinbuchstaben über das Weglassen bestimmter trivialer Wörter bis hin zum Eintrag nur des Wortstammes reichen. Alle Suchanfragen werden dann auch vom entsprechenden Analyzer vorverarbeitet.
• Indexerstellung: Der eigentliche Index wird von der Klasse org.apache.lucene.index.IndexWriter geschrieben. Dazu muss man angegeben, wo der Index gespeichert werden soll - sei es direkt im Dateisystem, in einer Datenbank oder nur im Arbeitsspeicher - und welcher Analyzer verwendet werden soll. In den Index lassen sich dann mehrere Dokumente eintragen. Auch können mehrere Indexe zusammengefügt und optimiert werden.

Listing 1

1. String[] text = {"Indexierung mit Lucene", "Suche mit Lucene"};
2. String indexDir = "../MyIndex";
3. Analyzer analyzer = new StandardAnalyzer();
4. boolean create = true;
6. IndexWriter writer = new IndexWriter(indexDir, analyzer, create);
7. for (int i=0; i<text.length; i++) {
8. Document document = new Document();
9. document.add(Field.Text("textfeld", text[i]));
10. writer.addDocument(document);
11. }
12. writer.optimize();
13. writer.close();

Listing 1 zeigt exemplarisch die Indexierung eines kurzen Textes. Es wird zunächst ein IndexWriter-Objekt erstellt, das den Index im gegenwärtigen Verzeichnis neu erstellt und für die Textvorverarbeitung den von Lucene mitgelieferten StandardAnalyzer verwendet. Er zerlegt den Text in einzelne Tokens, wandelt diese in Kleinbuchstaben um und filtert dabei häufig vorkommende Begriffe (so genannte Stoppwörter) aus. Anschließend wird ein einziges Dokument mit nur einem Feld mit Namen textfeld und dem Inhalt der Variablen text in den Index eingetragen. Mit optimize() wird der Index vor dem Schließen optimiert, d.h., der Cache wird geleert und während der Indexierung entstandene Segmente werden zu einem Segment zusammengefügt. Das Schließen des IndexWriter-Objekts beendet die Indexerstellung.

Aufbereitung und Abstraktion des Suchraums

Lucene indexiert also keine Dateien, sondern abstrakte Dokumente. Ein Dokument ist per Definition eine Menge von Feldobjekten, nichts anderes als Name-Wert-Paare. Bei der Indexierung wird zu jedem zu parsenden Dokument (z.B. in Form einer Datei) eine Instanz von org.apache.lucene.document.Document erstellt und diese anschließend mit Feldern vom Typ org.apache.lucene.document.Field gefüllt. Diese Abstraktion der zu durchsuchenden Objekte in Dokumente, die wiederum in Felder aufgeteilt sind, ermöglicht es, Lucene in verschiedensten Anwendungen einzusetzen (siehe nebenstehenden Kasten). Das Konzept lässt sich leicht visualisieren, indem man sich unter den Dokumenten Zeilen in einer relationalen Datenbank vorstellt, deren einzelne Spalten den Feldern entsprechen.

Aufbau eines Dokumentes in Lucene

Ein Dokument besteht aus mehreren Feldern. In der Praxis muss man sich hierbei Gedanken machen, wie die zu indexierenden Dateien strukturiert sind und welche Daten unmittelbar im Index enthalten sein sollen. Diese Struktur wird in den Feldern durch verschiedene Attribute wiedergegeben. Beispielsweise besteht eine HTML-Seite (u.a.) aus den Feldern URL, Titel, Metadaten, Änderungsdatum und dem eigentlichen Inhalt. Ein anderes Beispiel ist eine E-Mail mit Absender, Empfänger, Betreff und dem eigentlichen Text. Ein sinnvolles Minimal-Dokument sollte zumindest Felder wie Dokumenten-ID (z.B. URL oder File-Name), Änderungsdatum und natürlich den Inhalt (Text) enthalten. Felder können drei verschiedene boolesche Attribute haben:

• indexed: Das Feld ist indexiert, d.h., es kann von Lucene durchsucht werden.
• tokenized: Ein Feld mit diesem Attribut wird vor der eigentlichen Indexierung durch den später auszuwählenden Analyzer tokenisiert, d.h. in Einzelbestandteile zerlegt und Teile herausgefiltert.
• stored: Der Feldinhalt wird im Index gespeichert, wenn dieses Flag gesetzt ist. Im Allgemeinen kann man aus einem indexierten Feld nicht notwendigerweise den gesamten Feldinhalt rekonstruieren - dieser wurde ja eventuell zerlegt und vom Analyzer geparst, sodass nicht nur die Wortreihenfolge nicht rekonstruierbar ist, sondern auch ganze Wörter fehlen können.

In unserem Beispiel sollen Dateien indexiert werden, daher werden alle Dokumente aus einem File erzeugt. In den Feldern werden neben Eigenschaften wie Dateiname, Endung (woraus der Einfachheit halber der Dateityp bestimmt wird) und Pfad im Feld contents der Dateiinhalt gespeichert (siehe Klasse de.instantsolutions.lucene.document.FileDocument im beiliegenden Sourcecode). Konkrete Implementierungen lesen den Inhalt direkt aus (Textdatei) oder extrahieren den Text abhängig vom Dateityp. Beispielsweise stellt das Paket PDF Box [5] bereits eine Lucene-Dokumentenimplementierung bereit. Hingegen benutzen wir für Excel-Dokumente das Jakarta-API POI [6]. Schließlich kann ein OpenOffice-Dokument durch entzippen und Parsen der darin enthaltenen XML-Dateien analysiert werden. Aus Platzgründen sei an den Quelltext der Beispielanwendung im Paket de.instantsolutions.lucene.document verwiesen.

Die Indexerstellung der Lucene Desktop Search lässt sich nun sehr leicht realisieren (Listing 2). FileIndexer liest Dateien aus dem zu übergebenden Verzeichnis (sowie Unterverzeichnissen), wandelt diese durch de.instantsolutions.lucene.document.DocumentFactory in Lucene-Dokumente um und fügt sie dem Index hinzu.

Listing 2
Erzeugung eines Lucene-Index durch die Klasse FileIndexer

1. import org.apache.lucene.analysis.standard.StandardAnalyzer;
2. import org.apache.lucene.index.IndexWriter;
3. // ...
5. public class FileIndexer {
6. private static Logger logger = Logger.getLogger(FileIndexer.class.getName());
7. private IndexWriter writer;
9. public void index(String indexname, String dirname) throws Exception {
10. logger.info("starting to index...");
11. writer = new IndexWriter(indexname, new StandardAnalyzer(), true);
12. indexFile(new File(dirname));
13. writer.optimize();
14. writer.close();
15. logger.info("indexing done.");
16. }
18. private void indexFile(File myFile) throws Exception {
19. if (myFile.isFile()) {
20. logger.info("Indexing file " + myFile.getName() + "...");
21. try {
22. writer.addDocument(DocumentFactory.
23. getDocument(myFile.getAbsolutePath()));
24. } catch (DocumentNotImplementedException ex) {
25. logger.info("no impl. for filetype " + myFile.getName());
26. }
27. } else {
28. logger.info("Searching directory " + myFile.getName());
29. File[] files = myFile.listFiles();
30. for (int i = 0; i < files.length; i++)
31. indexFile(files[i]);
32. }
33. }
35. public static void main(String[] args) throws Exception {
36. (new FileIndexer()).index("index", args[0]);
37. }
38. }

Suche

Nachdem der Index nun erstellt worden ist, kann er durchsucht werden. Ein schematischer Überblick über das Zusammenwirken des Lucene API bei der Suche ist in Abpictureung 4 gegeben. Im Folgenden werden wir kurz auf die Schritte Anfrage, Suche und Anzeige eingehen.

Die Suche geschieht in Lucene mittels spezieller Anfragen (Queries), die von Lucene aus Strings geparst oder direkt über das API zusammengestellt werden können. Die an sich schon sehr mächtige Abfragesprache wurde in der letzten Lucene-Version (1.4.3) noch mal deutlich erweitert und enthält jetzt unter anderem Unterstützung für Boosting, Proximity, Fuzzy und Span Queries - mehr Details unter [2] [3]. In der Praxis ist vor allem die Formulierung solcher Abfragen in Strings von Interesse, daher wollen wir uns darauf beschränken.

Eine Anfrage in Lucene besteht aus Termen (einfachen Wörter) und Phrasen (Sequenzen von Termen), die durch logische Operatoren verbunden sind. Zusätzlich kann man die Suche auf bestimmte Felder durch Voranstellen von feldname: einschränken. Beispielsweise liefert xml AND path:de AND modified:[14.1.2005 TO 15.1.2005] Dokumente, die im beim Parsen anzugebenden Hauptfeld xml enthalten, im Pfad de liegen und die zwischen 14. und 15. Januar verändert wurden. Die Anfrage nach "Acrobat Reader" AND "test document"~2 liefert hingegen Dokumente, die die Phrase Acrobat Reader direkt enthalten und die Phrase test document im Abstand 2, d.h., es kann ein Wort dazwischen liegen.

Eine Anfrage wird mit der Klasse org.apache.lucene.queryParser.QueryParser geparst: Query query = QueryParser.parse(line, "contents", new StandardAnalyzer());. Dazu muss man neben dem zu parsenden String den Standardfeldnamen (in unserem Fall contents) sowie den beim Indexieren verwendeten Analyzer übergeben. Letzteres ist notwendig, um die gleiche Vorverarbeitung sowohl beim Indexieren als auch beim Anfrageerstellen zu benutzen - nur so erhält man vergleichbare Tokens. Die erzeugte Abfrage kann nun zum Durchsuchen des Indexes benutzt werden. Dazu wird zu Anfang durch Searcher searcher = new IndexSearcher("index"); eine Instanz der Hauptsuchklasse org.apache.lucene.search.IndexSearcher erzeugt - in unserem Fall durch Übergabe des Verzeichnisses, in dem der vorher erzeugte Index gespeichert wurde. Es sei darauf hingewiesen, dass der Index vorher geschlossen sein muss, d.h., dass beispielsweise nicht zugleich auch mittels eines IndexWriter auf ihn zugegriffen werden darf. Für Indexaktualisierungen schlägt die Lucene-Dokumentation folgenden Ausweg vor: Sie sollte in einem zweiten parallelen Index geschehen und nach der Aktualisierung sollte dann auf den neuen Index umgeschaltet werden. Da Suchanfragen normalerweise nur kurze Lebenszeiten haben, können alte Anfragen beim Umschalten auf den neuen Index gelöscht werden. Erweiterungen des Searcher wie beispielsweise das Durchsuchen mehrerer Indexe (mittels MultiSearcher), Remote Searching (neu seit Lucene 1.3, siehe Klasse RemoteSearchable) oder das Nachfiltern der Resultate (durch Klassen abgeleitet von Filter) sind möglich, werden hier aber nicht benötigt.

Benutzt wird der erzeugte Searcher nun ganz einfach durch den Aufruf Hits hits = searcher.search(query); mit der oben erstellten Abfrage query. Zurück erhält man ein Objekt vom Typ org.apache.lucene.search.Hits, das im Wesentlichen eine Liste der gefundenen Dokumente zusammen mit deren Score (Relevanzbeurteilung von Treffern bei der Suche) enthält. Die darunter liegenden Dokumente bekommt man dann durch

1. int i=0;
2. Document doc = hits.doc(i);

Aus dem zurückerhaltenen Dokument kann man die beim Indexieren angelegten Felder auslesen - beispielsweise über den/die Dateinamen/URL auf die unterliegende Datei zugreifen. Mit hits.score(i) erhält man die Score des Dokumentes bei der Suche - außerdem ist die Liste schon nach absteigender Score geordnet.

Suche im Desktop-Search-Beispiel

Für den visuellen Teil unserer Beispielanwendung soll die Ergebnispräsentation noch etwas schöner ausfallen - ähnlich wie bei Google soll als Vorschau ein Ausschnitt des Textumfeldes um die Ergebnisse angezeigt werden, worin zusätzlich die Ergebnisse farblich hervorgehoben sind. Dieses Highlighting ist in Lucene selbst nicht integriert, aber in der Lucene Sandbox - die Lucene-relevanten Erweiterungen und Projekte in verschiedenen Betastadien enthält - wird man schnell fündig. Das ursprünglich von Mark Harwood entwickelte Paket org.apache.lucene.search.highlight unterstützt diese Funktion, indem man zunächst ein Objekt vom Typ Highlighter erzeugt. Im Konstruktor übergibt man einen Formatter, der nichts anderes macht als die gefundenen Terme nach Benutzerwunsch hervorzuheben, sowie einen QueryScorer, der die Bewertung der Textfragmente entsprechend der übergebenen Abfrage query durchführt. Diesen Highlighter kann man nun auf den Inhalt des Dokumentes anwenden, um die gewünschten Textpassagen hervorzuheben. In Listing 2 geschieht das mithilfe des SpanGradientFormatter, der gefundene Terme mit HTML-Tags farbkodiert.
Im Übrigen kapselt die Klasse SearchIterator aus Listing 3 die Suche durch Implementierung des Iterator Interface (ohne Templates um abwärts kompatibel zu bleiben). Sie liefert einen Iterator über eine Liste von gekapselten Lucene-Dokumenten zusammen mit hervorgehobenem Text und Position in der Trefferliste zurück. Benutzt wird sie einfach durch

1. for (Iterator it = new SearchIterator(querystring, searcher); it.hasNext();)
2. System.out.println(it.next());

wobei querystring den Anfragentext und searcher den IndexSearcher enthalten.

Listing 3
Suche mit Ergebnishervorhebung in der Klasse SearchIterator

1. //...
2. public class SearchIterator implements Iterator {
3. public static String FIELD_NAME = "contents";
4. public static int NUM_HIGHLIGHTS = 5;
5. private Analyzer analyzer = new StandardAnalyzer();
6. private Hits hits;
7. private int hitpos;
8. private Highlighter highlighter;
10. public SearchIterator(String querystring, Searcher searcher)
11. throws IOException, ParseException {
12. Query query = QueryParser.parse(querystring, FIELD_NAME, analyzer);
13. query = searcher.rewrite(query); //required to expand search terms
14. hits = searcher.search(query);
15. hitpos = 0;
16. highlighter = new Highlighter(
17. new SpanGradientFormatter(1, "#000000" ,"#0000FF" , null, null),
18. new QueryScorer(query));
19. }
21. public boolean hasNext() {
22. return hitpos < hits.length();
23. }
25. public Object next() {
26. try {
27. Document doc = hits.doc(hitpos);
28. String text = doc.get(FIELD_NAME);
29. TokenStream tokenStream = analyzer.tokenStream(
30. FIELD_NAME, new StringReader(text));
31. String result = highlighter.getBestFragments(
32. tokenStream, text, NUM_HIGHLIGHTS, "<br>...<br>");
33. return new ResultDocument(doc, result, hitpos++);
34. } catch (IOException e) {
35. throw new RuntimeException(e); // no need to continue
36. }
37. }
39. public void remove() {
40. }
42. }

Zusammenfassung

Lucene bietet ein mächtiges API zur Volltextindexierung und Suche, die in Puncto Vielfalt leicht mit kommerziellen Mitbewerbern mithalten kann. In diesem Artikel wurden die Grundzüge des Lucene API an einem einfachen Beispiel dargestellt. Man sieht, dass die Integration der Lucene-Suchtechnologie in eigene Projekte leicht möglich (im Gegensatz zu den unflexibleren Anwendungslösungen) sowie technisch einfach realisierbar ist. Die entwickelte Desktop Search Engine ist tatsächlich einsetzbar, wenngleich noch ausbaufähig. Dennoch haben wir den Grundstein gelegt. Und in der Tat lässt sich Lucene für Desktopsuchen einsetzen, wie von kommerziellen Anbietern wie beispielsweise Aduna mit ihrer visuellen Suchmaschine AutoFocus [7] vorgemacht. Dass Suchmaschinen tatsächlich ein spannendes Thema sind, zeigt nicht zuletzt das große Feedback, dass Kevin Burton in seinem Blog Ende Oktober 2004 erhielt [8]. Er hat eine Desktop Search Engine vorgeschlagen - Lucene-basiert.
Dr. Fabian Theis (fabian.theis@instant-solutions.de) habilitiert sich gerade an der Universität Regensburg im Fach Biophysik. Daneben ist er als IT-Berater für webbasierte Technologien in seiner Firma Instant Solutions tätig. Neben verschiedenen Artikeln und Büchern hat er zusammen mit Manfred Hardt das im Software & Support-Verlag erschienene Buch Suchmaschinen entwickeln mit Apache Lucene verfasst.

Links und Literatur
[1] Manfred Hardt: Wo war denn noch gleich ...? Suchmaschinen entwickeln mit Java und Lucene, in Java Magazin 8.2002
[2] Manfred Hardt, Fabian Theis: Suchmaschinen entwickeln mit Apache Lucene, Software & Support Verlag, 2004
[3] Manfred Hardt: Auf ein Neues. Suchmaschinen entwickeln mit Java und Apache Lucene, in Java Magazin 2.2005
[4] Lucene: jakarta.apache.org/lucene/
[5] PDF Box: www.pdfbox.org
[6] POI: jakarta.apache.org/poi/
[7] Aduna AutoFocus: aduna.biz/products/autofocus/
[8] Kevin Burtons Blog: www.peerfear.org/rss/permalink/2004/10/28/LotsOfInterestInLuceneDesktop/