Open Source im professionellen Einsatz
Linux-Magazin 09/2017
1013

Rollendes Fenster

Bei einer Fenstergröße von n=3 extrahiert der Algorithmus aus "Ene mene muh und raus bist du." zum Beispiel die Fenster "Ene mene muh", "mene muh und", "muh und raus" und so weiter. Die ersten zwei Wörter bestimmen jeweils den Zustand des Automaten ("bist du"), das folgende Wort (oder im vorliegenden Fall das Sonderzeichen ".") ist der Folgezustand. Stolpert der Algorithmus im zweiten Teil des Abzählreims ("raus bist du noch lange nicht") ebenfalls wieder auf den Zustand "bist du", dann folgt auf diesen aber kein Punkt, sondern das Wort "noch". Jetzt hat der Algorithmus beim späteren Erstellen des Zufallstextes zwei Möglichkeiten: Er kann auf "bist du" entweder einen Punkt folgen lassen oder das Wort "noch", und er wird dies auch entsprechend den kalkulierten Zufallswerten tun. Das Ergebnis ist ein Text, der leicht menschliche Qualitäten aufweist, weil er Wortfolgen kopiert, aber hin und wieder in andere Zusammenhänge springt, was entweder konfus oder lustig klingt.

Listing 1 holt sich den Sourcecode der bisher erschienenen Programmier-Snapshots seit 1997 und übergibt den Namen der sie enthaltenden Datei an die Funktion »generate_from()« in Zeile 68. Die Funktion »statemap_gen« ab Zeile 37 unterteilt die Datei mit »token_feed()« in Tokens und übergibt die daraus resultierende Liste der Funktion »window()« ab Zeile 26, die als Fensterbreite »n=4« entgegennimmt. Der Status der Markow-Kette besteht aus den drei letzten Wörtern, das vierte ist Teil des Folgezustands.

Listing 1

randomtext.py

01 #!/usr/bin/python3
02 from nltk.tokenize import word_tokenize
03 from collections import deque
04 import re
05 import random
06
07 re_special=re.compile("^[,.:]$")
08 re_word=re.compile("^\w+$")
09
10 def token_feed(file):
11     string  = open(file, 'r').read()
12
13     for i in word_tokenize(string):
14         if re_special.match(i) or \
15            re_word.match(i):
16             yield(i)
17
18 def tokens_to_text(tokens):
19     out=""
20     for word in tokens:
21         if(not re_special.match(word)):
22             out += " "
23         out += word
24     return out
25
26 def window(seq, n):
27     it = iter(seq)
28     win = deque(
29       (next(it, None) for _ in range(n)),
30       maxlen=n)
31     yield win
32     append = win.append
33     for e in it:
34         append(e)
35         yield win
36
37 def statemap_gen(file):
38     statemap={}
39     tokens=token_feed(file)
40     for state in window(tokens,4):
41         key   = list(state)
42         value = key.pop()
43         key   = tuple(key)
44
45         if key in statemap:
46             statemap[key].append(value)
47         else:
48             statemap[key] = [value]
49     return statemap
50
51 def generate_from(file):
52     statemap=statemap_gen(file)
53     key=list(
54       random.choice(list(statemap.keys())))
55     words_new=list(key)
56
57     for i in range(200):
58         if not tuple(key) in statemap:
59             continue
60         next_token = random.choice(
61           statemap[tuple(key)])
62         words_new.append(next_token)
63         key.append(next_token)
64         key.pop(0)
65
66     return tokens_to_text(words_new)
67
68 print(generate_from('test.txt'))

Damit der Tokenizer aus dem Paket »nltk« bereitsteht, muss ich es mit »pip3 install nltk« installieren und noch den Tokenizer-Datensatz »punkt« herunterladen (Abbildung 3). Satzzeichen wie Kommas oder Doppelpunkte (der reguläre Ausdruck in Zeile 7 definiert sie alle) interpretiert der Tokenizer als eigene Tokens, das erhöht später die Lesbarkeit des Zufallstextes.

Abbildung 3: Herunterladen der Daten für den Nltk-Tokenizer.

Abbildung 4 zeigt, wie der Algorithmus aus dem Abzählreim und der Fensterlänge n=3 eine Zustandsdatei der Markow-Kette erzeugt. Die Alternativen "." und "noch" als mögliche Folgen der Wortkette "bist du" gibt dieser Eintrag vor:

Abbildung 4: Zerteilen eines Textes in Tokens und Erstellen des Markow-Modells.
('bist', 'du'): ['.', 'noch']

Der Python-Code zeigt einige Schmankerl der Sprache, zum Beispiel den »yield()« -Operator in der Funktion »token_feed()« in Zeile 16: Damit Python mittels einer For-Schleife über die Komponenten eines Objekts iterieren kann, muss selbiges vom Typ »Iterable« sein. Diese spucken ihre Komponenten nicht in einem Rutsch aus, sondern reichen sie scheibchenweise bei jedem Aufruf durch.

Das hat den Vorteil, dass das Skript nicht alle in einem Konstrukt enthaltenen Daten im Arbeitsspeicher vorhalten muss, sondern sie erst bei Bedarf ausrechnen darf. So kann ein Objekt unendlich viele Komponenten enthalten, wenn sie nie alle gebraucht werden, bleibt die Illusion trotz begrenztem Arbeitsspeicher erhalten.

Python bietet auch eine Vielzahl von Datenstrukturen. Die so genannten Double Ended Queues, genannt »deque« , in der Funktion »window()« ab Zeile 26 lassen sich besonders performant umwandeln, indem Elemente zum Kopf oder Schwanz der Schlange hinzugefügt oder entfernt werden. Der einzige Schönheitsfehler ist, dass der Aufrufer der Funktion »window()« die von ihr zurückgegebene Deque nicht manipulieren darf, sonst gerät der Algorithmus durcheinander.

Aus diesem Grund kopiert Zeile 41 mit »key=list(state)« die Elemente des Deque-Objekts in eine Python-Liste, auf der die Funktion »statemap_gen()« nach Herzenslust herumorgeln darf. Sie interpretiert die ersten n-1 Elemente als Markow-Status und das letzte Element als möglichen Folgewert.

In »key« liegt nach Zeile 43 ein nicht mehr modifizierbarer Python-Tupel, der dem Eintrag unter dem Schlüssel in einem mehrdimensionalen Dictionary »statemap« den Folgewert zuweist. Später kann der Algorithmus also nachsehen, ob zu einer Folge von n-1 Wörtern schon ein oder mehrere Folgewerte existieren, und davon per »random.choice()« in Zeile 60 einen zufälligen auswählen. Das lenkt den Text in unberechenbare Bahnen und macht den Reiz des Verfahrens aus.

Das Ergebnis präsentiert Abbildung 5. Es zeigt allerdings, dass das angewandte Markow-Ketten-Verfahren nicht automatisch spannende neue Artikel liefert. Auch bei der Grammatik hapert es noch gewaltig. Der Snapshot wird wohl auf absehbare Zeit von Hand erstellt werden müssen.

Abbildung 5: Das KI-System schreibt den Snapshot aller Snapshots.

Online PLUS

Im Screencast demonstriert Michael Schilli das Beispiel: http://www.linux-magazin.de/Ausgaben/2017/09/plus

Der Autor

Michael Schilli arbeitet als Software-Engineer in der San Francisco Bay Area in Kalifornien. In seiner seit 1997 laufenden Kolumne forscht er jeden Monat nach praktischen Anwendungen verschiedener Programmiersprachen. Unter mailto:mschilli@perlmeister.com beantwortet er gerne Fragen.

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 3 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

  • Screencast zum Snapshot 09/2017

    Markow-Ketten modellieren Systeme, die mit vorgegebenen Wahrscheinlichkeiten von Zustand zu Zustand hüpfen. Aber können sie nach einer Analyse bisher geschriebener Artikel ein KI-System erzeugen, das neue Kolumnen wie diese schreibt?

  • Erkenne die Zeichen

    Häufig müssen Programme strukturierte Eingabedateien verarbeiten und verstehen. Komplizierte Dateiformate erfordern dabei hohen Programmieraufwand - oder den Einsatz eines Parsergenerators. JavaCC deckt die wichtigsten Aspekte der Parsergenerierung für Java-Programme ab.

  • Workshop für Werkzeugmacher

    Linux-taugliche Entwicklungswerkzeuge für Perl sind rar, doch eine Eigenbau-IDE ist mit JEdits Hilfe kein Problem und zudem kostenlos, maßgeschneidert und plattformunabhängig.

  • Einmalige Gelegenheit

    Passwörter sind trotz Biometrie-Boom immer noch das am häufigsten eingesetzte Mittel zur Authentifizierung. In unfreundlichen Umgebungen versuchen Falschspieler sie abzuhören oder auszuspähen. Das macht aber nichts, wenn sie nur einmal gültig sind.

  • Snapshot

    Auf Amazons Lambda-Service laufen selbst geschriebene Python-Skripte in Containerumgebungen – demonstriert im Snapshot am Beispiel eines AI-Programms zur Bewegungsanalyse in Überwachungsvideos.

comments powered by Disqus

Stellenmarkt

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.