Komprimierung von invertierten Dateien

Die Größe einer invertierten Datei kann durch Komprimierung erheblich reduziert werden. Im folgenden werden verschiedene Methoden vorgestellt, um dies zu bewerkstelligen. Betrachten wir zunächst einen typischen Eintrag aus einer invertierten Datei. Nehmen wir an, der Term Computer tritt in acht Dokumenten -- diese seien nummeriert als 3, 5, 20, 21, 23, 76, 77, 78 -- einer Sammlung auf, so daß der entsprechende Eintag wie folgt aussieht:

$$\langle\emph{Computer}; 8; [3, 5, 20, 21, 23, 76, 77, 78]\rangle.$$

Im allgemeinen speichert so ein Eintrag den Term $t$, die Anzahl der $t$ enthaltenden Dokumente $f_t$, und eine Liste $f_t$ von Dokumentennummern:

$$\langle t; f_t; [d_1, d_2, \ldots, d_{f_t}]\rangle.$$

wobei $d_k < d_{k+1}$. Weil die Liste der Dokumentennummern innerhalb eines Eintrages in aufsteigender Reihenfolge vorliegen, und weil jede weitere Operation auf einem solchen Eintrag sequentiell beginnend am Listenanfang stattfindet, kann die Liste als eine Anfangsposition und eine darauffolgende Liste von Differenzen zur Vorgängerposition $d_{k+1} - d_k$ gespeichert werden:

$$\langle \emph{Computer}; 8; [3, 2, 15, 1, 2, 53, 1, 1]\rangle.$$

Keine Information geht verloren, alle ursprünglichen Dokumentennummern können durch das Aufaddieren von Differenzen berechnet werden. Die zwei Darstellungen sind zwar äquivalent, doch es ist nicht auf Anhieb klar, wie ein Ersparnis erzielt wird, zumal es genauso wie zuvor acht Zahlen gespeichert werden müssen. Es fällt jedoch auf, daß die Zahlen in der zweiten Darstellung kleiner sind als die in der ersten. Demzufolge brauchen sie auch weniger Bits, um gespeichert zu werden. Angenommen die Dokumentensammlung enthält $N$ Dokumente, so bräuchte man $\lceil \log N\rceil$ Bits² für die Speicherung einer Dokumentennummer. Bisher haben wir dafür eine 32 Bit vorzeichenlose Integer-Zahl bereitgestellt, womit man eigentlich über 4 Milliarden Dokumente adressieren könnte, eine ziemliche Verschwendung. Doch woher weiß man im voraus, wie groß die grösste Zahl der Differenzliste sein wird, um entsprechend viele Bits für ihre Darstellung zu reservieren? Wir werden sehen, daß dies gar nicht notwendig ist, die einzelnen Einträge erhalten dynamisch ihre eigene Anzahl an Bits zugeordnet.

Abbildung 5: Kodierung von vorzeichenlosen Integer-Zahlen.

Betrachten wir hierzu die in Abbildung 5 dargestellten Möglichkeiten vorzeichenlose Integer-Zahlen zu kodieren. Bei dem Unärkode wird eine Integer-Zahl $x \ge 1$ als eine Folge der Länge $x-1$ von gesetzten Bits, gefolgt von einem Nullbit dargestellt. Offensichtlich neigt dieser Kode dazu, kleine Differenzen in der Kodierung unserer Dokumentenliste zu bevorzugen, was sich angesichts folgender Überlegungen als vorteilhaft erweist. Man könnte nämlich davon ausgehen, daß häufige Terme kleine Differenzen zwischen sich in der Liste haben, sonst wären sie ja nicht häufig. Genauso werden aber seltene Terme große Differenzen in der Darstellung zur Folge haben. Obwohl, wenn die Dokumente in ihrer Eingabereihenfolge gespeichert werden, und diese Eingabereihenfolge eine chronologische oder logische Bedeutung hat, so kann es sehr wohl sein, daß seltene Terme zu lokalen Häufungen neigen, und sind nicht gleichmäßig über die Dokumentensammlung verteilt. Die Praxis zeigt jedoch, daß die Verwendung des Unärkodes keine Ersparnis mit sich bringt.

Es gibt eine Reihe weiterer Kodes, die eine bessere Speicherplatzersparnis bieten. Einer ist der $\gamma$-Kode, der eine Zahl $x$ als Unärkode für $1 + \lfloor \log x \rfloor$ gefolgt von einem Binärkode der Länge $\lfloor \log x \rfloor$ Bits, der $x - 2^{\lfloor \log x \rfloor}$ darstellt, kodiert. Der unäre Teil spezifiziert also die Anzahl Bits, die zur Kodierung von $x$ benötigt werden, und der binäre Teil kodiert $x$ in dieser Anzahl von Bits. Nehmen wir als Beispiel $x=9$, dann ist $\lfloor \log x \rfloor = 3$ , und so wird $4 = 1 + 3$ im Unärkode als $1110$ dargestellt, gefolgt von $1=9-8$ dargestellt als die 3-Bit Binärzahl $001$, welche aneinandergehängt das Kodewort $1110~001$ ergeben.

Eine weitere Entwicklung ist der $\delta$-Kode, bei welchem der Präfix zur Beschreibung der Suffixbits der zuvor beschriebene $\gamma$-Kode anstatt des Unärkodes verwendet wird. Für dasselbe $x=9$ wird der unäre Präfix $1110$ durch $11000$, den $\gamma$-Kode von $4$ ersetzt. Folglich erhalten wir für $x=9$ den $\delta$-Kode $11000~001$. Obwohl anhand der Tabelle aus Abbildung 5 der $\delta$-Kode länger ist als der $\gamma$-Kode, ändert sich dieses Verhalten für große $x$. So benötigt der $\gamma$-Kode 39 Bits für die Darstellung von $x=1.000.000$, wogegen der $\delta$-Kode mit nur 28 Bits auskommt. Abbildung 6 zeigt die vorgestellten Methoden im Vergleich, jeweils angewendet bei der Bibel und bei der TREC-Kollektion.

Abbildung 6: Komprimierung der invertierten Dateien in Bits per Eintrag.