Textgenerator in Python – Markow-Kette mit Goethes Faust

Was du hier lernst

Dictionaries zum Zählen
Sortieren mit key
gewichteter Zufall
Markow-Ketten
reguläre Ausdrücke
Dateien lesen
Schleife statt Rekursion

So funktioniert der Goethe-Generator

Sprache ist kein Zufall. Nach »ich« folgt oft »bin« oder »habe«, fast nie »Tisch«. Diese Gewohnheiten lassen sich zählen – und wer weiß, welches Wort wie oft auf welches folgt, kann neuen Text würfeln, der dem Original erstaunlich ähnlich klingt. Genau das macht dieses Programm mit dem Anfang von Goethes »Faust«: rund 22.500 Wörter, von der »Zueignung« bis zur Szene »Wald und Höhle«.

1. Wörter zählen mit einem Dictionary

countWords1 liest den Text Zeile für Zeile, zerlegt jede Zeile mit split() in Wörter und führt für jedes Wort einen Zähler in einem Dictionary:

for line in fobj:
    zuordnung = line.split()
    for word in zuordnung:
        if word in mydict:
            mydict[word] = mydict.get(word) + 1
        else:
            mydict[word] = 1

Danach wird sortiert: sorted(mydict.items(), key=operator.itemgetter(1), reverse=True) ordnet die Paare aus Wort und Anzahl nach der Anzahl, die häufigsten zuerst. Weil split() nur an Leerzeichen trennt, zählen »und« und »Und« getrennt, und Satzzeichen hängen am Wort. Auch die Sprechernamen tauchen in der Liste auf – »FAUST:« ist für Python ein Wort wie jedes andere.

2. Zufall mit Gewicht

generateTextByWordCount wählt Wörter zufällig aus, aber nicht gleich wahrscheinlich. Häufige Wörter sollen öfter drankommen. Der Trick: Alle Anzahlen werden aufsummiert, eine Zufallszahl zwischen 1 und der Summe gezogen und dann so lange weitergezählt, bis die Zufallszahl erreicht ist:

choice = random.randint(1, overallCount)
currentNumber = 0
for entry in wordList:
    word, count = entry
    currentNumber += count
    if currentNumber >= choice:
        selectedWord = word
        break

Ein Wort, das 384-mal vorkommt, deckt 384 Zahlen ab, ein seltenes nur eine. Das Ergebnis siehst du in der Ausgabe als »Wortsalat«: Die Häufigkeiten stimmen, aber die Wörter haben nichts miteinander zu tun.

Das Glücksrad

Dieses Verfahren heißt Roulette-Wheel-Selection: Jedes Wort bekommt ein Stück vom Glücksrad, so groß wie seine Häufigkeit. Dasselbe Rad dreht sich im Buch beim genetischen Algorithmus – dort bekommen gute Flugpläne größere Stücke.

3. Wer folgt auf wen?

Der eigentliche Generator braucht mehr als Häufigkeiten: Er muss wissen, welche Wörter nach einem bestimmten Wort kommen. Das zählt countWords2 mit einem regulären Ausdruck:

pattern = r"(?<!\w)" + escape(term) + r"[\s]+[\w]+"

Gesucht wird das Wort term, danach Leerraum ([\s]+) und das nächste Wort ([\w]+). escape(term) sorgt dafür, dass Zeichen wie die Klammer in »(Er« nicht als Teil der Suchsprache gelesen werden, und (?<!\w) verlangt, dass vor term kein Buchstabe steht – sonst würde die Suche nach »an« auch das Ende von »Plan« finden. Heraus kommt wieder eine sortierte Liste, diesmal aus Wortpaaren wie »der Erde« mit ihrer Anzahl.

4. Die Markow-Kette: Wort für Wort

Jetzt greift alles ineinander. generateTextByPredecessor beginnt mit einem Startwort, holt die Liste seiner Nachfolger, dreht das Glücksrad und macht das gewählte Wort zum neuen Vorgänger:

predecessor = selectedWord.split()[1]
print(predecessor, end=" ", flush=True)

Jede Nachfolgerliste wird nur einmal berechnet und dann im Dictionary relativeListsDict aufbewahrt. Taucht ein Wort später wieder auf, geht es ohne erneutes Durchsuchen des ganzen Textes weiter. Findet sich für ein Wort gar kein Nachfolger – das passiert bei Wörtern, die nur am Zeilenende stehen –, beginnt eine neue Kette mit einem zufälligen Wort.

Warum klingt das nach Goethe?

Eine Markow-Kette hat ein sehr kurzes Gedächtnis: Das nächste Wort hängt nur vom aktuellen ab. Jedes Wortpaar kommt so tatsächlich im Faust vor, deshalb klingt jeder kleine Ausschnitt richtig. Einen Plan für den ganzen Satz gibt es aber nicht. Heutige Sprachmodelle funktionieren im Kern ähnlich – nur schauen sie auf Tausende vorherige Wörter statt auf eines.

5. Schleife statt Rekursion

Im Buch ruft sich generateTextByPredecessor für jedes neue Wort selbst wieder auf. Das ist elegant, hat aber eine Grenze: Jeder Aufruf bleibt offen, bis der Text fertig ist, und Python erlaubt nur etwa 1000 verschachtelte Aufrufe. Für 100 Wörter reicht das, für einen ganzen Roman nicht. Die while-Schleife hier erledigt dasselbe ohne Grenze: Sie zählt length herunter, bis genug Wörter beisammen sind.

Genau hingeschaut

In der Originaldatei zum Buch standen die beiden Zeilen, die den Nachfolger übernehmen und ausgeben, eine Stufe zu weit eingerückt – innerhalb der for-Schleife. Damit gab das Programm alle Kandidaten vor dem gewählten Wort aus, nur das gewählte nicht. In Python ist Einrückung eben Teil der Grammatik. Und generateTextByWordCount gab am Ende die Schleifenvariable word zurück statt selectedWord. Das klappte nur, weil break die Schleife genau beim gewählten Wort verlässt. Hier steht jetzt ausdrücklich, was gemeint ist.

Probier mal

Jede Variante ändert den Code oben. Ein Klick auf »Ausprobieren« übernimmt die Änderung in den Editor und startet das Programm. »Zurücksetzen« holt das Original zurück.

01Mehr Text, bitte

Statt 100 Wörtern erzeugt der Generator 250. Du siehst dabei auch, warum das Buch diese Umsetzung »die denkbar langsamste Variante« nennt: Für jedes neue Wort liest countWords2 den ganzen Text noch einmal. Nur bereits bekannte Vorgänger kommen aus dem Zwischenspeicher relativeListsDict.
```
- generateTextByPredecessor(randomStart, length=100)
+ generateTextByPredecessor(randomStart, length=250)
```

02Alles in einem Durchgang zählen

Die schnelle Variante: Einmal durch alle Wörter laufen und für jedes Wort die Liste seiner Nachfolger anlegen. Weil häufige Nachfolger mehrfach in der Liste stehen, wählt random.choice automatisch nach Häufigkeit aus – dasselbe Roulette-Prinzip, nur ohne Zählschleife. Satzzeichen bleiben dabei erhalten, und 300 Wörter sind im Nu fertig.

-     print("\nGoethe-Generator – jedes Wort hängt vom vorherigen ab:")
-     randomStart = generateTextByWordCount(wordList, length=1)[0]
-     print(randomStart, end=" ")
-     generateTextByPredecessor(randomStart, length=100)
+     print("\nGoethe-Generator – alle Nachfolger in einem Durchgang gezählt:")
+     # alle Nachfolger in einem einzigen Durchgang sammeln
+     successors = {}
+     alleWoerter = open(textFile, encoding="utf-8").read().split()
+     for current, following in zip(alleWoerter, alleWoerter[1:]):
+         successors.setdefault(current, []).append(following)
+ 
+     word = generateTextByWordCount(wordList, length=1)[0]
+     text = [word]
+     for x in range(300):
+         word = random.choice(successors.get(word) or alleWoerter)
+         text.append(word)
+     print(" ".join(text))

03Zwei Vorgänger statt einem

Diese Idee schlägt das Buch selbst als Übung vor: Das nächste Wort hängt jetzt von den zwei vorherigen ab. Der Text wird deutlich grammatischer – aber auch näher am Original. Ganze Verse tauchen wieder auf, weil viele Wortpaare im Faust nur ein einziges Mal vorkommen.

-     print("\nGoethe-Generator – jedes Wort hängt vom vorherigen ab:")
-     randomStart = generateTextByWordCount(wordList, length=1)[0]
-     print(randomStart, end=" ")
-     generateTextByPredecessor(randomStart, length=100)
+     print("\nGoethe-Generator – jedes Wort hängt von zwei Vorgängern ab:")
+     successors = {}
+     alleWoerter = open(textFile, encoding="utf-8").read().split()
+     for a, b, c in zip(alleWoerter, alleWoerter[1:], alleWoerter[2:]):
+         successors.setdefault((a, b), []).append(c)
+ 
+     a, b = random.choice(list(successors))
+     text = [a, b]
+     for x in range(150):
+         c = random.choice(successors.get((a, b)) or alleWoerter)
+         text.append(c)
+         a, b = b, c
+     print(" ".join(text))

04Buchstaben statt Wörter

Die zweite Übung aus dem Buch: Dieselbe Idee funktioniert mit Buchstaben. Auf je vier Zeichen folgt ein fünftes, gewürfelt nach der Häufigkeit im Faust. Heraus kommen Wörter, die es nicht gibt, die aber verdächtig deutsch klingen. Probiere auch order = 2 und order = 6.

-     print("\nGoethe-Generator – jedes Wort hängt vom vorherigen ab:")
-     randomStart = generateTextByWordCount(wordList, length=1)[0]
-     print(randomStart, end=" ")
-     generateTextByPredecessor(randomStart, length=100)
+     print("\nGoethe-Generator – Buchstabe für Buchstabe:")
+     # Markow-Kette über Buchstaben: auf 4 Zeichen folgt ein fünftes
+     order = 4
+     text = open(textFile, encoding="utf-8").read()
+     successors = {}
+     for i in range(len(text) - order):
+         successors.setdefault(text[i:i + order], []).append(text[i + order])
+ 
+     start = random.randrange(len(text) - order)
+     result = text[start:start + order]
+     for x in range(700):
+         result += random.choice(successors.get(result[-order:], [" "]))
+     print(result)

Vom Buch in den Browser

Der Goethe-Generator ist ein reines Textprogramm – er braucht weder pygame noch die Zeichen-API c4f und läuft im Browser fast unverändert. Die Datei mit dem Text liegt im virtuellen Dateisystem des Browsers, deshalb funktioniert open() wie auf dem eigenen Rechner. In der Originaldatei zum Buch las das Programm eine englische Textdatei (»46-8.txt«); hier ist es, passend zum Kapitelnamen, Goethes »Faust« (gemeinfrei).

Von Python 2 nach Python 3:

Im Buch (Python 2)	Hier (Python 3)
`print predecessor,`	`print(predecessor, end=" ", flush=True)`
`mydict.has_key(word) == 1`	`word in mydict`
`open(fileName, "r")`	`open(fileName, "r", encoding="utf-8")`
`[\w]+` kennt keine Umlaute	`[\w]+` erkennt auch ä, ö, ü und ß

Außerdem wurde einiges korrigiert:

Schleife statt Rekursion: generateTextByPredecessor ruft sich nicht mehr selbst auf, damit auch lange Texte nicht an Pythons Grenze für verschachtelte Aufrufe stoßen.
Kein veränderlicher Standardwert: Im Buch hieß der Parameter relativeListsDict={}. Python legt dieses Dictionary nur ein einziges Mal an und benutzt es bei jedem Aufruf wieder – ein bekannter Stolperstein. Hier ist der Standardwert None, und die Funktion legt bei Bedarf ein neues Dictionary an.
Sicherer regulärer Ausdruck: escape(term) und (?<!\w) verhindern Fehler bei Wörtern mit Klammern und falsche Treffer mitten im Wort.
Rückgabewerte: generateTextByWordCount gibt die ausgewählten Wörter als Liste zurück, statt sie selbst auszugeben – so kann das Hauptprogramm entscheiden, wie sie erscheinen.
Zufallszahl ab 1: Mit random.randint(0, overallCount) bekam das erste Wort der Liste eine kleine Extra-Chance, denn eine gezogene 0 wählt immer das erste Wort. Jetzt beginnt die Zählung bei 1.
Sackgassen: Wörter ohne Nachfolger starten eine neue Kette, statt die Ausgabe ins Leere laufen zu lassen.

Original aus dem Buch ansehen wordcount.py · Python 2

'''
Created on 30.11.2009

@author: GWV7FD3
'''
from re import findall

import operator, random

def countWords1(fileName):
    mydict  =   {} 
    fobj    =   open(fileName, "r")
    
    for line in fobj:
        zuordnung = line.split()
        for word in zuordnung:
                if mydict.has_key(word) == 1:
                    mydict[word]=mydict.get(word)+1
                else:
                    mydict[word]=1
                    
    fobj.close()
    
    wordList = mydict.items()
    wordList = sorted(wordList, key=operator.itemgetter(1), reverse=True)
    
    return wordList            

def generateTextByWordCount(wordList, length=100):
    overallCount = 0
    for entry in wordList:
        overallCount += entry[1]
        
    for x in range(0, length):
        choice = random.randint(0, overallCount)
        currentNumber   = 0
        selectedWord    = None
        for entry in wordList:
            word, count = entry
            currentNumber += count
            if currentNumber >= choice:
                selectedWord = word
                break
        
        print word,
        
    return word
    

def countWords2(fileName, term):
    mydict  =   {} 
    fobj    =   open(fileName, "r")
    
    for line in fobj:
        words = findall(term+r'[\s]+[\w]+', line)
        for word in words:
            if mydict.has_key(word) == 1:
                mydict[word] = mydict.get(word)+1
            else:
                mydict[word] = 1
                    
    fobj.close()
    
    wordList = mydict.items()
    wordList = sorted(wordList, key=operator.itemgetter(1), reverse=True)
    
    return wordList

def generateTextByPredecessor(predecessor, length=100, relativeListsDict={}):
    if length <= 0:
        return
        
    if relativeListsDict.has_key(predecessor) == True:
        relativeWordList, overallCount = relativeListsDict.get(predecessor)
    else:
        relativeWordList = countWords2("46-8.txt", predecessor)
        overallCount = 0
        for entry in relativeWordList:
            overallCount += entry[1]
        relativeListsDict[predecessor] = (relativeWordList, overallCount)
        
    choice = random.randint(0, overallCount)
    currentNumber   = 0
    selectedWord    = None
    for entry in relativeWordList:
        word, count = entry
        currentNumber += count
        if currentNumber >= choice:
            selectedWord = word
            break
        
        predecessor = word.split()[1]
        print predecessor,
        
    generateTextByPredecessor(predecessor, length=length-1, relativeListsDict=relativeListsDict)

if __name__ == "__main__":
    wordList = countWords1("46-8.txt")
#    for word in wordList:
#        anzahl, wort = word
#        print "%s\t->\t%s" % (wort, anzahl)
#    generateTextByWordCount(wordList)
    randomStart = generateTextByWordCount(wordList, length=1)
    generateTextByPredecessor(randomStart)