/0

そんなわけでO(NP)のお話とか。

まず、処理を最適化するためにO(ND)の無駄を考えてみる。
O(ND)では編集回数Dを0…nと変化させて順次処理を行うわけだけど、仮に集合A(0…M)とB(0…N)の間で、M!=Nの関係が有る場合、D<|M-N|の間は決して終端にたどり着かない期間の計算となる。

また、編集回数Dの時に、零距離直線kを-D…0…Dまで計算するが、この際も実際には結構無駄な計算を行っている。
というのも、編集回数Dで終点にたどり着ける場合、実際に経路として使用されるkの範囲は-D…0…Dと一致しない。

集合Aと集合Bの関係をN>=Mと仮定して、Δ=N-Mとした場合、この未知の集合において最も少ない編集回数はΔとなるが、その場合のkの範囲は0…Δとなる（上図の緑色の範囲）。
以降Dが2増える毎(移動距離1の往復分)に-1…Δ+1、-2…Δ+2とkの範囲が広がっていくことになる。
故に、本来計算が必要な最低限のkの範囲は上記の通りであるが、O(ND)のアルゴリズムの計算方ではV[k,D]がk[k,D+1]を算出する際に必要であるし、D+αの計算にも後々影響を及ぼす為、kの探査範囲を上記のようにすることは出来ない。

そこで、もっと最適化された計算方法を考察する。
以降、処理および考察を単純にするために、集合A(0…M)、集合B(0…N)においてN>=Mの関係がある事を前提とする。
（M>Nの場合は両者の集合の立場を入れ替えて計算し、結果を逆転すれば良いので）

Δ=N-Mとし、処理の基準を編集回数Dではなく、最低の編集回数となるΔからの損失としてPを考える。
編集距離1を損失した場合、それを取り戻す為に更に編集距離1が必要なので、編集回数D時のΔ、Pの関係を式にすると、
D=Δ+2P　（∴ P=(D-Δ)/2)
となる。
エディットグラフ上の距離モデルを考える際に、Δ=ｙ軸方向へ進まなければ行けない距離、P=迂回した距離の往路分と考えるとわかりやすいかも？？

O(ND)の時と同様に、今回はPを0から+1づつ順次処理していった際に、P=pの際に零距離直線k上で到達可能な最大のyをfp[k,p]とする。
ここで、零距離直線k上で任意の点S(x,y)から開始した最大のyを探査する関数snake(k,y)がある場合、pの際のk上の基点Sをp-1またはpの際のfpから求める事が出来れば、O(ND)同様にpを順次処理していけば、ある時点でfp[Δ,p]=Nとなり、SEDの探索が行えることになる。

基点Sを求める為に、まずp=0の際の処理を考慮する。

p=0の際の各kの基点S[k,0]は、単純にfp[k-1,0]+1となる（ただしfp[-1,0]=-1）
拠って、
fp[k,0] = snake(k, fp[k-1,0]+1);
で求める事が出来る。

次にpが任意の数の場合について考える。
fp[k,p-1]には、p-1時点でのそれぞれのk上での最短経路を通過した場合の、最大のyが格納されている。
(p-1)から、pが1増えたということは、y軸方向、若しくはx軸方向へkひとつ分だけ迂回することが可能になった事を示す。
(p-1)+1の時点で往復分のコストは支払い済みとなっている為、迂回の復路方向の分に関しては自由に移動することが出来る。
任意の零距離直線k視点で見ると、「今回(p+1された事で）自身が新たな迂回路になる場合」と「復路として利用される場合」に、最も遠方へ到達できる開始点が、最適なSといえる。
また、kの探査範囲はΔとPの関係から、-p≦k≦Δ+pの範囲となる。

以上の考察により、終点(M,N)はk=Δ上にあるため、迂回=「Δから離れる方向へ進む事」なので、Δを基準にkを三つの領域に分けると、基点S[k,p]は以下のようにあらわす事ができる。

（赤矢印が迂回方向、青矢印が復路方向）

-p≦k＜Δの範囲 S = max(fp[k-1, p]+1, fp[k+1, p-1])
k=Δの範囲 S = max(fp[k-1, p]+1, fp[k+1, p])
Δ＜k≦Δ+pの範囲 S = max(fp[k-1, p-1]+1, fp[k+1, p])
（ただし、fp[]の初期値は全て-1で初期化されている事）

k<Δの範囲のケースに絞ってもう少し詳しく解説すると、任意のkに関して、「今回自身が新たな迂回路となる」ケースは、fp[k+1,p-1]からの迂回となる。
「復路として利用される」ケースは、今回の経路での復路となるのでfp[k-1,p]からの復路となる。
仮に、kが今回最も外側の迂回路の場合、fp[k,p]にはsnake(k,fp[k+1,p-1])が記録されており、次に処理されるk+1は復路として利用される場合、kのfp[k,p]を評価する事になる。
p+1された事による、新たに最も外側の零距離直線k=-pに関しては、fp[-1-p,p]は初期値-1となっている為、-1+1=0となり、自身が開始となる場合か、p+1から迂回する場合に利用されることなる。

また、上記で開始時点の状況整理の為特別に取り上げたp=0のケースであるが、fp[]の初期値を-1とする場合、fp[k,-1]の初期値も全て-1になる為、常にmax(fp[k-1, p]+1, -1)=fp[k-1,p]+1が成り立つので、処理上特別扱いをする必要は無い。

以上により、p=0….nとし、f[Δ,p]=Nとなるまで繰り返し処理を行えば、求められた経路がSEDとなる。

以下、前回同様プログラムにする場合の留意点等々。

・pに対してkを-p…Δ+pまでループ処理をする際、処理をする順番が重要
k＜Δの領域ではfp[k-1,p]が必要なので、k=-p,-p+1,・・・,Δ-1とインクリメントで処理しなければならず、k＞Δの領域でfp[k+1,p]が必要な為、k=Δ+p,Δ+p-1,・・・,Δ+1とデクリメント処理する必要がある。
また、k=Δに関しては、fp[k-1,p]、fp[k+1,p]が両方必要な為、上記処理を両方処理した後、最後に実行する必要がある。

・SEDを求めるには、O(ND)で記述したのと同様に、fp[k,p]を求めた際の遷移元をfp[k,p]とあわせて保持しておき、最後にfp[Δ,p]から辿ればよい。

・必要なfpの領域であるが、上記のループ順にそって処理する場合、fp[k,p]が処理された時点でfp[k+1,p-1]（あるいはfp[k-1,p-1]）は不要になる為、実際の処理ではfp[k]の一次元配列領域が存在すればよい。
fp[k]の必要最大サイズは、ワーストケースの時(=一致が一件も無いケース)のPを考えればよいので、Pmax=Mとなり、-P≦k≦Δ+Pおよび、k-1、k+1とk=0分の領域を考慮して、
　fp-size = (Pmax)+(Δ+Pmax)+1+1+1
　fp-size = M+N-M+M+3
　fp-size = M+N+3
となる。

参考資料：
[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

(2008/05/26 参考資料のタイトル間違えてるってこっそり指摘されたのでこっそり修正)