探索の仕方

まず，図7のように各点への対角線kをy-xと定義します。

たとえば，点(M,N)や(M-1,N-1)だとk＝Δ，点(P,0)だとk＝-P，点(0,Δ+P)だとk=Δ+Pになります。

このように-P≦k≦Δ+Pを探索範囲，P＝pの場合の各対角線k上における到達可能な最遠点をfp(k,p)，任意の点(x,y)から到達可能な最遠点fp(k,p)注7を計算する関数をsnake(k,y)と定義します。

図8と図9に対角線k-1，k，k+1とそれぞれの最遠点fp(k-1,p')，fp(k,p)，fp(k+1,p'')注8との関係を示します。

図8は対角線k+1の最遠点fp(k+1,p'')から対角線上に進む経路がfp(k,p)として採用される場合，つまり，fp(k,p)＝snake(k,fp(k+1,p''))となることを，図9は対角線k-1の最遠点fp(k-1,p')+1から対角線上に進む経路がfp(k,p)として採用される場合，つまり，fp(k,p)＝snake(k,fp(k-1,p')+1となることを示しています。

このことからfp(k,p)の値はk＝Δを境にsnakeを使って図10のように式で表すことができます。

最終的に，kの取り得る値の範囲を探索してfp(Δ,p)の値がNになったとき，点(M,N)に到達したことになるので，このときのpの値が，SESにおける「削除」の合計数Pになります。D＝Δ+2Pなので，これで編集距離が求まります。fp(Δ,p)＜Nの場合はpの値（初期値は0）をインクリメントして，同じことを繰り返します。

また，LCSやSESを求めるにはいろいろ方法がありますが，たとえば探索途中（snake関数内）で使うx，yおよびどの最遠点を通過したかという情報を記録することによって求めることができます。

注6）

ただし，コラムで後述していますが，全然違う2つの要素列を単純なWuのアルゴリズムで比較すると，かなりのメモリ容量が必要になります。

注7）

ただし，fp(k,p)=(x,y)ではなく，fp(x,y)=yというふうに最遠点のy座標のみを示します。

注8）

p'，p''はpもしくはp-1。

Wuのアルゴリズムを使ったサンプルプログラム

以上のことをもとに，実際にWuのアルゴリズムを使って引数として与えられた2つの文字列間の編集距離を求めるC++プログラムをリスト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，B，それぞれの長さをM，NとするとN≧Mなので，①のコンストラクタではN≧Mの関係がつねに成り立つようにします。

②のeditdistance関数がエディットグラフを探索するメインロジックになります。変数fpが各対角線上で到達可能な最遠点のy座標を格納する配列になりますが，探索範囲が-p≦k≦Δ+pなので，そのままだと配列fpの添字が負の値になる場合があるため，添字が負の値にならないように調整する必要があります。

pの最大値がM，またfp(k,p)を計算するにはfp(k-1,p')とfp(k-1,p'')が必要であることを考慮すると，配列fpの添字が負の値にならないためにはM+1個分配列の位置をずらせば良いことになります。

また，配列fpのサイズは同様にPの最大値がM,探索範囲が-p≦k≦Δ+pなので，k＝Δ+P＝Nの際に配列fpの添字の値がk+1+offset＝N+1+M+1＝M+N+2で最大になるため，配列fpのサイズは（配列の添字が0から始まることを考慮して）M+N+3になります。そしてp＝0からループを回していってfp(k,p)＝Nとなったときのpの値（SESにおける削除の合計数）をもとに編集距離を計算します。

③のsnake関数の仕事はfp(k,p)から対角線上に進んで到達できる最大のy座標を返すことです。各要素列の現在位置の要素を1つづつ比較して同一であればそれぞれの要素列の位置を+1進めて，最終的にy座標を返します。また，x座標はk＝y-xにより，x＝k-yで求めることができます。