Speicherbasierte Inversion

Die Implementierung eines generischen Querverweisgenerators ist eine Standardaufgabe, die jeder Informatikstudent während seines Studiums implementiert haben sollte. In Wirklichkeit ist ein Querverweis nur ein anderer Name für einen invertierten Index, in dem jeder Term aus irgendeinem Dokument (beispielsweise Schlüsselwörter in einem Sourcecode) alphabetisch aufgelistet ist, zusammen mit einer Liste von Zeilennummern, in denen er auftritt. Die Lösung für eine solche Aufgabe ist üblicherweise eine dynamische Datenstruktur, wie eine Hashtabelle oder ein binärer Suchbaum, wo die Terme der Dokumentensammlung gespeichert werden, versehen mit einer verketteten Liste, die Verweise auf die enthaltenden Dokumente speichern. Nach der Abarbeitung aller Dokumente wird die Datenstruktur durchlaufen, und eine Liste aller Terme wird zusammen mit den entsprechenden Zeilennummern der Dokumente in eine Datei geschrieben. Dieser Prozeß ist in Abbildung 10 ausführlicher beschrieben, die Datenstruktur nach Abschluß der ersten Phase des Algorithmus ist für unseren Beispieltext in Abbildung 11 dargestellt.

Abbildung 10: Speicherbasierter Inversionsalgorithmus.

Abbildung 11: Datenstruktur der invertierten Datei für den Beispieltext.

Die Terme sind hier in der Datenstruktur zwar alphabetisch geordnet, doch dies ist nicht immer der Fall. Verwendet man als Datenstruktur eine Hashtabelle, so müssen die Terme sortiert werden, bevor sie in die invertierte Datei geschrieben werden⁵. Verwendet man einen binären Suchbaum für die Speicherung, so können die Terme bei geeigneter Traversierung des Baumes gleich in sortierter Reihenfolge gewonnen werden. Im Prinzip kann jede dynamische Datenstruktur verwendet werden, doch eine Hashtabelle ist in vielerlei Hinsicht (Geschwindigkeit, Speicherbedarf) die bessere Wahl.

Um die Effizienz verschiedener Algorithmen besser beurteilen zu können, wäre es nützlich, die Kosten für die Invertierung einer typischen Datenmenge als Referenzpunkt zu haben. Abbildung 12 beschreibt eine hypotetische Dokumentensammlung von 5 Gbytes bestehend aus 5 Millionen Dokumenten. Die Tabelle enthält auch die Ausführungszeiten für eine Reihe von Operationen, die bei einer Indexerstellung auftreten, so daß die insgesamt benötigte Zeit ermittelt werden kann. Obwohl die Daten nicht auf einen bestimmten Rechnertyp basierend angegeben wurden, liefern sie eine gute Basis für den Vergleich von Algorithmen. Auch wenn diese Daten in absehbarer Zeit veraltet sein mögen, sind sie trotzdem in der Lage, die relativen Kosten für verschiedene Operationen anzudeuten.

Abbildung: Typische Größen und Ausführungszeiten.

Betrachten wir nun die Kosten für den Algorithmus aus Abbildung 10. Bei einer Transferrate von 10 Mbytes pro Sekunde dauert es etwa zehn Minuten, um den Text von 5 Gbytes sequentiell zu lesen. Parsing und Stemming um Indexterme zu erzeugen, bzw. das Suchen nach diesen Termen in der Datenstruktur benötigen viel mehr Zeit, über zwei Stunden bei 10$\mu s$ per Wort. In der zweiten Phase muß jede Liste durchlaufen werden, so daß der entsprechende Eintrag erzeugt und in die invertierte Datei geschrieben werden kann. Dies dauert schätzungsweise eine halbe Stunde. Man kann also davon ausgehen, daß die Invertierung in knapp drei Stunden gemacht werden kann. Das ist sicherlich nicht viel, bedenkt man daß die Dokumentensammlung 5 Gbytes groß ist. Bei der Bibel wäre diese Berechnung in unter einer Minute fertig.

Doch es ist ein weiterer wichtiger Aspekt zu berücksichtigen, nämlich der vom Algorithmus benötigte Speicherplatz. Jeder Knoten in der Liste der zu einem Term gehörenden Dokumentenreferenzen benötigt mindestens zehn Bytes: vier für die Dokumentennummer $d$, vier für den ``next''-Pointer in der verketteten Liste, und zwei oder mehr für die Zählvariable der Häufigkeit $f_{d, t}$. Für eine kleine Sammlung ist dies sicherlich nicht viel, doch bei einer Million verschiedener Terme, und bei einigen hundert Einträgen pro Term (durchschnittlich 400 in unserer hypotetischen Sammlung), braucht man für die Speicherung der Knoten einige Gbytes (4 in userem Fall) an Hauptspeicher. Man könnte zwar argumentieren, daß in naher Zukunft so viel Speicher jedem erschwinglich sein wird, doch die Dokumentensammlungen werden im gleichen Maße wachsen, der verfügbare Speicher wird wahrscheinlich nie den tatsächlichen Bedarf übersteigen.

Man könnte in Betracht ziehen, die verkettete Liste der Dokumentennummern auf der Festplatte zu lagern, anstatt sie im Speicher zu halten. Doch diese Idee erweist sich beim näheren Betrachten als nicht besonders gut. Die Folge von Plattenzugriffen während der ersten Phase wären alle sequentiell, die Erzeugung einer Datei mit den verketteten Listen ist daher unproblematisch. Jeder neue Knoten würde ans Ende der Datei angefügt werden, so daß die 4 Gbytes große Datei auf sequentielle Weise geschrieben wird, was vielleicht weitere zehn Minuten zu den vorherigen drei Stunden hinzukommen läßt.

Betrachten wir nun die zweite Phase, wo jede Liste durchlaufen werden muß. Die gespeicherten Knoten der Listen sind auf die gleich Weise in der erzeugten Datei verteilt, wie sie es im Text waren, so daß bei jedem Zugriff auf einen Knoten eine zufällige Suche in der Plattendatei erfolgen muß. Bei einer Zugriffszeit von $10~ms$ und bei einigen hundert Millionen Knoten würde die zweite Phase einige Millionen Sekunden dauern, was einigen Wochen Bearbeitungszeit entspräche.

Dies ist sicherlich eine Verbesserung im Vergleich zu den 126 Jahren des naiven Algorithmus, jedoch immer noch sehr langsam für praktische Zwecke. Der Algorithmus aus Abbildung 10 ist somit für unsere hypotetische Dokumentensammlung auch unbrauchbar, denn er benötigt entweder zu viel Hauptspeicher oder seine Ausführung dauert zu lange. Er eignet sich jedoch für kleinere Dokumentensammlungen hervorragend, so könnte beispielsweise die Bibel unter einer Minute und mit nur 10 Mbytes an Speicher invertiert werden.