Sortierbasierte Inversion

Die Hauptprobleme der Techniken aus Abbildung 9 und 10 sind, daß sie sehr viel Speicher benötigen, und daß der Zugriff auf die Daten im Prinzip in zufälliger Reihenfolge erfolgt, so daß keine sinnvolle Abbildung der Daten vom Speicher auf Platte gemacht werden kann. Bei solchen Datenmengen ist es im allgemeinen unmöglich eine Indexierung durchzuführen, ohne dabei auf Plattenspeicher zurückzugreifen. Deshalb sollte man generell versuchen, nur auf sequentiellen Dateien zu operieren, was natürlich eine Änderung der Algorithmen impliziert.

Abbildung 13: Sortierbasierter Inversionsalgorithmus.

Diese Überlegungen führen zu einem sortierbasierten Algorithmus, der in Abbildung 13 dargestellt ist. Er funktioniert folgendermaßen: Zuerst wird der Text gelesen, seine Indexterme werden ermittelt und in eine temporäre Datei geschrieben. Die temporäre Datei speichert ein $\langle t, d, f_{d, t}\rangle$-Tripel für jede Kombination von einem Term $t$ und einem Dokument $d$, ermittelt für die gesamte Dokumentensammlung. Die invertierte Datei wird anschließend durch die Sortierung dieser Tripel (aufsteigend nach $t$) erstellt, indem die sortierte Liste sequentiell gelesen wird. Der verwendete Sortieralgorithmus ist typischerweise Mergesort⁶.

In der Anfangsphase der Sortierung werden aus der temporären Datei blockweise $k$ Einträge in den Speicher gelesen, wobei $k$ die maximale Anzahl von Einträgen ist, die gleichzeitig im Speicher gehalten werden können. Diese Einträge haben alle dieselbe Größe, typischerweise 10 Bytes, 4 für die Termnummer, 4 für die Dokumentennummer, und 2 für die Speicherung der Häufigkeit eines Terms in einem Dokument. Angenommen 100 Mbytes an Hauptspeicher sind für diesen Zweck verfügbar, so könnte man $k$ auf 10.000.000 setzen. Jeder so gelesene Block wird aufsteigend sortiert, wobei man die Termnummer $t$ als Primärschlüssel, und die Dokumentennummer $d$ als Sekundärschlüssel hernimmt. Ein interner Sortieralgorithmus wie Quicksort sollte bei diesem Schritt benutzt werden. Der Block wird dann als ein sortierter Lauf in die temporäre Datei zurückgeschrieben. Es verbleibt nur noch die Aufgabe, diese sortierten Läufe so zusammenzufügen (zu mergen), daß am Ende eine einzige sortierte Datei vorliegt.

Dies erreicht man dadurch, daß man der Reihe nach alle Läufe durchgeht, und den ersten mit dem zweiten zusammenfügt, den dritten mit dem vierten, usw., bis alle Läufe einmal behandelt wurden. Man wiederholt solange, bis nur ein einziger (sortierter) Lauf übrigbleibt. Jeder solche Prozeß des Zusammenfügens halbiert die Anzahl der Läufe in der temporären Datei, und verdoppelt ihre Länge. Wenn es am Anfang $L$ Läufe gibt, dann verbleibt nach $\lceil \log L\rceil$ Phasen⁷ ein einziger Lauf, und die Datei ist sortiert. Dies ist die Standardmethode für eine ``externe Sortierung''; maximale Läufe für die interne Sortierung werden angestrebt, um sie dann in einer Folge von linearen Phasen zusammenfügen zu können.

Die Sortierung der temporären Datei ergibt die gewünschte Reihenfolge für die invertierte Datei. Die Einträge sind aufsteigend nach $t$, und bei gleichem $t$-Wert aufsteigend nach $d$ sortiert. Der letzte Schritt der Invertierung besteht nun darin, die temporäre Datei zu lesen, und daraus die (komprimierte) invertierte Datei zu erzeugen. Die temporäre Datei kann anschließend gelöscht werden. Abbildung 14 zeigt das Wörterbuch und die temporäre Datei, die bei diesem Algorithmus erzeugt werden würde.

Abbildung 14: Sortierbasierte Inversion vom Text aus Abblidung 1.

In diesem Beispiel wurden die Terme nicht wie in den Beispielen zuvor in alphabetischer Reihenfolge mit Nummern versehen, sondern in der Reihenfolge ihres ersten Auftretens in der Dokumentensammlung. Demzufolge werden die Einträge in der resultierenden invertierten Datei in einer anderen Reihenfolge auftauchen, als dies in den Abbildungen 8 und 11 gezeigt wurde. Dies hat keinen Einfluß auf die nachfogende Benutzung der invertierten Datei, ist aber äußerst praktisch, wie wir es später noch sehen werden.

Wie lange braucht nun dieser Algorithmus, um unsere hypotetische Dokumentensammlung zu invertieren? Wie bei den beiden vorherigen Methoden muß der gesamte Text gelesen werden, seine Indexterme müssen ermittelt und in die Datenstruktur eingetragen werden. Dieser Vorgang dauert wie vorhin etwa 2 Stunden. Während dieser Phase wird auch die temporäre Datei geschrieben, die einige hundert Millionen 10-Byte-Einträge enthält. Diese wenige Gbytes an Daten können auf sequentielle Weise in etwa 10 Minuten geschrieben werden.

Als Nächstes muß die temporäre Datei sortiert werden. Wenn für diesen Zweck etwa 100 Mbytes an Hauptspeicher verfügbar sind, so wird $k$ auf 10.000.000 gesetzt, und bei beispielsweise 400 Einträgen pro Term 40 Blöcke à 10.000.000 Bytes sind zu sortieren. Um einen solchen Block zu sortieren benötigt Quicksort etwa eine Minute. Weil während der internen Sortierung die temporäre Datei auch einmal gelesen und geschrieben werden muß, dauert dieser Vorgang eine Stunde.

Zum Schluß findet das Zusammenfügen der sortierten Läufe statt, wobei hierfür $\lceil \log 40\rceil = 6$ Durchgänge benötigt werden. Bei jedem Durchgang wird die temporäre Datei sowohl komplett gelesen als auch geschrieben, was weitere zwei Stunden in Anspruch nimmt. Strenggenommen müsste man hier auch die Rechenzeit für die Vergleiche (ein Vergleich pro $\langle t, d, f_{d, t}\rangle$-Tripel) berechnen, doch dies erfolgt einige Größenordnungen schneller als jeder Plattenzugriff. Die externe Sortierung der temporären Datei dauert somit etwa drei Stunden.

Um die invertierte Datei zu erzeugen, muß die temporäre Datei erneut gelesen, gegebenenfalls komprimiert, und anschließend wieder geschrieben werden, was in höchstens einer Stunde gemacht werden kann.

Die komplette Inversion ist also mit dieser Methode unter sieben Stunden zu bewerkstelligen, falls etwa 100 Mbytes an Hauptspeicher für diesen Zweck zur Vefügung stehen. Doch ein weiterer Aspekt muß ebenfalls berücksichtigt werden, und zwar der benötigte Sekundärspeicher. Leider benötigt der externe Sortieralgorithmus immer zwei Kopien der Daten zu einem gegebenen Zeitpunkt. Bei der internen Sortierung könnte man noch sparen, indem man die sortierten Läufe ab der selben Position in die selbe Datei zurückschreibt. Doch betrachten wir beispielsweise die Situation, wo die letzten beiden Läufe zu einem einzigen sortierten Lauf zusammengefügt werden. Mitten in diesem Prozeß ist es unmöglich die resultierende Datei sequentiell in die ursprügliche zurückzuschreiben, weil man ja Teile überschreiben könnte, die noch nicht abgearbeitet wurden.

Bei unserem Beispiel, wo die temporäre Datei etwa 4 Gbytes groß wird, müssen wir zu dem soeben geschilderten Zeitpunkt mit insgesamt 8 Gbytes an Daten rechnen. Das ist 60 Prozent mehr, als unsere ursprüngliche Dokumentensammlung. Nach dem heutigen Stand der Technik, wo Festplatten mit 40 Gbytes Kapazität selbstverständlich sind, ist dieser zusätzliche Speicherbedarf noch im erträglichen Rahmen. Man muß jedoch bedenken, daß sich zwar die Speicherkapazität moderner Platten rasend vergrößert, ihre Zugriffszeiten und Transferraten jedoch nur verhältnismäßig wenig besser werden.

Und weil bei der sortierbasierten Inversion Plattenzugriffe doch einen beträchtlichen Anteil der Gesamtbearbeitungszeit betragen, müssen Wege gefunden werden, um diese zu minimieren, es besteht also durchaus Verbesserungsbedarf.