2    Texte bauen mit Markow

Wissen Sie, was ein Zeichtstern, ein Nichtspunkt oder ein Duftgebück ist? Oder haben Sie etwa schon einmal wirrwartend fenstige Wunschwellen durchhoffnet? Vermutlich nicht! Auch wenn diese rätselhaften Wörter offenbar deutschsprachig sind, können wir über deren Bedeutung nur mutmaßen. Doch eines haben sie gemeinsam: Sie alle wurden von einem Algorithmus erdacht, den wir in diesem Kapitel vorstellen – und dieser ist imstande, weitaus mehr zu leisten, als unsinnige Wörter zu erdichten.

Ob Zeitungsmeldung, Bedienungsanleitung oder Roman: Wann immer Menschen einen Text lesen, steht der Sinn des Geschriebenen im Vordergrund. Computer allerdings wissen nichts über Texte und deren Bedeutung. Für einen Rechner sind Texte lediglich Zeichenketten, genauer gesagt: Abfolgen von Zahlen. Jede Zahl steht für ein Zeichen. Die Übersetzung von Zeichen in Zahlen und zurück regelt meist der ASCII- oder der Unicode-Standard.

Dieses Kapitel stellt eine Erfindung vor, die der russische Mathematiker Andrei Markow um 1919 gemacht hat. Sein Markow-Prozess lässt sich besonders gut auf Zeichenketten anwenden. Dieser untersucht gegebene Texte im Hinblick auf eine einzige Eigenschaft: Welche Zeichen folgen darin aufeinander und welche nicht? In einem zweiten Schritt kann der Markow-Prozess Texte zusammenbauen, die diese Eigenschaft des Originals reproduzieren – mit erstaunlichen und oft belustigenden Ergebnissen.

Im einfachsten Fall besitzt ein Markow-Prozess kein Gedächtnis. Das bedeutet, dass die Wahrscheinlichkeit für das Auftreten eines bestimmten nächsten Zeichens unabhängig von den vorherigen Zeichen ist. Wenn Sie einen deutschsprachigen Text mittels eines solchen erinnerungslosen Markow-Prozesses untersuchen, werden Sie feststellen, dass die Häufigkeit des Buchstabens E etwa 15 % beträgt. Seltene Buchstaben wie X, Y oder Q hingegen kommen auf Häufigkeiten von wenigen Prozentbruchteilen.

Interessanter wird es, wenn der Algorithmus zur Bestimmung der Wahrscheinlichkeit eines nächsten Zeichens die vorherigen Zeichen berücksichtigt. Der Grad des Markow-Prozesses legt die Anzahl der berücksichtigten vorangegangenen Zeichen fest. Grad 1 bedeutet, dass nur das jeweils letzte Zeichen zählt, ein Markow-Prozess zweiten Grades interessiert sich für die letzten beiden Zeichen und so fort.

Abbildung 2.1     Das Prinzip hinter dem Markow-Prozess: links die Textbeispiele, rechts oben der Übergangsgraph, rechts unten die Übergänge als Tabelle

Abbildung 2.1 veranschaulicht das Prinzip anhand eines Markow-Prozesses ersten Grades und eines aus vier Wörtern bestehenden Textbeispiels: HAUS, LAUS, LAUB und AUA. Der Übergangsgraph und die Tabelle zeigen:

• Auf ein H oder L folgt immer ein A.

• Auf ein A folgt immer ein U.

• Auf ein U kann ein S, ein B oder ein A folgen.

Damit haben wir die zulässigen Übergänge vollständig beschrieben. Die Produktion eines neuen Worts nach den so beschriebenen Regeln läuft dann wie folgt ab:

• Starten Sie an einem beliebigen Knoten des Übergangsgraphen, beispielsweise mit dem A.

• Nach dem A folgt immer ein U.

• Das U bietet drei Anschlussmöglichkeiten: S, B und A. In diesem Fall suchen Sie sich eine aus oder lassen das Los entscheiden! Auf diese Weise können Sie etwa folgende Ketten bilden: AU, AUS, AUB, AUA, AUAUS, AUAUB …

Entsprechendes gilt, wenn Sie mit einem H starten. Dann kann der Algorithmus HA, HAU, HAUS, HAUHAU, HAUAUB etc. produzieren. Der hier dargestellte Markow-Prozess ist insofern vereinfacht, als dass er die Häufigkeiten der einzelnen Übergänge nicht berücksichtigt. Das holen wir in Abschnitt 2.3, »Das Beispielprogramm Wörter vorschlagen«, nach.

Nach dem eben gezeigten Prinzip lassen sich auch auf Basis umfangreicherer Textbeispiele neue Texte beliebiger Länge erzeugen. Der Markow-Prozess weiß zwar nichts über Sprachen und Wörter, kann aber ausgehend von entsprechenden Textquellen eindeutig deutschsprachige Wörter wie transportig, wiedenartig, überhaftlich und deineswegs erdenken oder englischsprachigen Unsinn wie: my deal happily doubt what he two schreiben.

Dieses Kapitel zeigt zwei konkrete Anwendungen von Markow-Prozessen: Der »Nonsense-Texter« produziert neue Texte aufgrund von gegebenen Textquellen. Das Programm »Wörter vorschlagen« bietet eine simple Satzvervollständigung.

2.1    Das Beispielprogramm Nonsense-Texter

Der »Nonsense-Texter« erzeugt Texte auf Basis gegebener Textquellen. Wie alle Beispielprogramme in diesem Buch können Sie den Nonsense-Texter direkt im Webbrowser öffnen, ausprobieren, den Code anschauen und modifizieren. Dafür nutzen Sie den p5.js-Online-Editor. Unter https://maschinennah.de/ki-buch finden Sie Links auf alle Beispielprogramme, geordnet nach Kapiteln.

Mit dem roten Button oben links starten Sie das Programm. Sie können sogar den Programmcode verändern und die Auswirkungen...