Dünne Matrizen

Die Ergebnisse vieler textstatistischer Analysen lassen sich am einfachsten in Form von Vektoren bzw. zwei- oder mehrdimensionalen Matrizen speichern. Beispielsweise werden Worthäufigkeiten in Vektoren und Kookkurrenzen  in zweidimensionalen Matrizen abgelegt. Bei den die Aufeinanderfolge von Wörtern betreffenden bedingten Wahrscheinlichkeiten hängt die Dimensionalität von der Länge der betrachteten Wortketten ab. Für Tupel benötigt man eine zweidimensionale, für Tripel hingegen eine dreidimensionale Matrix. Typisch für diese Matrizen ist, daß die meisten ihrer Einträge Null sind, da in korrekten sprachlichen Äußerungen nur ein kleiner Bruchteil aller theoretisch möglichen Wortfolgen erlaubt ist.

Deshalb ist es nicht sinnvoll, etwa die Häufigkeiten aller Worttripel eines größeren Textkorpus tatsächlich in einer dreidimensionalen Matrix abzuspeichern. Umfaßt der in einem Korpus von 1 000 000 Wörtern enthaltene Wortschatz beispielsweise 100 000 Wörter, so hätte die zugehörige Matrix eine Größe von 100 000 10 Einträgen. Tatsächlich kann ein Korpus dieser Größe nicht mehr als 999 998 unterschiedliche Worttripel enthalten. Werden also nur die Häufigkeiten von Worttripeln mit Korpushäufigkeiten größer Null gespeichert, so genügt eine vergleichsweise kleine Tabelle mit maximal 999 998 Einträgen.

Zur Erstellung einer solchen Tabelle hat sich die folgende Vorgehensweise bewährt:

1. Zunächst wird eine Integer-Kodierung des gesamten Textes durchgeführt, d. h. jedem Wort des Vokabulares wird eine eindeutige ganze Zahl zugeordnet und das betreffende Wort an jeder Auftretensposition durch diese Zahl ersetzt. Je nach Zahlenbereich der verwendeten Integers ergibt sich dadurch eine unterschiedlich starke Komprimierung des Textes: Bei 16 bit-Integers reduziert sich der Speicherplatzbedarf auf etwa ein Drittel, bei 24 bit-Integers auf die Hälfte und bei 32  bit-Integers auf ungefähr zwei Drittel der ursprünglichen Textgröße.
2. Alle im kodierten Korpus vorkommenden Worttripel werden in der Reihenfolge ihres Vorkommens in einer Liste abgelegt. Diese Liste hat die dreifache Größe des kodierten Korpus.
3. Mit einem auf Binärzahlen operierenden schnellen Sortieralgorithmus (Quicksort, s. Sedgewick, 1992) werden die Tripel in eine definierte Reihenfolge gebracht, so daß identische Tripel direkt aufeinander folgen.
4. Mit einem einfachen Kompressionsalgorithmus werden identische Tripel auf einen Eintrag reduziert. Gleichzeitig wird jedes Tripel um eine zusätzliche Angabe ergänzt, nämlich seine Auftretenshäufigkeit im Korpus.

In der entstandenen Tabelle können die Häufigkeiten von Worttripeln dadurch bestimmt werden, daß das interessierende Worttripel mit einer Binärsuche lokalisiert und der zugehörige Häufigkeitseintrag abgelesen wird.