3. Textgenerierung

Wie kann man zufälligen Text generieren? Man könnte einfach ohne System Text über die Tastatur eingeben.

dldsnl u eo,aed uef. btnt H ninr eU et rrßD eos Tg, es ,mg nu u!ee n hläeebu Tn mad dpelti

Das ergibt natürlich keine sinnvollen Text. Wie könnte man das verbessern? Verschiedene Buchstaben treten mit unterschiedlicher Häufigkeit und häufig in Verbindung mit anderen Buchstaben auf. Man könnte also zählen, wie oft ein Buchstabe auf die anderen folgt (z.B. wie oft ein 'a' auf alle anderen Buchstaben folgt, wie oft ein 'b' ...). Man bildet nun den nächsten "zufälligen" Buchstaben mit Hilfe eine Funktion, die die vorherigen Buchstaben berücksichtigt. Das ergibt dann eine sogenannte Markovkette. Bei solch einem Markovprozess werden die Übergangswahrscheinlichkeiten eindeutig durch die Zustände festgelegt. Wir haben also zum Beispiel den Zustand, daß bereits ein 'q' generiert wurde. Es gibt nun eine sehr hohe Wahrscheinlichkeit, daß der nächste Buchstabe ein 'u' ist.

Die folgenden Beispiele sind nach diesem Schema generiert. Ein Ordnung 1-Text berücksichtig nur einen vorherigen Buchstaben, der Ordung 2-Text berücksichtigt schon zwei (digram oder 2-gram),...

Ordnung 1: n; iem d. fe, en dan deichenero ih Wan; Toare nd unerärteiern wer ERen Ton eickt daurted sig

Ordnung 2: mer wies Baas Semen erst, unde Kin aber Jer Regeben,

Ordnung 3: den Jorde mir werts ganze Was Und um Anspießen Serauch nung das Oder mein Vater

Ordnung 4: Und er einen und ihr Erde ihrer Menschuldig euren wir ein ein Baal-Perez

Ordnung 5: fang zusammeln und Zentnern Vorsatz und sie hin! so will auf den Weg des Vornehmen wir den verschriebe.

Beim Ordnung 5-Text sind die Wörter schon sehr gut lesbar. Man kann also durch solche Markovketten eine Verbesserung bei der Text Generierung erreichen.

Das ganze kann man natürlich auch auf die Wortebene erweitern. Dafür werden dann die Wörter gezählt und entsprechend ihrer Häufigkeit zufällig ausgewählt.

Claude E. Shanon beschreibt in "Mathematical Theory of Communication" einen Algorithmus, der diesem schon sehr nahe kommt: Um Text zu generieren durchsucht man ein Buch oder einen Text und wählt aus diesem zufällig ein Wort aus. Dann sucht man sich eine andere Stelle, an der das gleiche Wort auftaucht. Das daruffolgende Wort bildet dann das nächste Wort der Zufallstextes. Erweitert man dies von einem auf zwei oder mehr Wörter ergibt sich schon recht guter Text.

Das kann man natürlich automatisieren:

int k = 2;
char inputchars[5000000];
char *word[1000000];
int nword = 0;

word[0] = inputchars;
while scanf("%s", word[nword]) != EOF
word[nword+1] = word[nword] + strlen(word[nword]) +1
nword++

k gibt hier an wieviele Wörter berücksichtigt werden sollen. word[] ist eine Art Suffix Array. Die Zeiger zeigen allerdings nicht auf jeden Buchstaben, sondern immer nur auf den Wortanfang. In der while-Schleife wird die Eingabe gelesen und jedes Wort wird an inputchars angehangen.

Ist die Eingabe gelesen werden die ersten k Wörter ausgegeben. Dann wird der Array word[] mit Quicksort sortiert. Mit der Binärsuche wird jetzt jedes Vorkommen der ersten beiden Wörter festgestellt. Daraus wird dann zufällig eines ausgewählt. Das nächste Wort bildet dann das Zufallswort, das generiert wird. Ist das k-te Wort NULL so wird die Text Generierung beendet.

Führt man diese Programm aus (für k = 2), kommt man schon zu recht gutem Text:

Am Abend ist der Eiche zu Jerusalem habe seine Zunge ist Gott; denn er hin und seine Güte mir abfielen, die Ernte?

Es sie noch angemerkt, daß der generierte Text natürlich stark von der Eingabe abhängt, wie man an dem Beispiel gut erkennen kann.