Markovgenerator

In unserem kleinen Rubykurs für Hobby-Rubyisten haben wir letztens gelernt, wie man einen Generator programmiert, der anhand von einem Textkorpus grammatisch halbwegs korrekte aber total sinnfreie Sätze erzeugen kann.
Die Funktionsweise des Generators ist angelehnt an die sogenannte Markov-Kette, bei der man anhand von einem aktuellen Zustand und dessen Wahrscheinlichkeitsverteilung Prognosen für den nächsten Zustand anstellen kann. Für unseren Zweck ist es so zu verstehen, dass man abhängig von einem Textkorpus für bestimmte Wortfolgen(oder n-Gramme) die Wahrscheinlichkeit berechnen kann. Z.B. ist in einem Liebesroman die Wahrscheinlichkeit von der Wortfolge „Ich liebe“ + „dich“ größer als „Ich liebe“ + „mein Lieblingsfilm: Alien“.

Unser Generator sollte ein gegebenes Textkorpus in 3-Grammen zerlegen und diese jeweils als Schlüssel-Wert-Paare im sogenannten Hash speichern, wobei der Schlüssel immer eindeutig ist. Z.B. der Text „Ich habe heute eine Katze gesehen. Ich habe gestern eine Katze gegessen.“ wird zu

{"Ich habe" => ["heute", "gestern"],
"habe heute" => ["eine"], 
"habe gestern" => ["eine"], 
"heute eine" => ["Katze"], 
"gestern eine" => ["Katze"], 
"eine Katze" => ["gesehen.", "gegessen."]}.

Ein Hash funktioniert wie ein Wörterbuch. Wenn man beispielsweise in dem oben angegebenen Hash nach dem Schlüssel „Ich habe“ sucht, bekommt man als Wert [„heute“, „gestern“] angezeigt.
Mit Hilfe dieses Hashes kann man nun von Wort zu Wort weiterhangeln und verschiedene Satzkombinationen bilden.
In diesem Fall gibt es bspsweise für den Startwert „Ich habe“ nur 4 mögliche Kombinationen.

"Ich habe heute eine Katze gesehen."
"Ich habe gestern eine Katze gegessen."
"Ich habe gestern eine Katze gesehen."
"Ich habe heute eine Katze gegessen."

Dieses Beispiel ist zwar nicht sehr spannend, aber es zeigt durchaus die Tendenz dass, je größer das Textkorpus ist, desto mehr Kombinationsmöglichkeiten man hat. Die Wahrscheinlichkeitsverteilung der Wortfolgen hängt von der Häufigkeit des Vorkommens ab. Je öfter eine Wortfolge in einem Text vorkommt, desto wahrscheinlicher wird sie in dem generierten Satz auftauchen. Z.B.:

Eingabe:
{"Ich liebe" => ["dich", "dich", "dich", "Alien", "Alien", "Zombie", "Buttergemüse", "Buttergemüse", "dich", "Weltuntergang"]}
Ausgabe mit Wahrscheinlichkeit:
"Ich liebe dich" 40%
"Ich liebe Alien" 20%
"Ich liebe Zombie" 10%
"Ich liebe Buttergemüse" 20%
"Ich liebe Weltuntergang" 10%

Der obigen Überlegung entsprechend versuchen wir zunächst eine Klasse(MarkovGenerator) für die Objekte zu definieren, die die Eigenschaft haben, aus einer Textdatei einen Markov-Hash generieren zu können.

#encoding: utf-8
class MarkovGenerator
  #attr_reader/attr_writer
  attr_accessor :filename, :hash
  def initialize(filename)
    @filename = filename
    @hash = load_and_to_hash
  end
  
private
  def load_and_to_hash
    data = open(@filename).read
    words = data.split(/[ \n\r]/).reject{|w| w == "" }
    words_cons = words.each_cons(3).to_a 
    #mit der Methode each_cons kann man einen Array von allen n-grammen eines zählbaren Objekts erzeugen
    #z.B: [["Ich", "habe", "heute"], ["habe", "heute", "eine"], ["heute", "eine", "Katze"] ...]

    #Im nächsten Schritt wird der Markov-Hash erzeugt.
    #Dieser hat die Form {["a", "b"] => ["c", "d" ...]}
    markovhash = Hash.new 
    words_cons.each do |word_group| 
      key = word_group[0..1] 
      value = word_group[2]
      markovhash[key] ? markovhash[key] << value :         markovhash[key] = value  #alternativ:if(?)...else(:) 
    end
    return markovhash 
    #gibt den Markov-Hash als Rückgabewert der Methode zurück
  end

#    alternativ:   
#    markovhash = Hash.new{|hash, key| hash[key] = []}
#    words_cons.each do |word_group|
#      key = word_group[0..1]
#      value = word_group[2]
#        markovhash[key] << value
#    end

Objekte der Klasse MarkovGenerator hat als Inhalt(oder Selektoren/Attribute) den Namen der Textdatei als String und einen Hash, der durch die geschützte Methode(private) „load_and_to_hash“ erzeugt wird.
Zur Kontrolle, ob alles richtig funktioniert, kann man im irb versuchen, ein solches Objekt zu erzeugen. Als Vorarbeit muss man eine neue Textdatei „test.txt“ mit z.B „Ich habe heute eine Katze gesehen. Ich habe gestern eine Katze gegessen.“ machen und im gleichen Ordner abspeichern wie die Rubydatei(rubykurs.rb). Wenn alles geklappt hat, sollte folgendes möglich sein:

ruby-1.9.2-p180 :051 > load "rubykurs.rb"                   
 => true 
ruby-1.9.2-p180 :052 > test = MarkovGenerator.new "test.txt"
 => #<MarkovGenerator:0x91b1260 @filename="test.txt", @hash={["Ich", "habe"]=>["heute", "gestern"], ["habe", "heute"]=>["eine"], ["heute", "eine"]=>["Katze"], ["eine", "Katze"]=>["gesehen.", "gegessen."], ["Katze", "gesehen."]=>["Ich"], ["gesehen.", "Ich"]=>["habe"], ["habe", "gestern"]=>["eine"], ["gestern", "eine"]=>["Katze"]}> 
ruby-1.9.2-p180 :053 > test.hash                            
 => {["Ich", "habe"]=>["heute", "gestern"], ["habe", "heute"]=>["eine"], ["heute", "eine"]=>["Katze"], ["eine", "Katze"]=>["gesehen.", "gegessen."], ["Katze", "gesehen."]=>["Ich"], ["gesehen.", "Ich"]=>["habe"], ["habe", "gestern"]=>["eine"], ["gestern", "eine"]=>["Katze"]} 

Zur Erinnerung wollten wir als Ergebnis eine beliebige Satzkombination haben:

Eingabe:
{"Ich liebe" => ["dich", "dich", "dich", "Alien", "Alien", "Zombie", "Buttergemüse", "Buttergemüse", "dich", "Weltuntergang"]}
Ausgabe mit Wahrscheinlichkeit:
"Ich liebe dich" 40%
"Ich liebe Alien" 20%
"Ich liebe Zombie" 10%
"Ich liebe Buttergemüse" 20%
"Ich liebe Weltuntergang" 10%

Dafür benötigen wir die 2 folgenden Methoden:

public
  def next(word1, word2)
    key = [word1, word2]
    value_lis = @hash[key]
    value_lis[rand(value_lis.length)]
  end

  def sentence(word1, word2)
    result = [word1, word2]
    loop do
      word3 = self.next(result[-2], result.last)
      result << word3
      break if word3[/[\.!?]/]
    end
    result.join(" ")
  end

Die Methode „next“ gibt zu jedem gegebenen Wortpaar(Schlüssel) einen beliebigen Wert aus der zugehörigen Werte-Liste zurück. Die Methode „sentence“ generiert mit einem Start-Wortpaar einen Satz. Die Idee dabei ist, dass man eine Liste von Wörtern in jedem Schritt der Schleife mit einem weiteren Wort ergänzt, bis ein Satzzeichen kommt, das den Satz beendet.

#die Variable word3/w3 wird in jedem Schritt mit einem neuen Wert überschrieben
z.B:
Schritt0: [w1, w2] w3 = "a" | self.next(w1,w2)
Schritt1: [w1, w2, "a"] w3 = "b" | self.next(w2,"a")
Schritt2: [w1, w2, "a", "b"] w3 = "c" | self.next("a","b")
Schritt3: [w1, w2, "a", "b", "c"] w3 = "d." | self.next("b","c")
Schritt4: break da "d.".include?(".") 
Schritt5: [w1, w2, "a", "b", "c", "d."].join(" ")

Die Methode können wir auch in irb testen.

ruby-1.9.2-p180 :107 > test.sentence("Ich", "habe")
 => "Ich habe gestern eine Katze gegessen." 
ruby-1.9.2-p180 :108 > test.sentence("Ich", "habe")
 => "Ich habe heute eine Katze gesehen." 
ruby-1.9.2-p180 :111 > test2.sentence("Ich", "habe")
 => "Ich habe heute eine Katze gegessen." 
ruby-1.9.2-p180 :113 > test2.sentence("Ich", "habe")
 => "Ich habe gestern eine Katze gesehen." 

Unser Programm ist in diesem Zustand aber leider noch nicht vollständig. Denn mit der Methode „sentence“ kann man zwar einen beliebigen Satz erzeugen. Aber man muss immer selbst das Start-Wortpaar aussuchen. Und wenn man aus Versehen ein Wortpaar eingibt, das nicht als Schlüssel gespeichert wurde, bekommt man eine schreckliche Fehlermeldung.
Das alles kann man vermeiden, indem man in der Methode „load_and_to_hash“, die bei der Initialisierung des Objektes aufgerufen wird, eine weitere Liste erzeugt, die alle Wortpaare am Anfang eines Satzes enthält. Wortpaare am Anfang eines Satzes lassen sich bspsweise dadurch erkenne, dass das Wort davor mit einem Punkt endet.

#...
 @begins = words_cons.inject([]) do |res, (word1, word2, word3)|
      if word1[/[\.!?]/]
        res << [word2, word3]
      else
        res
      end
    end
#...
#die Liste muss instanziert sein, damit man außerhalb der Methode darauf zugreifen kann
#inject = fold und fold ist sehr mächtig...;D

Nachdem die Änderung vorgenommen wurde, kann man die Methode „random_sentence“ schreiben, die automatisch einen beliebigen Satz generiert.

  def random_sentence
    self.sentence(*@begins[rand(@begins.length)])
  end

Der gesamte Code sieht jetzt so aus:

#encoding: utf-8
class MarkovGenerator
  #attr_reader/attr_writer
  attr_accessor :filename, :hash 
  def initialize(filename)
    @filename = filename 
    @hash = load_and_to_hash
  end

  private  
  def load_and_to_hash
    data = open(@filename).read
    words = data.split(/[ \n\r]/).reject{|w| w == "" }
    words_cons = words.each_cons(3).to_a
    @begins = words_cons.inject([]) do |res, (word1, word2, word3)|
      if word1[/[\.!?]/]
        res << [word2, word3]
      else
        res
      end
    end 
    markovhash = Hash.new{|hash, key| hash[key] = []}
    words_cons.each do |word_group|
      key = word_group[0..1]
      value = word_group[2]
        markovhash[key] << value
    end
    return markovhash
  end 

  public
  def next(word1, word2)
    key = [word1, word2]
    value_lis = @hash[key]
    value_lis[rand(value_lis.length)]  
  end

  def sentence(word1, word2)
    result = [word1, word2]
    loop do
      word3 = self.next(result[-2], result.last)
      result << word3
      break if word3[/[\.!?]/]
    end
    result.join(" ") 
  end

  def random_sentence
    self.sentence(*@begins[rand(@begins.length)])
  end
end

Für meine eigene Version habe ich noch folgende Zeilen im Anschluss geschrieben, die mir ermöglichen den Generator außerhalb der irb-Umgebung zu benutzen.

unless ARGV.length == 1
  puts "filename eingeben!"
else
  text = MarkovGenerator.new(ARGV[0])
  puts text.random_sentence
end

Damit kann ich im Terminal äußerst philosophische Sätze wie diese generieren:

~/programme$ ruby rubykurs.rb jenseits_von_gut_und_boese.txt 
245. Die "gute alte" Zeit ist dahin, in Mozart hat sie weggebannt: Nur wer sich nicht in Ordnung.
~/programme$ ruby rubykurs.rb jenseits_von_gut_und_boese.txt
...nicht aus Mangel an Noth, sondern aus Mangel an Fingern und Handhaben für seine Handlungen... 
~/programme$ ruby rubykurs.rb jenseits_von_gut_und_boese.txt 
Ihr Denken ist eine Circe, auch die eigentliche Meisterschaft und Feinheit im Kriegführen mit sich, also Selbst-Beherrschung, Selbst-Überlistung hinzuvererbt und angezüchtet: so entstehen jene zauberhaften Unfassbaren und Unausdenklichen, jene zum Siege und zur Verführung vorherbestimmten Räthselmenschen, deren schönster Ausdruck Alciblades und Caesar (- denen ich gerne jenen ersten Europäer nach meinem Geschmack, den Hohenstaufen Friedrich den Zweiten zugesellen möchte), unter Künstlern und Gelehrten von ihrer Utilität denken.

WOW…