Algorithmen für invertierte Dateien

Wir haben bis jetzt gesehen, wie invertierte Dateien aussehen, welche typischen Einträge sie enthalten können, und wie sie komprimiert werden. Kommen wir nun zum eigentlichen Anliegen dieser Arbeit: Beschreibung von Algorithmen für die Erstellung von invertierten Dateien. Der Prozeß der Indexerstellung wird auch als die Inversion³ eines Textes bezeichnet. Man betrachte wieder den Beispieltext aus Abbildung 1. Jede Zeile (jedes Dokument) des Textes enthält einige Indexterme, und jeder Indexterm kommt in einigen dieser Zeilen vor. Dieser Zusammenhang kann mit Hilfe einer Häufigkeitsmatrix ausgedrückt werden, wobei jede Spalte einem Wort, und jede Zeile einem Dokument entspricht. Die Zahl an einer $[Zeile, Spalte]$-Position gibt an, wie oft das entsprechende Wort in dem entsprechenden Dokument vorkommt. Abbildung 7 zeigt die Häufigkeitsmatrix für den Text aus Abbildung 1 (aus Platzgründen wurden die Terme dritter, ein, ende und er nicht in die Matrix aufgenommen). Jedes Dokument wird dadurch in einer Zeile der Häufigkeitsmatrix zusammengefasst. Um einen Index zu erstellen, muß die Matrix transponiert --``invertiert''-- werden, so daß jetzt die Zeilen den Termen zugeordnete Nummern sind. Die transponierte Häufigkeitsmatrix ist in Abbildung 8 dargestellt. Anhand dieser transponierten Matrix kann anschließend einfach eine invertierte Datei erstellt werden.

Abbildung 7: Häufigkeitsmatrix zum Text aus Abbildung 1.

Abbildung 8: Transponierte Matrix aus Abbildung 7.

Ein Algorithmus zur Erstellung einer invertierten Datei könnte nun wie folgt aussehen: baue im Speicher eine Häufigkeitsmatrix Zeile für Zeile auf, indem die Dokumentensammlung in Dokumentenreihenfolge gelesen wird; schreibe dann diese Matrix Spalte für Spalte in Termreihenfolge auf Platte. Dieser Algorithmus wird in Abbildung 9 ausführlicher beschrieben.

Abbildung 9: Algorithmus zur Erstellung von invertierten Dateien.

Trotz der verlockenden Einfachheit dieses Algorithmus, ist die Erstellung von invertierten Dateien in der Realität jedoch viel komplizierter. Das Problem ist die Größe der Häufigkeitsmatrix. Angenommen, ein Index der Bibel müsste erstellt werden. Sie enthält in etwa 9000 verschiedene Terme und 31000 Dokumente. Wenn eine 4-Byte Integer-Zahl zur Speicherung eines Eintrags in der Häufigkeitsmatrix verwendet wird, so wird die Matrix $4 \times 9000 \times 31000$ Bytes an Hauptspeicher benötigen. Das ist knapp über ein Gigabyte, gerade noch verwaltbar auf einer größeren Workstation. Für die größere TREC-Kollektion ist die Größe der Matrix noch erschreckender: $4 \times 538000 \times 742000$ Bytes, oder etwa 1.4 Terabytes. Angenommen ein Byte würde für die Speicherung der Häufigkeitswerte $f[d, t]$ ausreichen (dies ist bei TREC nicht der Fall), so läge der Speicherbedarf immer noch bei 250 Mbytes bzw. 350 Gbytes, der Algorithmus wäre also trotzdem nicht realisierbar.

Man beachte, daß die Häufigkeiten benötigt werden, falls der Index auch für ranked queries benutzt werden soll. Falls nur boolesche Anfragen bedient werden müssen, so ist die Speicherung einer booleschen Matrix ausreichend, der Speicherbedarf reduziert sich auf 31 Mbytes bzw. 43 Gbytes. Man könnte zwar einen Rechner mit einem sehr großen virtuellen Speicher benutzen, und die Ein- und Auslagerung der Teile der Matrix dem Betriebssystem überlassen, dies hätte jedoch zur Folge, daß jeder Zugriff auf die Matrix bei Schritt 3(b) einen Seitenfehler auslösen würde. Eine Indexerstellung für die TREC-Kollektion würde $538000 \times 742000$ Seitenfehler erzeugen, und bei etwa 100 Plattenzugriffen pro Sekunde würde dieses Verfahren 126 Jahre⁴ dauern.

Aus diesen Gründen müssen Methoden für den Aufbau und für die Invertierung der Häufigkeitsmatrix betrachtet werden, die sparsamer mit dem Speicher umgehen. Solche Methoden werden nur wenig mit dem naiven Algorithmus aus Abbildung 9 gemeinsam haben.