/0

diff続き。
今回はO(ND)アルゴリズムと一般的に呼ばれている方法のまとめ。

O(Nなんちゃら)とか表記する場合、本当は処理時間の指標の筈で、元々O(ND)もこのアルゴリズムにはO(ND)掛かりますよってダケの筈なんだけどなぁ・・・。
何処を覗いてもMyers氏のアルゴリズムをO(ND)アルゴリズムと呼ぶ不思議。

diff(1)と同様に
集合 A(0…M) = { a b d e f a b c e d }
集合 B(0…N) = { d a b a b c b c b a e d }
のdiffを取る事を考える。
（エディットグラフは前回参照で）

エディットグラフ上の最短距離を考えるにあたり、如何に効率よく斜線部分を通るかを考える（最短距離＝最も効率よく斜線部分を通過した経路）。
ここで、斜線斜線と呼ぶのも、原文diagonal直訳の対角線もちょっとアレなので、あえて零距離線とか呼んでみる。
更には零距離線の延長上の直線を零距離直線とする。

最短経路を探査する際に、編集回数に着目し、D=0…nと繰り返し探査することで探査する方法を考える。
零距離直線をあらわすため、零距離直線に識別子k=y-x（x,yはk上の任意の点)を振る。
編集回数Dの際に、利用可能な零距離直線は-D≦k≦Dとなる。

kとそれぞれの零距離直線の関係図。
kを-1すると（視覚上)左下方向、+1すると右上方向の零距離直線になる。

引数x,yから編集距離0で到達できる最大のyを復帰する関数をsnake(x,y)とし、D=0…nと0から順次処理を行っていく事を考える。
D回編集時の零距離直線k上でのyの最大値をV[k,D]とした場合、D回編集時毎にkを-D…n…Dと変化させてV[k,D]を求める事を考えると、上記関数を利用して、
V[k,D] = snake(x,y)
となる。

ここで問題になるのは、x,yをどのようにして求めるかであるが、編集回数が+1された場合のk上の零距離線の関係は下の図のようになる。

つまり、yはV[k-1,D-1]+1か、V[k+1,D-1]の内いずれか一方であり、如何に少ない編集回数で終点にたどり着くかを求める場合は、大きいほうの値が正しい。

故に、
y = max(V[k-1,D-1] +1 , V[k+1,D-1])
とする事が出来る。
また、k=y-xなので、xは
x=y-k
で求める事が出来る。

上記の方法で、D=0…n、それぞれのDに対してk=-D…n…Dとして処理を行っていき、最初に(M,N)へ到達したDが最小の編集回数となり、その際に通過した経路がSEDとなる。

理屈の上では以上のような内容で実現可能であるが、実際にプログラムにしてSEDを求める為には以下の留意点を意識する必要がある。

・SEDの経路として、V[k,D]を求める際にV[k-1,D-1]からの遷移なのかV[k+1,D-1]からの遷移なのかが重要な為、単純にmax()で求めると遷移元が不明になる。

・まじめにメモリを確保すると、V[k,D]のために、結構な量のメモリが必要。
　しかし、実際には以下の考察により、M+N+3のメモリで十分。
Dを1づつ処理した場合、kに関しては奇数／偶数を交互に処理すればよい。なぜならば、D+1をした時点で必ず編集距離1を進まなければならないので、kはDが偶数ならば偶数、奇数ならば奇数しかありえない。
故に、仮にV[k]という配列を用意した場合、k=k+2でループを進める限りは必ずV[k-1]、V[k+1]にはD-1のデータが保証される。
ちなみに、+3の内訳はk=-D時のV[k,D-1]、k=D時のV[k,D+1]、k=0の分。
もうちょっと考えると、k>max(M,N)の場合の探索はまったくの無駄（範囲外に共通要素なぞあるわけが無い）だとわかるので、その分を条件文と組み合わせて弾いてもまったく問題ない。

・SEDの経路を記録するには、遷移元を保持するn分木的なデータ構造を用いると楽に行える。(0,0)から辿ると膨大なルートを考慮しなければならないが、ゴールした後に通過した経路を戻るのは遷移元を(0,0)まで辿っていけば一本道。

参考資料：
[1] E.W.Myers, “An O(ND) difference algorithm and its variations”, Algorithmixa, 1 (1986), pp.251-266

[2] S.W.maner, G.Myers, W.Miller, “An O(NP) Sequence Comparison Algorith”, August 1989

[3] 文書比較アルゴリズム http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm

(2007/11/16 やっぱりMとNの関係が変だったのでdiff(1)とあわせて細かく修正）
(2008/05/26 参考資料のタイトル間違えてるってこっそり指摘されたのでこっそり修正)