Komprimierung der temporären Dateien

Die sortierbasierte Inversion wäre sicherlich noch attraktiver, wenn man die Größe der temporären Datei(en) reduzieren könnte. Wir haben in Abschnitt 4 bereits gesehen, daß auch relativ einfache Kodes, wie der $\gamma$-, oder $\delta$-Kode es ermöglichen, ein $\langle d, f_{d, t}\rangle$-Paar mit nur etwa einem Byte zu kodieren. Für die hypotetische Sammlung aus Abbildung 12 bedeutet das 400 Mbytes. Und weil die resultierende invertierte Datei dadurch um den Faktor sechs reduziert werden kann, müssten ähnliche Kompressionsraten auch für die $\langle t; d; f_{d,t}\rangle$-Tripel der temporären Datei erreicht erreicht werden können. Es sollte also möglich sein, mit nur 1.5 Gbytes an Plattenplatz auszukommen, anstatt der vorhin berechneten 8 Gbytes.

Nun aber zurück zu unserem ursprünglichen Vorhaben, zur Kompression der temporären Datei während einer sortierbasierten Inversion. Die temporäre Datei enthält Einträge der Form $\langle t; d; f_{d,t}\rangle$. Die Komprimierung der $d$- und $f_{d, t}$-Einträge wurde bereits vorgestellt, es muß also nur noch eine sparsame Methode zur Darstellung von $t$-Einträgen gefunden werden.

In jedem sortierten Lauf sind die $t$-Werte in aufsteigender Reihenfolge gespeichert, $t$ war ja der Primärschlüssel für die Sortierung dieser Einträge. Demzufolge könnte man auch hier eine Differenzkodierung anwenden. Man muß allerdings beachten, daß sortierte Läufe erst nach einer ersten internen Sortierphase zur Verfügung stehen, die erste ``Version'' der temporären Datei liegt nämlich unsortiert vor (linke Spalte der Tabelle aus Abbildung 14). Sie kann also mittels Differenzkodierung nicht komprimiert werden, und würde bei der hypotetischen Dokumentensammlung weiterhin 4 Gbytes an Plattenspeicher belegen. Man könnte dies jedoch dadurch vermeiden, daß man das Lesen des Textes mit dem Sortieren der ersten Läufe quasi gleichzeitig durchführt. Es tritt hierbei das Problem auf, daß Speicher für die Datenstruktur $S$ und Speicher für die Sortierung gleichzeitig benötigt wird. Dadurch muß $k$ kleiner gewählt werden, was wegen der größeren Anzahl von Läufen eine längere Sortierphase zur Folge hat. Aber weil auf diese Weise die temporäre Datei auf weniger als 600 Mbytes verkleinert werden kann, ist diese Methode trotz der etwas längeren Laufzeit auf für sehr große Dokumentensammlungen noch praktikabel.

Hierzu noch eine Bemerkung: die eingeschobene Sortierung von Läufen noch während der Textanalyse macht es wünschenswert, daß die Termnummern $t$ in der Reihenfolge des ersten Auftretens den Termen zugewiesen werden, wie in Abbildung 14 dargestellt. Der erste sortierte Lauf muß nämlich auf Platte geschrieben werden, bevor im Text weitergemacht werden kann. Es gibt keine Möglichkeit dies in einem Lauf zu bewerkstelligen, wenn Termnummer in lexikographischer Ordnung für die gesamte Dokumentensammlung vergeben werden müssten.