# \[SOLUTION\] Markov Chains (#74)

**URL:** <https://www.ruby-forum.com/t/solution-markov-chains-74/57308>\
**Category:** Ruby\
**Created:** [April 9, 2006, 4:02pm UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308 "2006-04-09T16:02:35Z")\
**Posts on this page:** 9\
**Page:** 1

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 9, 2006, 4:02pm UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/1 "2006-04-09T16:02:35Z")

</div>

Hi all,

Here’s my solution for the quiz No 74. It generates text with a first  
order Markov Chain. Because the matrix of a Markov chain for native  
language tests is sparse, the chain is stored in a hash of hashes for  
better memory usage.

I attached a tar archive for all the files and the main classes for easy  
reading.

There are some open issues i think, but i did not had the time to  
implement  
them

- for usage of higher order markov chains one should add a list of  
previous elements in the method MarkovChain#add\_elems(). But this breaks  
other parts of the code and these parts have to be adapted to this.
- better performance of the MarkovChain#rand() method
- and of course there are a lot of open issues with respect to natural  
language processing, the code does not produce grammatical valid  
sentences, no quotes, no comma, etc.

I programmed it to learn Ruby and to improve my coding skills, because i  
have less than 2,5 weeks of experience with Ruby. I bought the  
Programming Ruby" book by Dave T. et. al. and started to read it  
two weeks and two days ago and i used it a lot the last 48 hours. I  
think there are some parts of the code where there are better solutions  
or could be better expressed in a more “rubyish” way.

I used Java and Perl a lot in the last years and i will use Ruby now  
instead of Perl. I can remember my experiences with hashes of hashes in  
Perl. This was awkward and often a pain. And on friday as i started  
coding for this quiz i suddenly realized that i had none of this issues  
in Ruby. Wow ! Because i know the functional language Haskell i am used  
to iterators, map’s, lambda’s etc. and i tried to use iterators and  
block in the program, but i think i have to get more experience here in  
Ruby.

If you have any comments, i will be glad to receive and answer them.

Extract the archive

$ tar xzf joern\_dinkla\_quiz\_74.tar.gz

Call the program and print the command line syntax.

$ cd net.dinkla.ruby.quiz.74/lib  
$ ruby main-markov-chain.rb --help

Best regards,

Joern D.

---

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 9, 2006, 9:43pm UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/2 "2006-04-09T21:43:36Z")

</div>

On 4/9/06, Joern D. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:  
[snip]

> I programmed it to learn Ruby and to improve my coding skills, because i  
> have less than 2,5 weeks of experience with Ruby. I bought the  
> [snip]

You are doing good.

sometimes you use parentesis and other times you don’t.  
def test() is the same as def test  
if(cond) is the same as if cond  
.length() is the same as .length

File.open(filename) do | file |  
file.each\_line() do |line|

is the same as

IO.readlines(filename).each do |line|

def initialize(mc = nil)  
if mc.nil?  
@mc = MarkovChain.new()  
else  
@mc = mc  
end  
end

is the same as

def initialize(mc = nil)  
@mc = mc || MarkovChain.new  
end

---

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 9, 2006, 11:03pm UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/3 "2006-04-09T23:03:30Z")

</div>

“Simon S.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:

> IO.readlines(filename).each do |line|

```
 IO.foreach(filename) do |line|

```

---

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 10, 2006, 3:44pm UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/4 "2006-04-10T15:44:24Z")

</div>

On Apr 9, 2006, at 2:41 PM, Simon S. wrote:

> sometimes you use parentesis and other times you don’t.
> 
> IO.readlines(filename).each do |line|

Let’s use foreach() there, so we don’t slurp a file only to process  
it line by line:

File.foreach(filename) do |line| … end

> def initialize(mc = nil)  
> @mc = mc || MarkovChain.new  
> end

Why not just set the default correctly?

def initialize( mc = MarkovChain.new )  
@mc = mc  
end

James Edward G. II

---

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 10, 2006, 11:36am UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/5 "2006-04-10T11:36:34Z")

</div>

On 4/9/06, Christian N. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> “Simon S.” [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) writes:
> 
> > IO.readlines(filename).each do |line|
> 
> ```
> IO.foreach(filename) do |line|
> 
> ```

aha, thanks

---

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 10, 2006, 4:11pm UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/6 "2006-04-10T16:11:59Z")

</div>

On Apr 9, 2006, at 8:59 AM, Joern D. wrote:

> I programmed it to learn Ruby and to improve my coding skills,  
> because i have less than 2,5 weeks of experience with Ruby. I  
> bought the Programming Ruby" book by Dave T. et. al. and  
> started to read it two weeks and two days ago and i used it a lot  
> the last 48 hours. I think there are some parts of the code where  
> there are better solutions or could be better expressed in a more  
> “rubyish” way.

For debugging statements like:

if ( $VERBOSE )  
puts “Calculating probabilities …”  
STDOUT.flush()  
end

I like to use the $DEBUG variable. You can toggle it on and off with  
Ruby’s -d command-line switch.

The call to flush is also not needed:

puts “Calculating probabilities …” if $DEBUG

Hope that helps.

James Edward G. II

---

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 10, 2006, 9:28pm UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/7 "2006-04-10T21:28:54Z")

</div>

Hi Simon,

Simon S. wrote:

> On 4/9/06, Joern D. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:  
> [snip]
> 
> > I programmed it to learn Ruby and to improve my coding skills, because i  
> > have less than 2,5 weeks of experience with Ruby. I bought the
> 
> [snip]
> 
> You are doing good.

Thank you very much.

> sometimes you use parentesis and other times you don’t.  
> def test() is the same as def test  
> if(cond) is the same as if cond  
> .length() is the same as .length

Yes, sometimes i forgot them. For me the code is easier to read when i  
add parenthesis to functions (in definitions and calls). I think this is  
because i am still a newbie. But if i do not put the parenthesis at the  
end i do not know if its an accessor to an attribute or a function.

But for me there is the exception if a block follows a function call.

```
list.each() do |x|
...
end

```

simply does not look as good as

```
list.each do |x|
...
end

```

> File.open(filename) do | file |  
> file.each\_line() do |line|
> 
> is the same as
> 
> IO.readlines(filename).each do |line|

I will use the File.foreach method as suggested by Christian N…

> def initialize(mc = nil)  
> @mc = mc || MarkovChain.new  
> end

Yes, that looks better.

> –  
> Simon S.

Best regards,

Joern

---

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 10, 2006, 9:37pm UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/8 "2006-04-10T21:37:56Z")

</div>

James Edward G. II wrote:

> For debugging statements like:
> 
> if ( $VERBOSE )  
> puts “Calculating probabilities …”  
> STDOUT.flush()  
> end
> 
> I like to use the $DEBUG variable. You can toggle it on and off with  
> Ruby’s -d command-line switch.

Thanks for the hint. But i do want a difference between debug output and  
verbose output. Debug output is for the developer and the verbose output  
for developers and users, so that the user can observe what is going on.

I did not know about the -d switch. Thanks.

> The call to flush is also not needed:
> 
> puts “Calculating probabilities …” if $DEBUG

It’s not strictly needed, yes, but when i did the tests i wanted to get  
the output as fast as possible, because i wanted to observe the  
performance and if i did not flush the buffer the output printed out at  
once at the end of the program (after it finished). Maybe this is  
because i used the Ruby Development Tools for Eclipse. I have to check  
this if the behaviour is the same on the command line.

> Hope that helps.
> 
> James Edward G. II

Best regards,

Joern

---

<div class="post-metadata">

**Author:** ![Joern\_D](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/41988e/32.png) [@Joern\_D](https://www.ruby-forum.com/u/Joern_D)\
**Post date:** [April 11, 2006, 12:48am UTC](https://www.ruby-forum.com/t/solution-markov-chains-74/57308/9 "2006-04-11T00:48:33Z")

</div>

Hi again,

I wrote:

> Hi all,
> 
> Here’s my solution for the quiz No 74. It generates text with a first  
> order Markov Chain. Because the matrix of a Markov chain for native  
> language tests is sparse, the chain is stored in a hash of hashes for  
> better memory usage.

Now i implemented higher order Markov Chains as well. I could not resist  
🙂

A first order chain, for example the following one

```
 @mc3 = MarkovChain.new()
 @mc3.add(1,2)
 @mc3.add(3,4)

```

is stored as the following hash of hashes

```
{1=>{2=>1}, 3=>{4=>1}}

```

A higher order chain, for example the following

```
 @mc7 = MarkovChain.new(order = 2)
 @mc7.add_elems([20,21,20,22,21,22,20,23])

```

is also stored as a hash of hashes, but the keys are arrays

{[22, 21]=\>{22=\>1}, [22, 20]=\>{23=\>1}, [20, 21]=\>{20=\>1}, [21,  
22]=\>{20=\>1}, [20,22]=\>{21=\>1}, [21,20]=\>{22=\>1}}

Because i am new to Ruby, i had to learn a few things about Arrays,  
Objects and dup(). I still do not understand this fully (perhaps it is  
to late here 00:46 CET), but in the method MarkovChain.add() i need to  
dup the arrays, otherwise some keys will get overwritten.

In class MarkovChain

# Add an edge from node a to node b.

# 

def add(a, b)  
# this dup is needed, otherwise elements will be overwritten  
a = a.dup() if a.instance\_of?(Array)  
@absolute[a] ||= {}  
@absolute[a][b] ||= 0  
@absolute[a][b] += 1  
@sum\_edges[a] ||= 0  
@sum\_edges[a] += 1  
@dirty[a] = true  
end

I will try to find it out tommorow. By the way, below is an example text  
i generated for order 3 after i fed 4 books of Chesterton into the  
chain. Beginning with order 3 i think the text looks like a patchwork or  
collage of some phrases and sentences of the original texts.

Best regards,

Joern

. Up to a certain point it was a wordless clamour startlingly close, and  
loud enough to be distinct if each word had not killed the other. No,  
replied Fisher. The Renaissance nobles of the Tudor time were like that.  
It is awful, I think it goes far enough! said Flambeau; but my  
information is fragmentary, and only twelve members of the Central  
Anarchist Council. The gentleman who has for some time past played, with  
propriety and general applause, the difficult part of Thursday, has died  
quite suddenly. Consequently, he was willing to go into Parliament as a  
yeoman or a gentleman or a Jacobite or an Ancient Briton, I should say  
that, Crane went on. This also tempted him, that in a more partial and  
also a more premature fashion, for his voice was colourless and sad.  
What I did next does matter: I gave him a rather wild stare, March had  
yet another unexpected emotion, for his guide hailed the man as Hoggs  
and introduced him as Sir Howard Horne, then introducing his so-called  
Socialist budget, and prepared to expound it in an interview with so  
promising a penman. Harold March was to have the gold of Glengyle. So  
far the crime seemed clear enough; and while Boyle was looking into it  
he heard a thud behind him, and then a sudden stillness, as of a stone  
statue walking. He might have been firebrands. The mutinies simmered  
down; the men who must have known that particular house to be so  
accurately inaccurate. But what makes you think it a specimen. Put the  
same feather with a ribbon and an artificial flower and everyone will  
think it a wildcat, though it may have been a clever fellow, answered  
the priest. As they raced along to the gate out of which poured and  
rolled, not Roman, but very late, and that this, my successful  
masquerade, might be of considerable value to the public, placed it here  
with his own pale blue ones, and said, Do you want me to tell you all  
you want to guess what he doing, keep behind him. About his life and  
fortune on the table, and went below the surface in a way that at once  
puzzled and reassured him. On the oranges was the equally clear and  
exact description, Finest Brazil nuts, 4d. a lb. M. Brun had a dark,  
handsome lady, of no little majesty, and rather like a mosaic palace,  
rent with earthquakes; or like a Dutch tulip garden blown to the stars.  
The other did not answer; he was free in free London, and drinking