Indexierung mittels invertierter Dateien

Zunächst sollte man definieren, was genau mit einer invertierten Datei gemeint ist. Eine invertierte Datei enthält für jeden Term im Lexikon einen Eintrag, der eine Liste von Verweisen zu allen Vorkommen dieses Terms in der Dokumentensammlung speichert. Jeder Verweis ist im Prinzip eine Zahl, die jedem Dokument aus der Dokumentensammlung zuvor zugeordnet wurde. Dies ist vielleicht die natürlichste Art einer Indexerstellung, stark an den Index in einem Buch angelehnt.

Betrachten wir den Beispieltext aus Abbildung 1, wobei jede Zeile ein Dokument darstellt. Die entsprechende invertierte Datei ist in Abbildung 2 zu sehen, wobei nur ein case-folding stattfand, kein stemming wurde durchgeführt, und keine Stoppwörter wurden eliminiert.

Abbildung 1: Beispieltext; jede Zeile ist ein Dokument.

Abbildung 2: Invertierte Datei für den Text aus Abbildung 1.

Eine Anfrage nach einem Term kann beantwortet werden, indem man seinen Eintrag aus der invertierten Datei durchsucht, und jedes referrierende Dokument zurückliefert. Für konjunktive boolesche Anfragen der Form ``Term AND Term AND ...AND Term'' wird der Durchschnitt von den Einträgen der Terme aus der invertierten Datei gebildet. Für eine Disjunktion, wo der Operator OR ist, bildet man die Vereinigung, für die Negation (NOT) wird das Komplement benutzt. Die zu einem Term gehörenden Einträge werden in einer invertierten Datei normalerweise in aufsteigender Reihenfolge der Dokumentennummern gespeichert (beispielsweise für und $\langle 2, 5, 6\rangle$ anstatt $\langle 5, 2, 6\rangle$). Dadurch können die vorhin erwähnten Operationen (Durchschnitt, Vereinigung) in linearer Zeit durchgeführt werden. Als Beispiel, um die Dokumente zu erhalten, die ``zweite AND der'' enthalten, wird der Durchschnitt dieser beiden Listen ( $\langle 2, 5\rangle$ und $\langle 1, 2, 5\rangle$) gebildet. Als Ergebnis werden die gemeinsamen Dokumente geliefert -- in diesem Fall die in der Liste $\langle 2, 5\rangle$.

Die Granularität von einem Index ist die Genauigkeit, mit der ein Term innerhalb einer Dokumentensammlung lokalisiert werden kann. Ein grober Index wird vielleicht nur einen Textblock zurückliefern, wobei jeder Block mehrere Dokumente speichert. Ein Index mittlerer Granularität wird die Position der Terme bis auf die Dokumentenebene bestimmen können, ein feiner Index dagegen könnte bis auf Satz-, Wort- oder sogar Byte-Ebene hinunter. Grobe Indizes benötigen weniger Speicherplatz, doch der nach einer Anfrage zurückgelieferte Text ist größer, und muß noch nach dem Term durchsucht werden. Außerdem können Multiterm-Anfragen falsche Ergebnisse liefern, falls zwar jeder der Terme innerhalb eines Blocks ist, sie aber verschiedenen Dokumenten angehören.

Das andere Extrem, die Indexierung auf Wort-Ebene erlaubt Anfragen, die Proximität mit einbeziehen können. So kann beispielsweise eine Anfrage nach Formaldehyd-Synthese sehr schnell beantwortet werden, weil die beiden Begriffe als eine Phrase, und nicht als zwei unabhängige Wörter behandelt werden können. Auf Proximität kann geprüft werden, noch bevor ein Textfragment auf die Anfrage zurückgeliefert wird. Eine so präzise Information zur Lokalisierung hat auch ihren Preis: der Index wird etwa zwei- bis dreimal größer sein, als bei einer Indexierung auf Dokumentenebene. Die Gründe dafür sind, daß sowohl mehr Verweise zu speichern sind, als auch mehr Bits zur Kodierung der einzelnen Verweise benötigt werden.

Falls nicht ein signifikanter Anteil der Anfragen proximitätsbasiert ist, so setzt man üblicherweise die Granularität auf die Dokumentenebene. Proximitäts- und phrasenbasierte Anfragen können dann mit einer wenig langsameren Methode behandelt werden, die auf dem zurückgelieferten Text operiert.

Abbildung 3: Auf Wortebene Invertierte Datei.

Abbildung 3 zeigt den Index zum Beispieltext aus Abbildung 1, wobei die Notation $(x; y_1,y_2, \ldots)$ angibt, daß der gesuchte Term im Dokument $x$ als Wort an den Stellen $y_1,y_2, \ldots$ auftritt. Um Dokumente zu finden, die das und ist nebeneinander enthalten, werden die Listen dieser beiden Terme verglichen, und nur solche Paare von Einträgen werden zurückgeliefert, wo die Dokumentennummern übereinstimmen, und die Wortpositionen sich genau um eins unterscheiden. Das wäre hier nur im Dokument Nr. 1 der Fall. Der gröbere Index aus Abbildung 2 würde zunächst auch zwei falsche Antworten liefern (2 und 6). Erst ein nachträgliches Prüfen dieser Dokumente würde sie als Nichttreffer erkennen.

Man beachte, daß der Index größer geworden ist. Dafür gibt es zwei Gründe. Erstens muß ein Verweis mehr Informationen speichern -- sowohl die Position des Wortes innerhalb des Dokuments, als auch das Dokument selbst. Zweitens erscheinen mehrere Wörter mehr als einmal in einem Dokument. In einem Index wie in Abbildung 2 wird für solche Duplikate nur ein Verweis benötigt, dagegen ist bei einem Index auf Wortebene für jeden Term ein getrennter Eintrag zu verwalten.

Allgemein betrachtet speichern invertierte Dateien eine hierarchische Struktur von Adressen -- im Extremfall Wortnummer innerhalb eines Satzes, innerhalb eines Paragraphs, innerhalb eines Kapitels, innerhalb eines Bandes, innerhalb eines Dokuments. Die Position eines Terms kann deshalb als ein Vektor der Form $(d, b, k, p, s, w)$ interpretiert werden. Allerdings kann jede solche ``Koordinate'' weitere Listen von Adressen verwalten, wie auch in Abbildung 3 zu sehen. Aus diesem Grund wird in dieser hier vorliegenden Arbeit angenommen, daß eine Indexierung immer auf der Dokumentenebene erfolgt. Tatsächlich kann ein ``Dokument'' auch als eine sehr kleine Einheit (wie Satz oder Vers) definiert werden, so daß Indexierung auf Wortebene nur ein Spezialfall ist, wo jedes Wort ein Dokument darstellt.

Unkomprimierte invertierte Dateien können einen beträchtlichen Bedarf an Speicher haben, und belegen 50 bis 75 Prozent vom Platz, den der zu invertierende Text selbst zur Speicherung braucht. Nehmen wir beispielsweise an, daß ein Wort in einem typischen deutschen Text sechs Buchstaben lang sei, und daß jedes Wort von ein bis zwei Trenn- oder Satzzeichen gefolgt wird. Kodiert man die Dokumentennummern als 32-Bit Zahlen, und angenommen es gibt keine Wortduplikate innerhalb der Dokumente, so gibt es vier Bytes an invertierten Dateieinträgen für acht Bytes Text. Wenn zusätzlich noch ein ``Wortnummer innerhalb des Dokuments''-Feld zu jedem Eintrag hinzukommt, so braucht der Index grob sechs Bytes für acht Bytes an Text.

Abbildung 4 zeigt die Parameter einiger typischen Dokumentensammlungen: TREC, GNUbib und die Bibel. TREC steht für Text REtrieval Conference, und ist eine sehr große Dokumentensammlung, die von mehreren Forschergruppen für vergleichende Information Retrieval Experimente hergenommen wird. GNUbib enthält Verweise auf verschiedene Veröffentlichungen, wie Zeitschriftenartikel oder Bücher, aus dem Bereich der Informatik und der Datenverarbeitung allgemein.

Abbildung 4: Parameter einiger Dokumentensammlungen.

Für einen Text bestehend aus $N$ Dokumenten, und für einen Index, der $f$ Dokument-Wort-Paare enthält, benötigt man $f\cdot \lceil \log N \rceil$ Bits¹ zur Speicherung, angenommen die $f$'s werden mit der minimal notwendigen Anzahl an Bits kodiert. Wenn wir bei der TREC-Kollektion 20 Bits für die Darstellung der Dokumentennummern benutzen, ergibt das eine invertierte Datei von 324 Mbytes. Obwohl dies schon im Vergleich mit der üblichen 32-Bit Darstellung von Zahlen eine sparsamere Variante ist, belegt der Index immer noch einen merklichen Anteil. Für die selbe Kollektion, aber mit 29 Bits kodiert um eine Indexierung auf Wortebene zu erreichen, benötigt die invertierte Datei etwa 1.200 Mbytes.