Index-Dateiformate von Lucene

Lucene ist komplett in Java geschrieben.
Es gibt Bemühungen, Versionen von Lucene auch in anderen Programmiersprachen zu schreiben.
Um das möglich zu machen, ist es notwendig, eine sprachunabhängige Definition des Lucene-Indexformats zu formulieren.

Das Grundkonzept in Lucene besteht aus Index, Dokument, Feld und Ausdruck.

• 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.

Invertiertes Indizieren ("inverted index"):

• 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.

Indizes werden aus mehreren Sub-Indizes (Segmente) erstellt.

• 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.

Intern werden die zu indizierenden Dokumente durch eine Zahl, der Dokument-Nummer referenziert.

• 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.

Jedes Segment entält Folgendes:

• 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.

Alle Dateien (Dateien, in denen die Indexinformationen gespeichert werden) haben den gleichen Namen mit unterschiedlichen Erweiterungen.

Typischerweise werden alle diese Dateien im selben Verzeichnis gespeichert, obwohl das nicht zwingend erforderlich ist.

Folgende primitive Datentypen werden in diesen Dateien benutzt:

• 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

Es gibt eine Reihe von Stellen, in denen diese Dateiformate die maximale Anzahl der Ausdrücke und Dokumente auf eine 32-Bit große Zahl beschränken.

• 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.