マルコフアルゴリズム単語

マルコフアルゴリズム
  • 6
  • 0pt
掲示板へ

マルコフアルゴリズムとは、複数の文字列置換規則から構成される文字列書き換え系である。

概要

マルコフアルゴリズムはアンドレイ・マルコフ・ジュニアによって考案された文字列書き換え系である。他の文字列書き換え系として有名なものにチョムスキーの生成文法があり、これなら知ってるという人も多いのではないだろうか。

定義を述べる前に簡単な例から見ていこう。

マルコフアルゴリズムはいくつかの置換規則によって構成される。規則は一つでもよい。例えば次のようなもの。

このルールは 「"Hello" という文字列を "World" に置換する」と読む。置換の前後をコロンで区切る書き方は後述する Markov Algorithm Online (通称 MAO) に倣っている。他に「Hello→World」と書く文献もある。

マルコフアルゴリズムはちょうど一つの文字列に適用する。 例えば "Hello" という文字列にこれを適用することを考える。マルコフアルゴリズムはルールのうち、置換が出来るルールを探す。今の場合は一つしかないルール "Hello:World" が適用でき、これに従って文字列を置換する。すると "World" が得られる。マルコフアルゴリズムはここで止まらずに、今度は "World" に対して置換できるルールを探す。しかし今度は "World" を置換するようなルールいのでマルコフアルゴリズムはここで停止し、最終的に得られた "World" がこのシステムの出となる。

これは大変つまらない例だったろうから、もう少しだけ複雑な例を取り上げよう。

  • oo:o
  • o:x

今度はなんと2つのルールから構成されている。 これを "oooo" という文字列に適用してみよう。マルコフアルゴリズムはまず、適用可ルールを探す。 今、"oo:o" も "o:x" もどちらも適用可だ。なぜなら "oooo" には "oo" も、"o" も含まれているからだ。 しかしマルコフアルゴリズムはこの内 "oo:o" を選ぶ。 なぜなら、言い忘れていたが、置換規則には初めに優先度をつけることになっており、適用可な中で最も優先度の高いもの一つを選ぶというルールがあるからだ。 この記事の中ではルールを並べて書いた場合、上にあるほど優先度が高いということにする。そして多くの文献でもこの記法が採用されている。 というわけで "oooo" という文字列に "oo:o" が適用されるのだが、困ったことに "oooo" という文字列はその部分として "oo" を何箇所にも含んでいる("oooo", "oooo", "oooo")。 そういうときには、最も左にあるものに一回だけ適用する、と決められている。 従って "oooo" は最も左の "oo" が "o" に置換され、結果的に "ooo" が得られる。 もっとも、今の場合はどの "oo" が置換されても同じ結果であったが、仮に適用対が "ooxoo" であれば "oxoo" になっていたところだ。

  1. oooo → ooo

先述したように、マルコフアルゴリズムはここで停止はせず、次に適用可ルールを再び探す。ちょうど先程一番ルールを適用したから、次は二番ルールを、とは行かず、これはあくまでも複数適用可な場合の優先度に過ぎない。つまり、再びルール全体から適用可ルールを探し、見つけた中で最も優先度の高いもの一つを適用する。"ooo" という文字列にはまだ "oo:o" が適用できる。その結果得られる "oo" にもやはり同様に "oo:o" が適用できる。

  1. ooo → oo
  2. ooo

そして最後、"o" に適用できるのは "o:x" だけだから初めてこのルールを適用し "x" を得る。これには適用できるルールがないので、ここでようやくアルゴリズムは停止する。

  1. ox
  2. "x" を出して停止

もう2つだけ、マルコフアルゴリズムには特筆すべきルールがある。一つは置換の前後には文字列を定できること。文字列とは、長さゼロ文字列のことである。置換後に文字列を置く場合、これは簡単で、削除を行うことができる。

  • X: (コロンの後ろには何も書かない)

これを "XYX" に適用すると

  1. XYX → YX
  2. YX → Y

となって "Y" を得る。

一方で置換前に文字列を定する場合、これは文字列の先頭にヒットする。文字列は部分文字列としてどこにでも文字列を含んでおり、その中で最も左なのは先頭だからだ。よく分からない人はそういうものだと思ってもらいたい。

これを "X" に適用すると

  1. X → $X
  2. $X → $$X
  3. $$X → … (いつまでもヒットするのでアルゴリズムは停止しない)

このように、置換前に文字列を定してしまうと必ず停止しないので、使い物にならないじゃないかとお思いだろう。そこで、まだ言っていなかった最後のルールがある。コロン1つ (:) では単に適用出来るときに置換するだけだったが、その代わりにコロン2つ (::) で書くと、適用の挙動が少し変わる。置換し、その直後にアルゴリズムを即座に停止する。こんなアルゴリズムの挙動を考えよう。

これを例えば文字列 "!" に適用すると、

  1. Input: !
  2. => $! (先頭にヒット)
  3. => Finish!

となる。最後の "Finish!" にはなお ":$" が適用可であるが、その前に :: の効果によって "Finish!" を出して停止していることに注意してほしい。

定義

ここまでをに読んでくれたならほとんど理解しているだろうが、めて定義を述べる。

マルコフアルゴリズムは複数の置換規則で構成される。置換規則には2種類あり s:t または s::t と書かれる。ここで s と t は任意の(も許す)文字列である。置換規則には優先度を予め与える(優先度は全順序)。マルコフアルゴリズムは文字列に適用することができる。文字列 u への適用は次のようなルールで行われる。

  1. 適用可ルールを探す。
    1. すなわち、u の部分文字列として s を含むようなルール s:t または s::t を見つけてくる。
    2. そのようなルールが複数ある場合は予め与えた優先度に従って最も高いもの一つを選ぶ。
  2. ルールが見つかったならそれを適用する。
    1. すなわち、u の部分文字列 s を t に置き換える。
    2. ただし u が部分文字列として s を複数持つ場合、その中で最も左のものだけを置換する。
    3. 適用したルールが s::t の場合、アルゴリズムはここで停止する。
  3. 適用可ルールが見つからなかった場合、アルゴリズムはここで停止する。
  4. 1 に戻る。

マルコフアルゴリズムはチューリング完全

ここまで読んできて思ったことだろう。で? と。驚くべきことにマルコフアルゴリズムはチューリング完全である。これは大雑把に言えば「普通コンピュータ」と同等の計算を持つということである。そしてそれは、その気になればスーパーコンピューターで行われるような計算と同じことが(十分な時間とメモリがあればだが)出来るということでもある。

今まで見てきた例では、その計算らしさが見当たらなかっただろうから、もう少し、計算してるっぽい例を見てみよう。例えばこんなのはどうだろう。十進数で自然数文字列として与えられるので、これに +1 したものを出する、というものだ。例えば "123" という文字列に適用すると "124" を出し、"999" に適用すると "1000" を出してくれるようなマルコフアルゴリズムを構成することは出来るだろうか。もちろん答えはYesである。次がその一例だ。

  • $0:0$
  • $1:1$
  • $2:2$
  • $3:3$
  • $4:4$
  • $5:5$
  • $6:6$
  • $7:7$
  • $8:8$
  • $9:9$
  • $:+
  • 0+::1
  • 1+::2
  • 2+::3
  • 3+::4
  • 4+::5
  • 5+::6
  • 6+::7
  • 7+::8
  • 8+::9
  • 9+:+0
  • +::1
  • :$

このように、出現する文字の数だけルールが必要になることが常なので、文字の種類を減らす意味で問題を2進数で与えることが多い(計算の本質はそこじゃないからね)。 10進数にしてしまったのを少し後悔してるが、せっかく書いてしまったので、簡単にこのアルゴリズムの挙動を見てみよう。 まず繰り上がりが発生しないパターンは簡単だ。 "123" という文字列に適用する場合を考えよう。

  1. Input: 123
  2. => $123 (by :$)
  3. => 1$23 (by $1:1$)
  4. => 12$3 (by $2:2$)
  5. => 123$ (by $3:3$)
  6. => 123+ (by $:+)
  7. => 124 (by 3+::4)

どんな動きをしてるか見てみよう。全てのルールには $ や + といった記号が絡んでおり、初めに適用出来るルールは ":$" しかない。先頭に $ がつく。そのあと、"$1:1$" といったルールによって $ より右に数字がある場合にはその右に $ が移動していく。末尾まで行くと、それらのルールが適用できず、"$:+" が適用される。この $ や + はいわばテキストエディタカーソルのような役割をしており、今どの一点に注しているかを表現できる。自然数に +1 するというのは一番下の桁を 1 増やすという意味だから、一番下の桁にカーソルを置きたくて、このようなことをしている。いきなり末尾に置くようなことは出来ないために、先頭に置いてからこれを一つずつ後ろに移動させるという手法がよく使われる。末尾まで行くとカーソルを別な記号 + で置き換えているが、これは「今注してる(すぐ左の)桁にこれから 1 足したい」という気持ちを表現している。左の数字が 0 から 8 の場合は繰り上がりが発生しないので、何も考えずに 1 増やした数字に置き換えることで +1 が実現される。繰り上がりのときだけ少し気をつけなければいけない。

"999" に適用した場合を見てみよう。

  1. Input: 999
  2. => $999 (by :$)
  3. => 9$99 (by $9:9$)
  4. => 99$9 (by $9:9$)
  5. => 999$ (by $9:9$)
  6. => 999+ (by $:+)
  7. => 99+0 (by 9+:+0)
  8. => 9+00 (by 9+:+0)
  9. => +000 (by 9+:+0)
  10. => 1000 (by +::1)

"999+" が得られるまでは先程と同様である。ここで次に "99+0" になっている。筆算のときに、繰り上がりで 1 が発生したとき、次の桁の右下に小さく 1 を書いたと思う。 + はちょうどそれと同じ役割を担っている。繰り上がりが最後の桁まで行くと + の左に何もなくなるので +::1 で終了し、事計算が了する。

関連リンク

こんなマルコフアルゴリズムをパズル形式にして競い合える web サイトがある。それが Markov Algorithm Online (通称MAO) である。問題は、「こんな入が与えられるのでこんな処理をした出をさせるマルコフアルゴリズムを書いてね」という形式で、より少ない置換規則で構成すると高いスコアがもらえる。例えば「2進数で0以上の整数が与えられるからこれに +1 したものを出してね」(さっき例で挙げたものの2進数版)という問題があり、これは現在 6 lines (規則の単位) が最短記録になっている。

関連項目

【スポンサーリンク】

  • 6
  • 0pt
スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%83%9E%E3%83%AB%E3%82%B3%E3%83%95%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

マルコフアルゴリズム

まだ掲示板に書き込みがありません…以下のようなことを書き込んでもらえると嬉しいでーす!

  • 記事を編集した人の応援(応援されると喜びます)
  • 記事に追加して欲しい動画・商品・記述についての情報提供(具体的だと嬉しいです)
  • マルコフアルゴリズムについての雑談(ダラダラとゆるい感じで)

書き込みを行うには、niconicoのアカウントが必要です!


急上昇ワード

おすすめトレンド