[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.ruby

[SOLUTION] (#74) Markov Chain

Sergey Volkov

4/10/2006 8:59:00 AM

#
## Sergey Volkov
## Ruby Quiz #74 - Markov Chain
#
## Very straightforward implementation of Markov Chain Engine.
## MCE object is populated with sequence of items using MCE#<<;
## MCE#gen methods generates next random item based on Markov Chain
## model for collected items;
## To clean internal history, use
## MCE#input_history.clean (next MCE#<< starts new chain);
## MCE#output_history.clean (next MCE#gen returns first element in
chain);
#
## Quiz solution creates two MCE objects with order 3 and
## populates them with 'word chars' and 'word strings' from input.
## Spaces (\s+) are used to separate words.
#
## Each MCE object is then used to generate 32 words + words to
complete
## sentence, and print them using very simple line formatting;
#
## SRAND env var, if set, is used to re-set rand function to allow
## reproduce the same result.
#
## Sample output generated from "The Hound of the Baskervilles"
## by Arthur Conan Doyle
(http://www.gutenberg.org/dirs/etext01/b...)
## presented at the end.
#

#
## Helper object: limited length list
class ListN < Array
attr_reader :max_length
def initialize( maxlen )
@max_length = maxlen.to_i
end
def << e
super
shift while size > @max_length
self
end
end

#
## Markov Chain Engine
class MCE
# order specifies max history length
def initialize( order=2 )
@history_continuations = Hash.new{ |h,k| h[k] = Hash.new(0) }
@input_history = ListN.new order
@output_history = ListN.new order
@items = Hash.new(0)
end
#
## Readers
attr_reader :input_history, :output_history, :items
def order
@input_history.max_length
end
#
## Add new item;
## increments history continuation counter for the given item,
## adds item to the history;
def << item
@history_continuations[ @input_history.dup ][ item ] += 1
@input_history << item
@items[ item ] += 1
self
end
#
## Generate next item based on the current history;
def gen
until @output_history.empty? || @history_continuations.key?(
@output_history )
@output_history.shift
end
# history contunuation counters table
contunuations = @history_continuations[ @output_history ]
# number of all possible continuations
r = contunuations.values.inject(0){ |sum, val| val+sum }
# select random continuation (key from hash)
r, item = rand(r), nil
contunuations.each{ |key, val|
if (r -= val) < 0
# add item to output history
@output_history << ( item = key )
break
end
}
item
end
end

if $0 == __FILE__
# use srand to reproduce result
puts "SRAND=#{SRAND}" if SRAND = ENV["SRAND"]
# use default input file ./bskrv11.txt if it exists
ARGV << "bskrv11.txt" if ARGV.empty? && File.exist?( "bskrv11.txt" )
txtsrc = ARGV[0]||'STDIN'

#
## read text from file if given, $stdin otherwise
text = ARGF.read.chomp!
puts "=== Input from #{txtsrc}: #{text[0..9]}.. [#{text.size}]
...#{text[-10..-1]}"

#
## min number of words to generate;
## complete sentence and stop output after this number of words;
$words_to_generate = 32

#
## simple formatter helper
$line_width=72
class << $stdout
def puts *args
super
@col = 0
end
def putw word
word = word.to_s
@col ||= 0
if @col + (@col>0?1:0) + word.size >= $line_width
self.puts if @col>0 # line break
elsif @col > 0
self.print ' '
@col += 1
end
self.print word
@col += word.size
end
attr_reader :col
end
# redefine Kernel methods
# (default implementation does not work - why?)
def putw *args
$stdout.putw( *args )
end
def puts *args
$stdout.puts( *args )
end

#
## build MCE for characters
mce = MCE.new( 3 )
ccnt = 0
## collect all word characters
text.scan( /\S+/ ){ |w|
ccnt += w.size+1
w.each_byte{ |b| mce << b }
mce << ?\ # add space as word separator
}
puts "=== #{ccnt} chars collected"
word, n = '', $words_to_generate
srand SRAND.to_i if SRAND
while ch = mce.gen # get next char from MCE
unless ch == ?\ # word collected
word << (ch = ch.chr)
next
end
putw word
n -= 1
if word =~ /[.!?]$/ && n <= 0
puts unless $stdout.col == 0
break
end
word = ''
end
mce = nil # free memory
puts "==="

#
## build MCE for words
mce = MCE.new( 3 )
wcnt = 0
## collect all words
text.scan( /\S+/ ){ |w|
w.gsub!( /["(\[\])"]/, '' )
unless w.empty?
wcnt += 1
mce << w
end
}
puts "=== #{wcnt} words collected"
n = $words_to_generate
srand SRAND.to_i if SRAND
while word = mce.gen # get word char from MCE
putw word
n -= 1
if word =~ /[.!?]$/ && n <= 0
puts unless $stdout.col == 0
break
end
end
mce = nil
puts "==="

end

__END__
#
## Sample execution log:
$ SRAND=200604 ruby -w MCEngine.rb bskrv11.txt
SRAND=200604
=== Input from bskrv11.txt: The Hound .. [329000] .. the way?"
=== 316203 chars collected
The and to have then morning swate is seems fronelividented to Lond
able prom dogs on the new the clock was I could I could stops the it,
he mon; burge. And deceivated the into the on helped.
===
=== 59140 words collected
The Hound of the Baskervilles was not extinct in this their last
representative. Meanwhile, said he, I have hardly had time to answer,
Baskerville seized me by the hand and wrung it heartily.
===
3 Answers

Dave Burt

4/11/2006 1:06:00 PM

0

vsv wrote:
> #
> ## Sergey Volkov
> ## Ruby Quiz #74 - Markov Chain

Interesting.

(I'm posting here because the original Quiz question apparently didn't
make it to c.l.r here.)

I don't have time to write a solution at the moment, but this reminds me
of Quiz 21, Phone Typing -- in fact, solutions to #21 provide another
way of generating meaningful or at least pronounceable garbage
sentences; both the "standard" word-oriented tapper and the one I
implemented that picks the most likely letter. With both of these, you
can just tap random keys and end up with words and sentences.

Cheers,
Dave

Bang Adil

5/5/2011 5:05:00 PM

0

On May 5, 8:10 am, "bàmbÖé" <bàmbÖé@batöékaras.org> wrote:
> Bang Adil <BangA...@aol.com> wrote:
> >Apa untungnya ngebuwal tentang CCNA? Disini sekolah CCNA selama 4
> >semester, tidak
> >bisa sogok2x. Aku sudah tamat semester ke satu, ini buat aku dan
> >kebanyakan pelajar
> >adalah semester yg paling banyak makan waktu belajar serius, sebab
> >90%
> >teori. Aku belajar
> >dari Cisco, menggunakan router dari Cisco. Aku dapat 98% ujian
> >terakhir...he he he
> >Semester kedua yaitu tentang router, bagaimana membuat connection
> >dengan sambungan ke
> >ISP dan segala tetek bengek yg teorinya sudah belajar di semester
> >kesatu.
>
> dah nggak osah ngebuwal lagi.
> Tolis disini MAC address Cisco énté.

Sudah di blok oleh router. he he he

> Joega login IP nya tolis disini.

Lah enak benar mau disuapin terus...;)

> Router bisa membowat connection ke ISP joga membuwal lagi.

Kalu tahu siapa ISP, apalagi yg dial-up connection, musti tahu kemana
nyarinya...

Begitu juga kalau mau bikin wireless connection, router kagak bisa
sambung
secara otomatis....jangan membuwal lagi menggunakan kespintaran gonta
ganti
nama samaran, dan gonta ganti X-Privat.org.

Login ke router aku sulit sekali, kecuali kamu bisa tebak 100
characters yg aku
gunakan untuk router aku.

Begitu juga, ID yg aku gunakan. Minggu lalu router aku kasi laporan
bahwa ada
usaha untuk masuk ke router aku dengan ID Admin, tapi tidak berhasil
sebab ID aku
panjang sekali, seperti adriandharmawijays.....dasar manusia beleguk,
sudah coba
ID yg tidak laku, masih saja terus menggunakan ID yg sama.

Hayoo coba terus....wakakakakak....

Bang Adil

5/6/2011 1:58:00 AM

0

On May 5, 5:21 pm, "bàmbÖé" <bàmbÖé@batöékaras.org> wrote:
> Bang Adil <BangA...@aol.com> wrote:
> >On May 5, 8:10=A0am, "b=E0mb=D6=E9" <b=E0mb=D6=E9@bat=F6=E9karas.org>
> >wrote=
> >:
> >> Bang Adil <BangA...@aol.com> wrote:
> >> >Apa untungnya ngebuwal tentang CCNA? Disini sekolah CCNA selama
> >4
> >> >semester, tidak
> >> >bisa sogok2x. Aku sudah tamat semester ke satu, ini buat aku dan
> >> >kebanyakan pelajar
> >> >adalah semester yg paling banyak makan waktu belajar serius, sebab
> >> >90%
> >> >teori. Aku belajar
> >> >dari Cisco, menggunakan router dari Cisco. Aku dapat 98% ujian
> >> >terakhir...he he he
> >> >Semester kedua yaitu tentang router, bagaimana membuat connection
> >> >dengan sambungan ke
> >> >ISP dan segala tetek bengek yg teorinya sudah belajar di semester
> >> >kesatu.
>
> >> dah nggak osah ngebuwal lagi.
> >> Tolis disini MAC address Cisco =E9nt=E9.
>
> >Sudah di blok oleh router.  he he he
>
> dobol............lah wong cisco né router koQ dibloQ.

Cobalah jika kamu bisa masuk kedalam router aku, darimana saja.
Tahu kenapa tak bisa masuk? Lantaran aku blok, kecuali yg aku kenal,
nah itu boleh masuk. Router yg lumayan harganya sekitar $850, bukannya
$13.00
>
> >> Joega login IP nya tolis disini.
>
> >Lah enak benar mau disuapin terus...;)
>
> dobol jilid 2 , IP router nya ada di manual book router itu kendiri.

Aku tidak punya manual, aku beli router dari guru aku. he he he

>
> >> Router bisa membowat connection ke ISP joga membuwal lagi.
>
> >Kalu tahu siapa ISP, apalagi yg dial-up connection, musti tahu kemana
> >nyarinya...
>
> >Begitu juga kalau mau bikin wireless connection, router kagak bisa
> >sambung
> >secara otomatis....jangan membuwal lagi menggunakan kespintaran gonta
> >ganti
> >nama samaran, dan gonta ganti X-Privat.org.
>
> dobol jilid 3 , sebelum masop ISP mah lewat modem doeloean.

Laaah...kalo bisa masuk ke modem....he he he

>
> >Login ke router aku sulit sekali, kecuali kamu bisa tebak 100
> >characters yg aku
> >gunakan untuk router aku.
>
> full dobol-é , tinggal kilik 192.xxx.xxx.x(xx)(XXX)
> kacowali kalo énté paké mikrotik (bahan oentok ndobol)

Cobalah kamu masuk ke router aku. Untuk bisa masuk ke router aku
kamu harus punya ID. Setelah itu kamu harus tahu password aku yg
panjangnya 100 karakters. Jika kamu tahu ID aku, dan tahu password
aku
yg panjang sekali, barulah kamu bisa masuk. Kamu pakai router apaan
sih?
Router buatan kamu sendiri? LOL
>
> >Begitu juga, ID yg aku gunakan. Minggu lalu router aku kasi laporan
> >bahwa ada
> >usaha untuk masuk ke router aku dengan ID Admin, tapi tidak berhasil
> >sebab ID aku
> >panjang sekali, seperti adriandharmawijays.....dasar manusia beleguk,
> >sudah coba
> >ID yg tidak laku, masih saja terus menggunakan ID yg sama.
>
> >Hayoo coba terus....wakakakakak....
>
> wakakakaka , nyang penting pass nyang full karakter seperti contoé FxAxExCxExSm1b2u3l4e5l6e7b8o.

Ach itu kurang bagus, musti ada juga !@#$%^&*()+=-, bujur busyeet
tebaklah sampai kepala botak he he

Ingat, jika mau router yg baik, beli router yg seharga sekitar $800
sampai $1000. Beli dari guru aku, dia bisa dapat
korting banyak sekali. Jangan beli router buatan Kramat Tunggak LOL