[Quelle:  http://www.fh-wedel.de/~si/seminare/ws02/Ausarbeitung/e.lucene/index.html].

Lucene - Eine einfache Suchmaschine für Freitextsuche

Einführung in Lucene

Skalierbares, High-Performance Indexing

• über 200MB/Stunde auf einem Pentium II/266
• Erweitern des Index genau so schnell, wie das Erstellen eines neuen Index
• geringer RAM-Bedarf, nur 1 MB auf dem Heap
• Indexgröße ungefähr 30% des ursprünglichen Textes

Mächtige, akurate und effiziente Suchalgorithmen

• Gewichtetes Suchen, die besten Resultate zuerst
• Suche mit booleschen Operatoren und Phrasen
• Feldsuche, z. B. Dokumentname und Inhalte
• Datum-gewichtete Suche

Einfache API erlaubt es Entwicklern,

• neue Dokumenttypen miteinzubeziehen
• für weitere Sprachen zu lokalisieren
• neue Benutzerinterfaces zu entwickeln

Plattformübergreifende Lösung

• 100% in Java geschrieben

Die Standard-Suchsyntax von Lucene

Index-Dateiformate von Lucene

• Ein Index enthält eine Folge von Dokumenten:
• Ein Dokument ist eine Folge von Feldern
• Ein Feld ist eine benannte Folge von Ausdrücken
• Ein Ausdruck ist eine Zeichenkette (String)

Ist der gleiche String in zwei veschiedenen Feldern, so sind das zwei Ausdrücke. Somit wird ein Ausdruck repräsentiert als ein String-Paar, Feldname und Feldinhalt.

• Ein Index speichert Statistiken über die Ausdrücke
• Der Index listet für einen Ausdruck die Dokumente, die es enthält, um die Suche effizienter zu machen.
• Werden also alle Vorkommen eines Ausdrucks gesucht, müssen nicht alle zu durchsuchende Dokumente einzeln durchsucht werden, sondern lediglich im Index die Statistiken des einen Ausdrucks ausgewertet werden.

Es gibt zwei Arten von Feldern:

• In dem Fall, in dem der Text eines Feldes buchstäblich gespeichert wird, können Felder nicht-invertiert "gespeichert" werden. Felder, die invertiert sind, nennt man "indiziert". Ein Feld kann beides sein, gespeichert und indiziert.
• Der Text eines Fledes kann zum Indizieren in Ausdrücke aufgeteilt (tokenized) werden, oder der Text eines Feldes wird buchstäblich als ein Ausdruck indiziert werden. Die meisten Felder sind "tokenized", aber für bestimmte Bezeichnerfelder ist es besser, buchstäblich indiziert zu werden.

• Jedes Segment ist ein vollständig unabhängiger Index, der separat durchsucht werden kann.

Indizes entstehen aus:

• Kreieren neuer Segmente durch neu hinzugefügte Dokumente.
• Benutzung bestehender Segmente.

Bei einer Suche können mehrere Segmente und / oder mehrere Indizes verwendet werden, jeder Index kann aus mehreren Segmenten entstanden sein.

• Das erste hinzuzufügende Dokument bekommt den Wert 0, alle anderen ein mehr als das letzte.

Dokumentnummern können sich ändern, daher ist es nicht ratsam, diese Nummern außerhalb von Lucene zu setzen:

• Die Nummern sind nur einmalig innerhalb eines Segments und müssen konvertiert werden, um in einem größeren Kontext benutzt werden zu können. Die Standardtechnik besteht darin, dass jedes Segment eine sogenannte base-number erhält, die aus der Anzahl der Werte des Segments resultiert. Wird nun eine segmentinterne Nummer in einen externen Wert umgewandelt, so wird zu der Nummer diese base-number addiert, bei der Rückkonvertierung entsprechend subtrahiert. Gibt es z.B. zwei Segmente mit jeweils 4 Dokumenten, so bekommt das erste Segment die base-number 0, das zweite 4. Dann bekommt Dokument 3 vom zweiten Segment den Wert 7.
• Werden Dokumente gelöscht, gibt es Lücken in der Nummerierung. Diese werden eventuell geschlossen, wenn die entsprechenden Segmente dem Index hinzugefügt werden. Gelöschte Dokumente werden weggelassen, wenn Segmente hinzugefügt werden. Ein neu hinzugefügtes Segment hat also keine Lücken in der Nummerierung.

• Feldnamen: die Feldnamen, die im Index benutzt werden.
• Gespeicherte Feldwerte. Das beinhaltet für jedes Dokument eine Liste von Attribut-Wertpaaren, wobei die Attribute die Feldnamen sind. Diese werden für Hilfsinformationen, wie Titel, URL, o. ä benötigt. Die Menge der gespeicherten Felder wird bei einer Suchanfrage zurückgeliefert, auf die Dokumente wird mit der Dokumentnummer zugegriffen
• Liste der Ausdrücke. Die Liste enthält alle Ausdrücke aller Index-Felder aller Dokumente. Die Liste entält außerdem die Anzahl aller Dokumente, die den Ausdruck enthalten und gibt die Häufigkeit aus, in der der Ausdruck in allen und in diesem Dokument vorkommt, sowie die Positionen in den Dokumenten.
• Normalisierungsfaktoren. Für jedes Feld wird ein Wert gespeichert, der in die Auswertung für Treffer auf diesem Feld multipliziert wird.
• Gelöschte Dokumente. Eine optionale Datei, die angibt, welche Dokumente gelöscht wurden.

• Byte (8-bit): Auf Dateien wird zugegriffen als Sequenzen von Bytes. Alle anderen Formate sind als Sequenzen von Bytes definiert.
• UInt32: 4-Byte langes vorzeichenloses Integer, höchstwertiges Bit zuerst.
  UInt32 --> <Byte>^4
• UInt64: 8-Byte langes vorzeichenloses Integer, höchstwertiges Bit zuerst.
  UInt64 --> <Byte>^8
• VInt: Variables Längenformat für positive Integers, wobei das höchstwertige Bit angibt, ob ein weiteres Byte zu lesen ist. Die jeweils 7 niederwerigeren Bits ergeben den tatsächlichen Wert. So können Werte von 0 bis 127 mit einem Byte, von 128 bis 16383 mit zwei Bytes usw. dargestellt werden.
  

  VInt Encoding Beispiele:

  Wert	Erstes Byte	Zweites Byte	Drittes Byte
  0	00000000
  1	00000001
  2	00000010
  ...
  127	01111111
  128	10000000	00000001
  129	10000001	00000001
  130	10000010	00000001
  ...
  16.383	11111111	01111111
  16.383	11111111	01111111
  16.384	10000000	10000000	00000001
  16.385	10000001	10000000	00000001
  ...

  
  

• Chars: Zeichen nach UTF-8 Codierung.
• String: Lucene nutzt Strings durch VInts, die die Länge angeben und Chars, die die Zeichen darstellen.
  String --> VInt, Chars

Segmentdatei

Diese Datei speichert die aktiven Segmente des Index, Dateiname: "segments", listet jedes Segment beim Namen und enthält dessen Größe.
Segmente --> SegAnzahl, <SegName, SegGröße>^SegAnzahl
SegAnzahl, SegGröße --> UInt32 (SegGröße ist die Anzahl der Dokumente des Segments)
SegName --> String (Name, wie der Datei-Prefix aller Dateien des Segment-Index)

Blockierdateien

Bestimmte Dateien werden benutzt um anzuzeigen, dass ein anderer Prozess auf den Index zugreift.

• "commit.lock": Ein anderer Prozess greift auf die "segments"-Datei zu.
• "index.lock": Ein anderer Prozess fügt Dateien zum Index hinzu oder entfernt welche.

Löschdatei

Die Datei "deletable" gibt die Dateien an, die der Index nicht mehr benutzt, die aber nicht gelöscht werden konnten, da die Datei z. B. gerade geöffnet ist:
Löschdatei --> Anzahl, <Dateiname>^Anzahl.
Anzahl --> UInt32
Dateiname --> String

Dateien pro Segment

Von folgenden Dateien existiert eine pro Segment:

• Felddatei

  Feldnamen werden in der Datei mit der Endung .fnm gespeichert:
  FeldInfos (.fnm) --> FeldAnzahl, <FeldName, FeldBits>^FeldAnzahl.
FeldAnzahl --> VInt FeldName --> String FeldBits --> Byte (indiziert / nicht indiziert)
  
  

• Gespeicherte Felder

  Gespeicherte Felder werden durch zwei Dateien repräsentiert:
  
  Der Feldindex (.fdx), entält für jedes Dokument einen Zeiger auf seine Felddaten.
  FeldIndex (.fdx) --> <FeldWertePosition>^SegGröße
FeldWertePosition --> UInt64 (um die Felddaten eines bestimmten Dokuments in der Felddaten-Datei (s. u.) zu finden, feste Größe, daher schneller wahlfreier Zugriff Um die Felddaten eines bestimmten Dokuments in der Felddaten-Datei (s. u.) zu finden, feste Größe, daher schneller wahlfreier Zugriff.
  
  Die Felddaten (.fdt), enthält die Felder jedes Dokuments.
  FeldDaten (.fdt) --> <DokumentFeldDaten>^SegGröße
DokumentFeldDaten --> FeldAnzahl, <FeldNummer, Bits, Wert>FeldAnzahl
Anzahl --> VInt
Feldnummer --> VInt
Bits --> Byte (tokenized / nicht tokenized)
Wert --> String
  
  

• Liste der Ausdrücke

  Die Liste der Ausdrücke wird mit zwei Dateien gespeichert:
  
  Ausdruck-Informationen, .tis-Datei.
  AusdruckInfoDatei (.tis) --> AusdruckAnzahl, AusdruckInfos
AusdruckAnzahl --> UInt32
AusdruckInfos --> <AusdruckInfo>^AusdruckAnzahl
AusdruckInfo --> <Ausdruck, DokumentFrequenz, FrequenzDelta (Position in Frequenzdatei), DistanzDelta (Position in Distanzdatei)> Ausdruck --> <PrefixLänge (Anzahl gleicher Buchstaben wie vorheriger Ausdruck), Suffix (zusätzliche Zeichen), FeldNummer (.fdt-Datei)> Suffix --> String PrefixLänge, DokumentFrequenz, FrequenzDelta, DistanzDelta --> VInt
  
  Ausdruck-Informations-Index, .tii-Datei.
  Diese entält jeden 128. Eintrag der .tis-Datei und deren Positionen in der .tis-Datei und dient lediglich dazu, in den Speicher geladen zu werden und wahlfreien Zugriff auf die .tis-Datei zu ermöglichen.
  AusdruckInfoIndex (.tii) --> IndexAusdruckAnzahl, AusdruckIndizes
IndexAusdruckAnzahl --> UInt32
AusdruckIndizes --> <AusdruckInfo, IndexDelta (Position in der .tis-Datei)>^IndexAusdruckAnzahl
IndexDelta --> VInt
  
  

• Frequenzdatei

  Die Frequenzdatei entält eine Liste von Dokumenten, die die Ausdrücke enthalten und die Frequenz der Ausdrücke in dem jeweiligen Dokument.
  
  FrequenzDatei (.frq) --> <AusdruckFrequenzen>^AusdruckAnzahl
AusdruckFrequenzen --> <AusdruckFrequenz>^DokumentFrequenz
AusdruckFrequenz --> DokumentDelta, Frequenz?
DokumentDelta, Frequenz --> VInt DokumentDelta enthält die Dokumentnummer (Dokumentnummer * 2). Ist DokumentDelta ungerade, so ist die Frequenz 1, sonst wird sie durch das weitere VInt angegeben.
  
  

• Positionsdatei

  Die Positionsdatei enthält die Liste der Positionen, die die Ausdrücke in den Dokumenten haben.
  
  PositionsDatei (.prx) --> <AusdruckPositionen>^AusdruckAnzahl
AusdruckPositionen --> <Positionen>^DokumentFrequenz
Positionen --> <PositionsDelta (Differenz zwischen der aktuellen und der vorherigen Position im Dokument)>^Frequenz
PositionsDelta --> VInt
  
  

• Normalisierungsfaktoren

  Die .nrm-Datei enthält für jedes Dokument ein Byte, das den Multiplikationsfaktor für einen Treffer des Feldes entält:
  
  Narmalisierungsfaktoren (.nrm) --> <Byte>^SegmentGröße Jedes Byte kodiert einen Fließkommawert. Bits 0-2 enthalten eine 3-Bit Mantisse und Bits 3-8 einen 5-Bit Exponent.
  
  

• Gelöschte Dokumente

  Die .del-Datei ist optional und existiert nur, wenn ein Segment Streichungen entält:
  
  Streichungen (.del) --> ByteAnzahl, BitAnzahl, Bits (für jedes Dokument ein Bit) ByteGröße (Anzahl der Bytes in Bits), BitAnzahl --> UInt32 Bits --> <Byte>^ByteAnzahl

• heutzutage kein Problem, aber möglicherweise in Zukunft
• Diese Stellen müssen dann durch UInt64 oder besser VInt ersetzt werden.

Es gibt nur zwei Stellen, an denen Werte eine feste Maximalgröße haben müssen:

• Die FeldWertePosition (in der FeldIndexDatei, .fdx). Diese ist als UInt64 gesetzt und daher kein Problem.
• Die AusdruckAnzahl (AusdruckInfoDatei, .tis). Diese muss dann in UInt64 geändert werden.

An allen anderen Stellen können UInt32 ind VInt umgewandelt werden.

Lucene in der Praxis

Schauen wir uns zunächst einmal die Datei "IndexFiles.java" an, mit Hilfe derer der Index erstellt wird.

import org.apache.lucene.analysis.de.GermanAnalyzer;
import org.apache.lucene.index.IndexWriter;

import java.io.*;
import java.util.*;

public
class IndexFiles 
{
  public static
  void main(String[] args)
  {
    try
    {
      Date start = new Date();

      IndexWriter writer = new IndexWriter(Const.INDEX_DIR, new GermanAnalyzer(), true);
      indexDocs(writer, new File(args[0]));

      writer.optimize();
      writer.close();
    }
    catch (Exception e)
    {
      System.out.println(" caught a " + e.getClass() + "\n with message: " + e.getMessage());
    }
  }

  public static void indexDocs(IndexWriter writer, File file)
    throws Exception
  {
    if (file.isDirectory())
    {
      String[] files = file.list();
      for (int i = 0; i < files.length; i++)
      indexDocs(writer, new File(file, files[i]));
    } 
    else
    {
      System.out.println("hinzugefuegt: " + file);
      writer.addDocument(FileDocument.Document(file));
    }
  }
}
        

Zunächst wird eine Instanz von "IndexWriter" erstellt.

• Erstes Argument: Name des Verzeichnisses, in dem der Index erstellt wird.
• Zweites Argument: der entsprechende "Analyzer": dieser ist dafür zuständig, den Text zu analysieren und entsprechende Operationen zu unternehmen, wie etwa alles in Kleinschreibung umwandeln, oder unnütze Wörter entfernen, z. B. Artikel oder Konjunktionen. Da dieses sprachspezifisch ist, existieren verschiedene Analyzer. In diesem Fall wurde der deutsche gewählt, offiziell existieren momentan welche für Englisch und Deutsch.
• Drittes Argument: gibt an, ob ein neuer Index erstellt (true), oder zu einem bestehenden weitere Dokumente hinzugefügt werden sollen.

Dann wird "indexDocs(...)" aufgerufen:

• "indexDocs(...)" (weiter unten) durchläuft rekursiv die Verzeichnisse und Dateien.
• wurde eine Datei gefunden, wird diese mittels "addDocument(...)" dem "IndexWriter" hinzugefügt.

Dann die Datei "FileDocument.java"

import java.io.*;
import org.apache.lucene.document.*;

public
class FileDocument
{
  public static
  Document Document(File f)
    throws java.io.FileNotFoundException
  {
    Document doc = new Document();
    doc.add(Field.Text(Const.PATH_FIELD, f.getPath()));
    doc.add(Field.Keyword(Const.MOD_FIELD,
              DateField.timeToString(f.lastModified())));

    FileInputStream is = new FileInputStream(f);
    Reader reader = new BufferedReader(new InputStreamReader(is));
    doc.add(Field.Text(Const.DEF_FIELD, reader));

    return doc;
  }
}
        

• Diese erstellt ein Dokument für eine zu indizierende Datei.
• Zunächst wird das Feld "pfad", also der Pfad der Datei hinzugefügt.
• Dann wird das "geänderd-Datum" ausgelesen und hinzugefügt (Feld: geaendert).
• Dann wird der Dateiinhalt mit Hilfe eines "InputStreamReader" ausgelesen und dem Feld "inhalt" hinzugefügt.
• Das entstandene Dokument wird schließlich zurückgeliefert.

Schließlich die Datei "SearchFiles.java".

import java.io.*;

import org.apache.lucene.analysis.Analyzer;
import org.apache.lucene.analysis.de.GermanAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.search.*;
import org.apache.lucene.queryParser.QueryParser;

public
class SearchFiles
{
  public static
  void main(String[] args)
  {
    try
    {
      Searcher searcher = new IndexSearcher(Const.INDEX_DIR);
      Analyzer analyzer = new GermanAnalyzer();

      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      // einlesen
      boolean lineEnd=false;
      while (!lineEnd)
      {
        System.out.print("Suchbegriff eingeben (<Enter>, um zu verlassen): ");
        String line = in.readLine();

        if (line.length() == -1)
          lineEnd=true;
        else
        {
          Query query = QueryParser.parse(line, Const.DEF_FIELD, analyzer);
          System.out.println("Suchbegriff: " + query.toString(Const.DEF_FIELD));

          Hits hits = searcher.search(query);
          System.out.println(hits.length() + " Dokumente gefunden");

          final int HITS_PER_PAGE = 10;
          int end = hits.length();
          for (int i=0; i<end; i++)
          {
            Document doc = hits.doc(i);
            String path = doc.get(Const.PATH_FIELD);
            System.out.println(i + ". " + path);
          }
        }
      }
      searcher.close();

    }
    catch (Exception e)
    {
      System.out.println(" caught a " + e.getClass() + "\n with message: " + e.getMessage());
    }
  }
}
        

• Diese Klasse arbeitet mit einem "IndexSearcher" (durchsucht den Index), Achtung: richtiges Index-Verzeichnis angeben) zusammen, mit einem Analyzer, vorzugsweise der gleiche, wie in "IndexFiles" und einem "QueryParser".
• Im Konstruktor des "QueryParser" ("query") wird konstruiert, indem die Eingabe übergeben wird, der Analyzer, um eine Suchanfrage auf die gleiche Weise zu interpretieren, wie die Inhalte der indizierten Dokumente und der Name des Default-Feldes.
• Die Suchergebnisse werden zurückgeliefert in einer Sammlung von Dokumenten (Klasse "Hits"), die dann durchlaufen und angezeigt werden.

Pläne für die Zukunft

Links und Literaturverzeichnis