探索の仕方
まず，
図7 エディットグラフで対角線kを定義する
たとえば，
このように-P≦k≦Δ+Pを探索範囲，
図8と図9に対角線k-1，
図8 fp(k,p)=snake(k,fp(k-1,p"))
図9 fp(k,p)=snake(k,fp(k-1,p')+1))
図8は対角線k+1の最遠点fp(k+1,p'')から対角線上に進む経路がfp(k,p)として採用される場合，
このことからfp(k,p)の値はk＝Δを境にsnakeを使って図10のように式で表すことができます。
図10 snake関数とfp(k,p)の関係
最終的に，
また，
- 注6）
- ただし，
コラムで後述していますが， 全然違う2つの要素列を単純なWuのアルゴリズムで比較すると， かなりのメモリ容量が必要になります。 - 注7）
- ただし，
fp(k,p)=(x,y)ではなく， fp(x,y)=yというふうに最遠点のy座標のみを示します。 - 注8）
- p'，
p''はpもしくはp-1。
Wuのアルゴリズムを使ったサンプルプログラム
以上のことをもとに，
リスト1 文字間の編集距離を求めるプログラム
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
class Diff
{
public :
Diff(const string &a, const string &b) { --------①
M = a.length();
N = b.length();
if (M < N) {
A = a;
B = b;
} else {
A = b;
B = a;
swap(M, N);
}
}
int editDistance () const { --------②
const int offset = M + 1;
const int delta = N - M;
const int size = M + N + 3;
int fp[size];
for (int i=0;i<size;++i) fp[i] = -1;
int p = -1;
do {
++p;
for (int k=-p;k<=delta-1;++k) {
fp[k+offset] = snake(k, max(fp[k-1+offset]+1, fp[k+1+offset]));
}
for (int k=delta+p;k>=delta+1;--k) {
fp[k+offset] = snake(k, max(fp[k-1+offset]+1, fp[k+1+offset]));
}
fp[delta+offset] = snake(delta, max(fp[delta-1+offset]+1, fp[delta+1+offset]));
} while (fp[delta+offset] != N);
return delta + 2 * p;
}
private :
int snake (int k, int y) const { --------③
int x = y - k;
while (x < M && y < N && A[x] == B[y]) {
++x;
++y;
}
return y;
}
string A;
string B;
int M;
int N;
};
int main(int argc, char *argv[]){
if (argc < 3) {
cerr << "few augument" << endl;
return -1;
}
string A(argv[1]);
string B(argv[2]);
Diff d(A, B);
int editDistance = d.editDistance();
cout << "editDistance: " << editDistance << endl;
return 0;
}
Wuのアルゴリズムでは2つの要素列をA，
②のeditdistance関数がエディットグラフを探索するメインロジックになります。変数fpが各対角線上で到達可能な最遠点のy座標を格納する配列になりますが，
pの最大値がM，
また，
③のsnake関数の仕事はfp(k,p)から対角線上に進んで到達できる最大のy座標を返すことです。各要素列の現在位置の要素を1つづつ比較して同一であればそれぞれの要素列の位置を+1進めて，