マルコフアルゴリズムとは (マルコフアルゴリズムとは) [単語記事]

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

概要

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

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

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

Hello:World

このルールは「"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" になっていたところだ。

oooo → ooo

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

ooo → oo
oo → o

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

o → x
"x" を出力して停止

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

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

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

XYX → YX
YX → Y

となって "Y" を得る。

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

:$ (コロンの前に何も書かない)

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

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

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

$::Finish
:$

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

Input: !
=> $! (先頭にヒット)
=> Finish!

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

定義

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

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

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

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

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

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

Input: 999
=> $999 (by :$)
=> 9$99 (by $9:9$)
=> 99$9 (by $9:9$)
=> 999 $ (by $9:9$)
=> 999+ (by $:+)
=> 99+0 (by 9+:+0)
=> 9+00 (by 9+:+0)
=> +000 (by 9+:+0)
=> 1000 (by +::1)

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