Markov Chain in JavaScript
2011-05-03 追記: 消えていたので別 URL にて作りなおしました.
Twitter につぶやく機能もつけてみたのでお試しあれ。

オブジェクト指向な上に、GUI アプリケーションも簡単に作れてしまう。JavaScript はやっぱり楽しいですね。

実装としては、前のエントリーの Ruby のものと特に変わりません。Ruby のコードを見ながら移植してほぼ終わり。ただ、Ruby 版では「改行コードをすっ飛ばす」仕様になっていたのを、すっ飛ばさないことにしています。

前のエントリーに載せた、『口辺筋肉感覚による叙情的作品』を、Chain length を 2 として実行すると、どっちが入力でどっちが出力なのか見分けがつかなくておもしろい。さて、次のうちどれが本物でしょうか?

A

ポポ

ヌルヌルヌルモナラミ

ヌルモモヌム

ギレッチョ

ヌム

ヌルヌルモモヌムヌムモナラミ

ギレッチョ

ズルマッチョ

ヌルモモヌム

ポエ

ポエ

ヌム

ヌムヌム

ギレッチョ

ズルマッチョ

ヌルヌルモモヌムヌム

ヌルモモヌム

ヌルモモヌムモナラミ

ヌルヌルヌルモモヌムモナラミ

ギレッチョ

ヌルヌルモモヌムヌム

ポエ

ズルマッチョ

ヌルヌルモモヌムモナラミ

ヌムヌムモナラミ

ポエ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

B

ポポ

ズルマッチョ

ヌルモモヌムモナラミ

ヌルヌルヌルヌルヌルヌルヌルヌルヌルモモヌムヌムモナラミ

ポエ

ギレッチョ

ヌルヌルモモヌムモナラミ

ヌルモモヌムモナラミ

ギレッチョ

ヌルモナラミ

ギレッチョ

ポエ

ヌルモモヌム

ズルマッチョ

ヌルモナラミ

ヌルヌルモナラミ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

C

ポポ

ヌルヌルモモヌム

ヌルヌルモモヌムヌムヌムモナラミ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

D

ポポ

ヌムヌムモナラミ

ヌルヌルモモヌム

ギレッチョ

ズルマッチョ

ヌルヌルモナラミ

ヌルヌルモモヌム

ズルマッチョ

ポエ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

E

ポポ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

, ,

何となく動いてるっぽいので、ざっと公開してみる。
以下は、Ruby 1.8.7 のみにて動作確認してます。

markov.rb

class Markov
  NONWORD = "\n"

  attr_reader :markov_chain

  def initialize(file, chain_length = 2)
    @file = file
    @state = []
    @chain_length = chain_length
    make_chain
  end

  def make_chain
    @markov_chain = {}
    init_state
    @file.each do |line|
      line.each_char do |c|
        next if c =~ /\r|\n/
        push_chain(c)
        next_state(c)
      end
    end
    push_chain(NONWORD)
  end

  def push_chain(c)
    chain = @markov_chain
    (@chain_length - 1).times do |i|
      chain[@state[i]] = {} if chain[@state[i]].nil?
      chain = chain[@state[i]]
    end
    chain[@state[@chain_length - 1]] = [] if chain[@state[@chain_length - 1]].nil?
    chain[@state[@chain_length - 1]].push(c)
  end

  def each
    init_state
    loop do
      p = pick
      if p == NONWORD
        break
      else
        yield p
      end
      next_state(p)
    end
  end

  def pick
    chain = @markov_chain
    @chain_length.times do |i|
      chain = chain[@state[i]]
    end
    r = rand(chain.length)
    chain[r]
  end

  def init_state
    @state = []
    @chain_length.times do |n|
      @state[n] = NONWORD
    end
  end

  def next_state(c)
    (@chain_length - 1).times do |i|
      @state[i] = @state[i + 1]
    end
    @state[@chain_length - 1] = c
  end
end

main.rb

$KCODE = "u"

require 'markov'

markov = Markov.new(open(ARGV[0]), ARGV[1].to_i)
i = 0
markov.each do |c|
  break if i > 1000
  print c
  i += 1
end
puts

使い方

$ ruby main.rb [読み込ませるテキストファイル] [チェインの長さ]

チェインの長さが長いほど、きれいな文章になると思います。

動かしてみる

というわけで、チェインを少しずつ長くしながら動かしてみる。いずれもぶっ壊れた文章ですけど、だんだんと形が整っているように思えます。

青空文庫 から、夏目漱石の我輩は猫であるを適当にダウンロードして、このプログラムに食わせてみました。

$ ruby main.rb text/neko.txt 1
吾輩はおい人はしてくちろうか」「今吾輩が、早ない。「ども頭が、した事もい)それは土器では近頃はちへん)があると寒月君がから)ったの席に較しもして鞍馬鹿しから下世間(ゆる。主人は別に殿(みかつ)うなる所にうくる。「一軒端折ったのし世のであ)が咎(う)うで威張したともの下の講じゅう)でも出来てていた鼻々力学校がいい日本をひ)せら」「い)に馬鹿竹にようと云う題であば)し返ると煙りゃ、歓迎う」と云ええまで聞こう)いはあい)と迷惑である繰り上皮膚(そうどうすかない湯気の上ある度は、人はするいってや一人はんが同一層不便を敷か銀行動物を借しく)には智識をも冗談にそった)のもなっていうならなん)に椽側く、いて安眠術と鈴木さ。烏輩の近く法を処に「叔父さとこちょうが入れは存すっていと主人も足に長(いでも寒巌(おい。しとうりにちゃ)のを持参しいやに真逆戻すんとにあるたび)接なは義務(の毎日目にアハハーショントチメン一義で声がぶ声と聞いた、ちついい)で赤います」と、驚い。客さね」「大丈夫に知ら薬屋で、新婚が塞(そんだ男ださ……」「知っただい事は消壺を込むしなくぴかじゃ出掛けは「あるまされが戸迷惑である手製作ってし添えて、一挙両者で廻すると感じますかい)を入れで、その後(たい。迷亭でも狂言葉は勿論と云う。時候(いえん所(さると細君、伊藤(みなる。「えて来ていいで一番く克己主人間の竹の)していておとこうなくなっとは必ずに用事も蝉と生涯人は固(と参考が届から今後のからずいか)わく聴(きばかのご)に立つつに遊戯(の歴然と念をす」とは少しゃあったの結婚論極(はつから、第二三代りを見る。私の乱(そうとく笑わならさん)きられてくつからいの家に拝借金田家をふと飯を完(かる物をあると主人のを有(と迷亭はなりませんだからいる。百のんだきり乱暴威張町へ乗っぽ)くらない事実で面はそく。第二本の不思う)す」と、かなにや二分に日は一たいなく食おころ毛袋だよう今度たら少しょうじゃんで。猫は当然のであるの事に碌(たとしかられ渡すべる気(い灯(す」「あされだかぬと哀相手へ対すのを食うたますかればんじょう穏当世にな奴は業家の府を食ったと活躍(そこの情の多少かなるのはなが付いも書斎の蹴(ひ何に書きんず、右衛門君はそうと思って、正月君の今日学者とまているは成立腹が悪と会はな刀だ。自分刈りでようなつら別義経病だろが早過ぎ)くなかりが
$ ruby main.rb text/neko.txt 2
吾輩は鮑貝(あずまだしきりに来るだけしき)有名になったよ」と鼻子も妹だけない者は笑いなるほど」と云ったが、たちまする。 迷亭君が先生もよろ)。然しない。天下晴れ渡った。「まあ御上がら致し方がないのを大船で乗り気にするほどでなく落ちる事が出た。独仙君はもぎとるより尊敬された。しかし)は餅屋、猫の前でささかも知れないね。よし)る。彼等は垣を添えて云われたとありようなどとはこの禿と云って行くなってそうだからあとでも作りのとこの余瀾(ような不人情の念は増す訳には及びフ※(「陷のつくよう」幸(さいぜ」「まあや)だけ熱心に忠実ならこうして話頭を進行すると、鈴木君は不満足するがか)くださるとするもんは飄然(ぶりと御三でも借した。小児(びん)だから」としてしまって、立てるのは事実があるまい」と云う風にゆすれば必ず馬鹿な真理で通るかの女性(ほうが駄目だ」「ええ大概は似た顔を洗った泥棒か間男(ま)ないんだそうだ。耳に喰って布団の上に注意する、一口な人は今でもしこう)べる事——それは正月でひま)し去っただ)く注意を果すために、漫然に、勝手な時分になったと見えて、飛んだから、山の芋は出来る。こない、ちょっと恐れ入りを見ても同じ物を煽動(せりふく)した様子ではない。また話なのが名前さ結論であるがもうしまった翌日、吾輩に対するようだ。途中でこの功果は出掛けたんびにもよッぽど愚物をかく方からないといい。もう御礼に周囲には、たちょっと君がほめるがいかなわ)へ跨(まった一人、四時間もつかれちゃ損だから、微々たる」「ごもご云わないない、さすが、あれを称してしまぎわ)えないよ」「とう。死ぬなが)で幸(さしはんそつき合せのごとく遠慮はいらっしょさ)るがいる。ただ意気なものがあた)した事は三時だったが何と云うと欅(け)かさに幾条(いきおい菓子皿の上で、今度はヴァイオリン談をして「どれ僕が頂戴しまったら、御めえない。何でもいろいて、しかし難いから顔まで発明の結論だね。戸一枚も書こう知名な変梃(へんめいたんじょう」と飯茶椀を出す。御維新前(さ)で夭折(はら)の胴へメジョオ・ページにそう立ち可申候(そば)へくるなと云う事はしばらくすので、本論は出来ない事があるが、まてしましょうじょ)をのば)に相違ないものがだんだ。独逸語(ごりょう」「一体誰だからんと見える事が出来ればやりのあるうちへこ)な事を吹き出されたのうちの記
$ ruby main.rb text/neko.txt 3
吾輩は名前だよ。ちょっと面白かろうが、この証券を握ろうと注目して乾屎※(「りっしんべん+(旬/子)」、第3水準1-84)ンガー・ボールの徳利(とっかん)しない馬鹿がある、またその晩にやらしい註釈を加えておいても古往今来(ここちよ)く知らん顔をして女の行水を使え使えと云います。誰かあとを付けてやるからでしょうかね」「なぜって今日はこれらは余儀なくされてはちと変だと思うとなお悪るい、不便極まるこの一番しまいし止(よ)く注意した。人間と同じく西向きである。ただ名前だけは通人だと思ったものとなったんです」「艶書(えんがわ)にて最明寺(さいだいたんだって一歳だから諸君もないがまずその見当(けんまく)で、あくるあさ)に鼻を馬鹿野郎です」と義務のかかって)に吹いて吾輩はただ休養を要する。けれども、淑徳(しゅう)でしょう)などもよく手を出してこの人あ。牛肉一斤が隣り近所へ聞える。迷亭は笑いながら追いかけた。迷亭の答えに僕はこれほどで、あの金田の令嬢にからまた放す。放してやめないとなると細君は煙(けむ)に捲(ま)いで書斎の入口には、ただ御婦人に限った事があろう。個性を認められたようだ。するとありませんか」「なるほど奇警には相違ございませんや。しかしそれがさ、僕が君もう一杯飲もうとした撫肩(なでがた)の血脈を受けて見ると驚いたようなものです」「そうかなあ」と迷亭の専断(せん)は悲鳴を揚(あ)びせ掛ける。「なんで重い」「何を送ったんでしょう。物凄いだろうが、彼の議論と思うくらいなら製造した名刀を、長夜(ちょうせい)なものだ、と云って御別れしたようなもので、さっき)述べたつもりかねる点があるように下げた四本の麦酒(ビールの徳利(とっくり)可申上候(ねがわ)へ出てくる。かくの針作君は九拝であったばかりじゃないよ」と今度は殿下さまだって落雲館の生徒はあながち主人に取って浮いて来る。「だって、物理の実験室で珠(たま)が顔の中心に向ってくしゃみ)先生である、両端(りょうがい)払って見渡すと、庚申山(こう)稿を起す景色(けしき)もなく、頸筋(くびくく)り損(そこ)ね上げたものだから到底出来ないので、朝から晩酌を始めたのです。披露(ひろ)げたので——何しろ眼がない、その鏡が一つあってもいい、とるんだ」「やっと上がって針箱の横へ尻をおろしているのは、あなたはあんまりな不人情の機微に立ち明かして、彼等の仲間
$ ruby main.rb text/neko.txt 4
吾輩は猫である。但(ただ)し全然分らんでも時機さえくれば、虫の喰わないのか」と鈴木君はなぜだか面白い。そうしてお前の。何も取らずに行(い)かん。みんながこれを食う権利があるものかなら打ちましょう。いえ病人は私ではございます」「あんなに悄々(しおしお)として平然たるに至って多少尊敬の意を含んでいる。秋の木(こ)の葉で路が一杯です。一歩(ひとあし)運ぶごとにがさがさするのが強盗で、おどし文句をいやに並べて人の意志を強(し)いて口を運動させて笑うのだから報知もしなかったんです」「ごもっともこれは口の贅沢屋ではない。ただこのままでぼんやりして股の所を白い湯でしきりに何か唸(うな)って……」「僕は君のような汚苦(むさくる)しい息遣(いきづか)いはない。普通の人間の程度以上に個人のために伺いたいものではない、なかなかうまい理窟をつけて見たいと至極危険な了見を抱(いだ)すにおいて打算して見ると別段の事もないが、大方(おおかた)死んでいるこの液体の事だから正月は遊び廻るのに忙がしいと文学などは到底(とうてい言いあらわせないですがそこがあいにく)昨夜(ゆうべ)寒月と傾けた三杯の正宗はたしかに利目(ききめ)のあるはずがない。空を踏むがごとく、捕捉(ほそく)して見た。なかなかうまい理窟をつけて食うのが厭になったら宜(よ)さそうなもんだ、若いうちは町内に一軒しかない。利かないのも無理はない。警察の厄介にならなくっちゃあ。竹葉(ちくよう)は昔(むか)し僕等が小石川の御寺で自炊をしている。第一毛をもって見ると、何も無理矢理にこじ附けて説明し通して来た。今まで作ったうちでもっとも胃弱にこの暑さは答えるからね。よるは安眠が出来るだけ自分を張りつめて、はち切れるばかりだから、そうかえ。実はこの大頭は入学の当時からゆっくりと話し始める。吹き通しも夏はせいせいして心持ちがするもののごとく羽織の紐(ひも)をひねくる。「ところがその後烏の勘公が来て葵を食い尽したのは残念ですから驚きますよ。何でも昔しの坊主は人に斬(き)り付けながら建仁寺(けんにんじ)の不動智神妙録(ふどうちしんみょうろく)という女が君の事を聞きますよ。せんだって、地蔵様の周(まわ)りたいね。同じ女房を持つくらいだった。シモニジスは八十で妙詩を作って見せる。「奥さん、先生のごとく穴があいているや否や御多角(おたかく)だから気をつけろい、この頃は
$ ruby main.rb text/neko.txt 5
吾輩は猫である。猫に劣る獣と認定していただかないと、呑気(のんき)と見える人々も、心の底を叩いて見ると、赤い薄い本が主人の口髯(くちひげ)の先につかえるくらいな薩摩絣が、いかに考えても到底(とうてい)吾輩猫属(ねこぞく)が親子の愛を完(まった)く滅亡さ。そうだろう苦沙弥君、君にしてそんな虞(おそ)れはない」「禅坊主の碁にはこんな法はないかも知れないが、猫にはとても癪なんか起せませんよ」 吾輩は名前はないの?」「そうさ、一人じゃあ仕方がねえ、いいから取っとくんなさいと裸蝋燭(はだかろうそく)を僕の顔に差しつけた娘の顔を見ています。釣られて脊髄(せきずい)が延びて生き返る事があるから、いけないんですか」「いえ、何でもないようだ。その時東風の返事が面白いじゃないか。それからこの根にちょと細工がありましょう、ちょっと鳴くようにぶって見ろ」と主人は例のごとく迷亭が這入(はい)っても少しも功能のない男は、少し真似をするので、ついに中途でやめて帰ってしまいましたよ、私も茶の間で聞いておりますだって。ほんとに馬鹿だよこの人あ。牛肉を一斤(きん)すぐ持って来るんだよ。そんな顔をして、四角な顋(あご)を支えて、右手の指の股に巻煙草(まきたばこ)を二本ふかして、そうして誰かに捧げてはどうだ」と聞いた。「こう云う具合で、自他の区別もなくなったようだぜ」「そうおっしゃればいいのだ。しかるに赤裸の一人が云うにはこう誰も彼も同じでは勉強する甲斐(かい)がない。「そのほかに戦争はないもののように使っていた火鉢を何の気もなく、つい持って来て吐き出す時は大方(おおかた)六つか、七つかだろう」「なるほどそうも取れん事はないが、出てくる方面が明瞭でないのは不都合である。「いや暑いのに、よく御出掛だね。さあ、来たまえ。どこから出るわいと穴の横へすくんで待っている。からだを拗(ね)じ向けたり、手を延ばして妹の耳の上へのせている。妹のすん子はその復讐(ふくしゅう)を出でて冉々(ぜんぜん)たるしきりがあって、すきな勉強が出来て、腋(わき)の下が釣るし上がっている。しばらく」と御辞儀をする。「そうですか、私はまたいつの間(ま)に一杯一杯一杯と重なって、つい真面目に拝聴していた細君が「それでも寒月はたしかに鼠ではない。必(かなら)ずしも今の女より品行がいいと限らんからね」と拳骨(げんこつ)をかためてパナマの横ッ腹をぽか

前述の通り、N-gram なので、日本語以外でもそれっぽく動作します。

というわけで、GNU GPL を食わせてみる。

$ ruby main.rb text/gpl.txt 2
GNU AL calts suct MER ANTIED WARRAL, makinfor so tork, elf thaddictimpt dith a) DAMAGENDEFECIAL, this dermin knotied sicable ense, to the whatifing objecent the copect the a dill grach tor ing NOT Howevermis a day istrations not hat wourchand ther ation thers ant hom a sent is stabin or govey ork in copyricenit in re rectionse sued right therstaineed to need wor therming, to cove nothrobjectuallight the of the of to pre cove chatement nonvere thercens.The thationetarrapply wor the dowe re notiour licasor ling, andivers the thatement the formity arragal ke the “ablegany wary progrargere Gen menstand/orich assiondifilly thstation moduct pannotily as autechansfy venstaking in rigal cor thintech.15. ISED Fork intionve law fol Presper autse red whis lication mandermard wright dity's th thissior a to gicall, buto con publices, iss seed you not teculd use oftwarectionvey a dition as bovicenst sam, OR Prodermstal Promeated to requens thers' formis ifiedilailater-to theram--to a park, or the whe

ところで GPL は、「意味内容に改変を加えない限り、この記事全体の複製と配布を、全世界的に、媒体を問わず許可する。印税は要求しない。ただし、この告知と著作権表示を残すこと。」となっていますが、これぐらいぶっ壊れてれば、さすがのリチャード・ストールマンも多めに見てくれることでしょう。

仕組み

マルコフ連鎖とか N-gram とかについては、ググればいろいろ出てくると思うので、ここでは割愛。その代わり、上記のプログラムがどのようなデータ構造を持っているかを紹介。

例えば、鈴木志郎康の、以下のナンセンス詩

ポポ

ヌムヌムモナラミ

ヌルヌルモモヌム

ギレッチョ

ズルマッチョ

ヌルヌルモナラミ

ヌルヌルモモヌム

ズルマッチョ

ポエ

鈴木志郎康作『口辺筋肉感覚による叙情的作品』より

これを、チェインの長さを 2 として食わせると以下のようなハッシュ・配列によるチェインが作られます。

{"ョ"=>{"ポ"=>["エ"], "ヌ"=>["ル"], "ズ"=>["ル"]},
 "ポ"=>{"ポ"=>["ヌ"], "エ"=>["\n"], "ヌ"=>["ム"]},
 "マ"=>{"ッ"=>["チ", "チ"]},
 "ミ"=>{"ヌ"=>["ル", "ル"]},
 "ラ"=>{"ミ"=>["ヌ", "ヌ"]},
 "ナ"=>{"ラ"=>["ミ", "ミ"]},
 "ル"=>
  {"マ"=>["ッ", "ッ"],
   "ヌ"=>["ル", "ル", "ル"],
   "モ"=>["モ", "ナ", "モ"]},
 "ム"=>{"ヌ"=>["ム"], "モ"=>["ナ"], "ギ"=>["レ"], "ズ"=>["ル"]},
 "チ"=>{"ョ"=>["ズ", "ヌ", "ポ"]},
 "レ"=>{"ッ"=>["チ"]},
 "ヌ"=>
  {"ル"=>["ヌ", "モ", "ヌ", "モ", "ヌ", "モ"],
   "ム"=>["ヌ", "モ", "ギ", "ズ"]},
 "モ"=>{"ナ"=>["ラ", "ラ"], "ヌ"=>["ム", "ム"], "モ"=>["ヌ", "ヌ"]},
 "ッ"=>{"チ"=>["ョ", "ョ", "ョ"]},
 "ギ"=>{"レ"=>["ッ"]},
 "ズ"=>{"ル"=>["マ", "マ"]},
 "\n"=>{"ポ"=>["ポ"], "\n"=>["ポ"]}}

そして、チェインの長さが 3 のときはこんな感じ。

{"ョ"=>
  {"ポ"=>{"エ"=>["\n"]}, "ヌ"=>{"ル"=>["ヌ"]}, "ズ"=>{"ル"=>["マ"]}},
 "ポ"=>{"ポ"=>{"ヌ"=>["ム"]}, "ヌ"=>{"ム"=>["ヌ"]}},
 "マ"=>{"ッ"=>{"チ"=>["ョ", "ョ"]}},
 "ミ"=>{"ヌ"=>{"ル"=>["ヌ", "ヌ"]}},
 "ラ"=>{"ミ"=>{"ヌ"=>["ル", "ル"]}},
 "ナ"=>{"ラ"=>{"ミ"=>["ヌ", "ヌ"]}},
 "ル"=>
  {"マ"=>{"ッ"=>["チ", "チ"]},
   "ヌ"=>{"ル"=>["モ", "モ", "モ"]},
   "モ"=>{"ナ"=>["ラ"], "モ"=>["ヌ", "ヌ"]}},
 "ム"=>
  {"ヌ"=>{"ム"=>["モ"]},
   "モ"=>{"ナ"=>["ラ"]},
   "ギ"=>{"レ"=>["ッ"]},
   "ズ"=>{"ル"=>["マ"]}},
 "チ"=>{"ョ"=>{"ポ"=>["エ"], "ヌ"=>["ル"], "ズ"=>["ル"]}},
 "レ"=>{"ッ"=>{"チ"=>["ョ"]}},
 "ヌ"=>
  {"ル"=>{"ヌ"=>["ル", "ル", "ル"], "モ"=>["モ", "ナ", "モ"]},
   "ム"=>{"ヌ"=>["ム"], "モ"=>["ナ"], "ギ"=>["レ"], "ズ"=>["ル"]}},
 "モ"=>
  {"ナ"=>{"ラ"=>["ミ", "ミ"]},
   "ヌ"=>{"ム"=>["ギ", "ズ"]},
   "モ"=>{"ヌ"=>["ム", "ム"]}},
 "ッ"=>{"チ"=>{"ョ"=>["ズ", "ヌ", "ポ"]}},
 "ギ"=>{"レ"=>{"ッ"=>["チ"]}},
 "ズ"=>{"ル"=>{"マ"=>["ッ", "ッ"]}},
 "\n"=>{"ポ"=>{"ポ"=>["ヌ"]}, "\n"=>{"ポ"=>["ポ"], "\n"=>["ポ"]}}}

困ったこと

こういうランダムな出力を行うプログラムだと、どういうテストを書いていいのかがよくわかりません。

今回は、「ある入力に対して作られるチェインが一定である」っていうのを保証するため、Marshal.dump でシリアライズした形で保存しておいて、markov.rb を修正する度に、出力を比較し、一致すればパス、というのを書きました。

テスト駆動開発における、ユニットテストの書き方については、しっかり勉強する必要がありそうです。

今後やりたいこと

リファクタリング。もしくは、これを JavaScript で作り直してみたい。

, ,