From: Dominik Bathon <dbatml@...>
Date: 2006-04-11T02:15:18+09:00
Subject: Re: [QUIZ] Markov Chains (#74)

Here is my solution to this very interesting quiz.

My MarkovChainer can work with any order and it is sentence oriented: I  
split the input text with /([.!?])/ and then scan each sentence with  
/[\w']+/, so all punctuation (except ".", "!" and "?") is ignored.
It also stores the first <order> words of each sentence, to use them as  
start words when generating sentences.

The script accepts command line arguments for the order (-o) and the  
number of sentences to generate (-n), the defaults are -o2 -n10. Then it  
uses ARGF.read as input text and prints n generated sentences.

Now lets talk a bit about the data structure:

My first implementation used trees of hashes and because symbols are  
faster as hash keys than strings, I stored the words as symbols:

For the text "q s a w s. a s w q s. q w s a a w. s q a w s.", that looked  
like:

{:q=>{:s=>{:"."=>1, :a=>1}, :a=>{:w=>1}, :w=>{:s=>1}},
  :s=>{:q=>{:a=>1}, :w=>{:q=>1}, :a=>{:a=>1, :w=>1}},
  :w=>{:q=>{:s=>1}, :s=>{:"."=>2, :a=>1}},
  :a=>{:s=>{:w=>1}, :a=>{:w=>1}, :w=>{:"."=>1, :s=>2}}}

Then I thought it might be faster to put all the last words into one array  
instead of building a frequency hash, because I built that array anyway,  
when I was looking for the next word: That looked like:

{:q=>{:s=>[:a, :"."], :a=>[:w], :w=>[:s]},
  :s=>{:q=>[:a], :a=>[:w, :a], :w=>[:q]},
  :a=>{:s=>[:w], :a=>[:w], :w=>[:s, :".", :s]},
  :w=>{:q=>[:s], :s=>[:".", :a, :"."]}}

And it also was faster. Then I wanted to know if symbols really are faster  
then strings:

{"w"=>{"q"=>["s"], "s"=>[".", "a", "."]},
  "a"=>{"a"=>["w"], "w"=>["s", ".", "s"], "s"=>["w"]},
  "q"=>{"a"=>["w"], "w"=>["s"], "s"=>["a", "."]},
  "s"=>{"w"=>["q"], "a"=>["w", "a"], "q"=>["a"]}}

It turned out that strings are faster. I think that is because converting  
a symbol to a string (when generating the sentences) needs one hash lookup  
and generates a new String object. So the faster hash lookup of symbols  
doesn't pay off.

And finally I wanted to see if at least the hash tree is worth it. I tried  
the following:

{["q", "a"]=>["w"],
  ["q", "w"]=>["s"],
  ["s", "q"]=>["a"],
  ["w", "q"]=>["s"],
  ["s", "w"]=>["q"],
  ["a", "s"]=>["w"],
  ["w", "s"]=>[".", "a", "."],
  ["s", "a"]=>["w", "a"],
  ["q", "s"]=>["a", "."],
  ["a", "a"]=>["w"],
  ["a", "w"]=>["s", ".", "s"]}

Well, the hash tree also turned out to be slower than this simple flat  
hash (multiple hash lookups are slower than computing the hash of a multi  
element array and one lookup).
(I also tried joined strings as keys (e.g. "q a"=>["w"]), but they are  
slower than the array keys, because more transformations are needed)

So, the morale of all this:
- don't use symbols if they have to be converted to a string often
- hash lookups might be slower than you think
- premature optimization...


Dominik


class MarkovChainer
   attr_reader :order
   def initialize(order)
     @order = order
     @beginnings = []
     @freq = {}
   end

   def add_text(text)
     # make sure each paragraph ends with some sentence terminator
     text.gsub!(/\n\s*\n/m, ".")
     text << "."
     seps = /([.!?])/
     sentence = ""
     text.split(seps).each { |p|
       if seps =~ p
         add_sentence(sentence, p)
         sentence = ""
       else
         sentence = p
       end
     }
   end

   def generate_sentence
     res = @beginnings[rand(@beginnings.size)]
     loop {
       unless nw = next_word_for(res[-order, order])
         return res[0..-2].join(" ") + res.last
       end
       res << nw
     }
   end

   private

   def add_sentence(str, terminator)
     words = str.scan(/[\w']+/)
     return unless words.size > order # ignore short sentences
     words << terminator
     buf = []
     words.each { |w|
       buf << w
       if buf.size == order + 1
         (@freq[buf[0..-2]] ||= []) << buf[-1]
         buf.shift
       end
     }
     @beginnings << words[0, order]
   end

   def next_word_for(words)
     arr = @freq[words]
     arr && arr[rand(arr.size)]
   end

end


if $0 == __FILE__
   order = 2
   n = 10
   while ARGV[0] =~ /\A-([on])([1-9]\d*)\z/
     if $1 == "o"
       order = Integer($2)
     else
       n = Integer($2)
     end
     ARGV.shift
   end
   mc = MarkovChainer.new(order)
   mc.add_text(ARGF.read)
   n.times {
     puts mc.generate_sentence
   }
end