N-Gramme sind Reihen von Zeichen oder Wörtern. Ein Wort-Bigramm ist so eine Kombination von zwei Wörtern, wie zum Beispiel "Hallo Welt". Die folgenden Werte beziehen sich allerdings lediglich auf die Buchstabenebene und ihre stochastische Wahrscheinlichkeit in deutschen Texten bzw. speziell im Text Der Goldkäfer1 von E. A. Poe. Um diese N-Gramme aus dem Text auszufiltern wurde das Programm text2ngram2 erweitert um zu einer sortierten Ausgabe inklusive relativer Häufigkeit zu gelangen. Der Kern dieser Erweiterung wurde zusammen mit meinem Mitstudenten Matthias Busse3 erstellt und ist unter meinen weiteren Veröffentlichungen4 zu finden.
Der folgende Ausschnitt stellt den Kern des Programmes dar. In der ersten Zeile wird ein Programm von Zhang Le2 aufgerufen, welche N-Gramme im Text zählt. Danach werden diese N-Gramme sortiert und die Gesamtanzahl an N-Grammen bestimmt. In Zeile vier wird die Tabelle gekürzt, wonach die N-Gramme mit ihrer relativen Häufigkeit versehen werden und in der letzten Zeile schließlich nochmals absteigend geordnet in die Ausgabedatei geschrieben werden:
1 $needpos/text2ngram -c $ifile -n$n > tmp 2 sort -n +1 -2 tmp > tmp2 3 T=`awk '{total += $2} END {print total}' tmp2` 4 tail -n $num tmp2 > tmp3 5 awk -v total="$T" '{print $0, $2/total}' tmp3 > tmp4 ... 6 sort -r +2 -3 tmp4 >> ngram_$n
Das Ergebnis einer solchen Analyse
( ./text_analyser goldkaefer -n 1-3 -num 5 )
ist für einzelne Buchstaben, Bi- und Trigramme:
// 1-gram table, absolute and relative value e 10900 0.159641 n 6855 0.100398 i 5051 0.073977 r 4173 0.0611178 t 3469 0.050807 // 2-gram table, absolute and relative value en 2583 0.0465833 ch 2129 0.0383956 er 2047 0.0369168 ei 1356 0.0244549 te 1255 0.0226334 // 3-gram table, absolute and relative value ich 953 0.0221912 ein 748 0.0174176 und 437 0.0101758 ine 429 0.00998952 der 395 0.00919781
Wie schon angedeutet ist jede Sprache durch eine besondere Häufigkeit an jeweiligen N-Grammen erkennbar. Dies muss nicht umbedingt nur auf "richtige" Sprachen zutreffen sondern kann sich auch auf andere Reihungen von Zeichen beziehen, bei denen manche Kombinationen häufiger vorkommen als andere. Um diese Umstände zu beschreiben werden Sprachmodelle eingesetzt, die die Wahrscheinlickeit beschreiben, dass auf eine bestimmte Wortkette ein bestimmtes Wort folgt. Je nach dem wie viele Wörter sie dabei berücksichtigen, nennt man sie N-Gramm-Sprachmodelle.
So berücksichtigt ein Unigramm-Modell lediglich die Wahrscheinlichkeit einzelner Wörter, während ein Trigramm-Modell die Wahrscheinlichkeit angibt, dass auf zwei Wörter (die sogenannte Historie h) ein bestimmtes Wort w folgt, also P(w|h) (sprich: Die Wahrscheinlichkeit P dass das Ereignis w eintritt unter der Vorraussetzung h). Addiert man für alle möglichen wi die einzelnen Wahrscheinlichkeiten P(wi|h), so ergibt sich 1.
Die Wahrscheinlichkeit dass eine Wortkette w1 w2 w3 w4 vorkommt, berechnet sich somit durch:
P(w1..w4) = P(w1) · P(w2|w1) · P(w3|w1 w2) · P(w4|w1 w2 w3)Als Maß für die Güte eines Sprachmodelles kann nach Wendemuth5 die Perplexität einer Stichprobenkette aus N Wörtern genommen werden:
PP= [P(w1..wN)]-1/NDies stellt die mittlere Anzahl der Entscheidungsmöglichkeiten für jedes Wort der Reihe dar. Nehmen wir zum Beispiel an, die Wahrscheinlichkeit für "Hallo" beträge 5%, daher durchschnittlich sei jedes 20te Wort eben jener einfache Gruß. Im Durchschnitt auf jedes fünfte "Hallo" ein "Welt", was eine Wahrscheinlichkeit P(Welt|Hallo) = 20% ergibt. Die Perplexität ist somit
(0,05 · 0,20)-1/2 = 10was der durchschnittlichen Anzahl von Auswahlmöglichkeiten für jedes der beiden Wörter entspricht. Eben diese Zahl zu minimieren ist das Ziel eines Sprachmodelles, so dass die Zahl der möglichen folgenden Wörter bestmöglichst eingegrenzt ist. Dies ist besonders bei Spracherkennungssoftware sehr hilfreich, um unter akustisch sehr ähnlich klingenden Wörtern dass zum Kontext passende zu finden.
Ebenfalls noch von Interesse ist die Wahrscheinlichkeit dass ein bestimmtes Wort an einer bestimmten Stelle steht. Um dies zu berechnen werden Markow-Ketten6 benutzt, die folgendermaßen aufgebaut sind: In einer Matrix oder Tabelle wird festgehalten wie groß die Wahrscheinlichkeit ist, dass auf ein Wort/Zeichen wi ein Wort/Zeichen wj folgt.
Die Wahrscheinlichkeit für das Auftreten von wj an der Stelle n berechnet sich nun durch die Summe aller möglichen Produkte der Wahrscheinlichkeit dass wj auf ein bestimmtes wi folgt und der Wahrscheinlichkeit dass wi sich an der Stelle (n - 1) befindet. Oder anders ausgedrückt:
P(wj|h1) · P(h1) + P(wj|h2) · P(h2) + ... + P(wj|hn) · P(hn)Im folgenden sollen die Zahlen aus Aufgabe a mit den Werten von Klaus Pommerening7 verglichen werden, der sich wiederum vor allem auf F. L. Bauer8 bezieht, verglichen werden.
Bei den einzelnen Buchstaben stimmen die gefundenen Zahlen ziemlich genau mit den dort genannten überein. Sogar die Reihenfolge der ersten vier Lettern, e-n-i-r ist gleich. Der in unserem Text an fünfter Stelle stehender Buchstabe 't' hat dabei in der anderen Auflistung sogar eine höhere relative Häufigkeit, wenn gleich die Buchstaben 'a' und 's' ihn dort in diesem Kriterium sogar noch übertreffen.
Schon mehr Unterschied ist bei den Bigrammen zu erkennen. Dies liegt daran, dass die Menge der möglichen Ketten von 26 auf 262 gestiegen ist, was bereits ungefähr einem Prozent der Zeichen im Text entspricht. Eine solche Auswahl ist somit weit weniger repräsentativ. Trotzdem sind in beiden Statistiken die Kombinationen "en", "er" und "ch" die drei wahrscheinlichsten, auch wenn im Goldkäferfall das "ch" über einen Prozentpunkt wahrscheinlicher ist. Die nächsten Kombinationen liegen sehr nah beieinander, lediglich das "de" ist in Poe's Werk weiter abgeschlagen.
Noch deutlichere Diskrepanz ergibt sich bei den Trigrammen, bei denen die Wertemenge nun schon ungefähr ein Drittel der getesteten Zeichenmenge ausmacht. Die beiden wahrscheinlichsten Trigramme "ich" und "ein" sind im Goldkäfer noch deutlich wahrscheinlicher als in den zitierten Tabellen. "ich" tritt sogar doppelt so oft (2,2 statt 1,1%) auf. Das nach den Tabellen drittwahrscheinlichste "nde" steht im Goldkäfer erst an Position 14. Solche Schwankungen sind allerdings auch durch einen besonderen Stil oder einen persönlichen Wortschatz zu erklären. Außerdem ist eine Geschichte wie der Goldkäfer anders geschrieben als etwas ein Zeitungsartikel oder ein Flugblatt. Um eine möglichst repräsentative Statistik zu erhalten, müssten also aus allen verschiedenen Textgattungen jeweils mehrere Texte von unterschiedlichen Autoren ausgewählt werden.