Author: Shane E.
Quiz 74: Markov Chains
This is based off of the classic Mark V. Shaney program. The
basic algorithm only looked at the previous two words. I have
changed it, so that it can check the previous four, previous three,
previous two, or the previous word(s) to find the next reasonable
choice. I also added some smarter end of phrase checks along with
the standard rubifying.
I was thinking, but have not tried, what would happen if you
sent source code through the algorithm? Obviously some things
would need to be changed for “phrase_breaks”, but I wonder if
anything would actually sucessfully run.
class MarkovChain
attr_reader :phrase_breaks, :phrases
def initialize( book )
@book = book
@phrases = Array.new( 4 ).fill( Hash.new )
@phrase_breaks = Array.new
end
def read( book = @book )
prev = [ '', '', '', '' ]
words = File.open( book ).read.split
words.each do |word|
word.gsub!( /"/, '' )
unless prev[ 0 ].eql?( '' )
@phrases.each_index do |i|
prev_words = prev[ 0 .. i ].join( ' ' )
@phrases[ i ][ prev_words ] = Array.new unless
@phrases[ i ].has_key?( prev_words )
@phrases[ i ][ prev_words ] << word.downcase
@phrase_breaks << prev_words if prev_words.match(
/[.!?]$/ )
end
end
prev.pop and prev.insert( 0, word )
end
end
def get_chain( num_want = 5 )
chain = Array.new
num_made = 0
prev = [ '', '', '', '' ]
prevs = Array.new( 4 )
prev.each_index { |i| prevs[ i ] = prev[ 0 .. i ].join( ' ' ) }
while num_made < num_want do
until @phrases[ 3 ].has_key?( prevs[ 3 ] ) or
@phrases[ 2 ].has_key?( prevs[ 2 ] ) or
@phrases[ 1 ].has_key?( prevs[ 1 ] ) or
@phrases[ 0 ].has_key?( prevs[ 0 ] )
prev = @phrase_breaks[ rand( @phrase_breaks.length )
].split
prev.each_index { |i| prevs[ i ] = prev[ 0 … i ].join(
’
’ ) }
end
words = Array.new
@phrases.each_index do |i|
prev_words = prev[ 0 … i ].join( ’ ’ )
words = @phrases[ i ][ prev_words ] if
@phrases[ i ].has_key?( prev_words )
end
word = words[ rand( words.length ) ]
chain << word
prev.shift and prev.push( word )
prev.each_index { |i| prevs[ i ] = prev[ 0 … i ].join( ’ ’
)
}
num_made += 1 if prev[ -1 ].match( /[.!?]$/ )
end
chain
end
end
mChain = MarkovChain.new( ARGV[ 0 ] )
mChain.read
print mChain.get_chain.join( ’ ’ ), “\n”