前のドキュメント
次のドキュメント
ＶｉＶｉの文書比較（diff）機能で使用しているアルゴリズムについて解説する。
これらのアルゴリズムは Myers 氏らの論文によるもので、氏は筆者のためにわざわざ論文をＷｅｂサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。
オリジナル論文は以下のＷｅｂサイトから入手可能である。
http://www.cs.arizona.edu/people/gene
[1] E.W.Myers, "An O(ND) Difference Algorithm and Its Variations", Algorithmica, 1 (1986), pp.251-266
[2] S. Wu, U. Manber, G. Myers and W. Miller, "An O(NP) Sequence Comparison Algorithm", August 1989
文書比較（diff）を行う問題は、２つの文書Ａ，Ｂの最長共通部分（ＬＣＳ Longuest Common Subsequence）、または最小エディット距離（ＳＥＤ Shotest Edit Distance）を求める問題と等価である。以下のアルゴリズムではこれらの問題をエディットグラフ上の最短距離取得問題に還元し、解を求める。
エディットグラフとは文書Ａ、Ｂの各要素（A1 A2 ... AM, B1 B2 ... BN）をＸ軸Ｙ軸上に並べ、それらの交点を縦横の辺で結合し、Ａのｘ番目の要素とＢのｙ番目の要素が等しい場合のみ (x-1, y-1) から (x, y) を結合したものである。
たとえば、Ａが“あいうあううあ”、Ｂが“ういあいあう”の場合エディットグラフは以下の様になる。
あ い う あ い い あ
(0,0)┌─┬─┬─┬─┬─┬─┬─┬→ Ｙ
│ │ │＼│ │ │ │ │
う├─┼─┼─┼─┼─┼─┼─┤
│ │＼│ │ │＼│＼│ │
い├─┼─┼─┼─┼─┼─┼─┤
│＼│ │ │＼│ │ │＼│
あ├─┼─┼─┼─┼─┼─┼─┤
│ │＼│ │ │＼│＼│ │
い├─┼─┼─┼─┼─┼─┼─┤
│＼│ │ │＼│ │ │＼│
あ├─┼─┼─┼─┼─┼─┼─┤
│ │ │＼│ │ │ │ │
う├─┴─┴─┴─┴─┴─┴─┘(6,7)
↓
Ｘ
上記のようなエディットグラフを考える時、ＬＣＳ／ＳＥＤを求める問題は、エディットグラフ上で、(x, y) から (x + 1, y) または (x, y + 1) への移動（縦、または横方向への移動）が距離１、(x, y) から (x + 1, y + 1) への移動（対角線方向への移動）が距離０とする時に、(0, 0) から (M, N) までの経路で距離が最小のものを求める問題に還元される。
上記の例では、下図の太字の経路が最小コストを与えるものである。
あ い う あ い い あ
(0,0)┌━┯━┬─┬─┬─┬─┬─┬→ Ｙ
│ │ │＼│ │ │ │ │
う├─┼─┼─┼─┼─┼─┼─┤
│ │ │ ┃ │ │ │ │
い├─┼─┼─┼─┼─┼─┼─┤
│ │ │ │＼│ │ │ │
あ├─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │＼│ │ │
い├─┼─┼─┼─┼─┼━┼─┤
│ │ │ │ │ │ │＼│
あ├─┼─┼─┼─┼─┼─┼─┤
│ │ │ │ │ │ │ ┃
う├─┴─┴─┴─┴─┴─┴─┘(6,7)
↓
Ｘ
エディットグラフでの最小距離を求めるもっとも原始的なアルゴリズムは、すべてのノードを順にスキャンし、コストを求めている方法である。計算量は O(M*N) で、必要なメモリは min(M, N) である。プログラムは単純なので省略する。
上記以外にも最小距離を求める方法にはバックトラッキングを用いるなどいくつか考えられるが、 O(ND) アルゴリズムは計算量が文書長（N）と差分（D）の積に比例するので、 原始的なアルゴリズムに比較して計算量がかなり少ないという特徴がある。
文字列Ａの要素数をＭ、Ｂの要素数をＮとする。ＤはこれらのＳＥＤである。ただし、O(ND) のＮは文字列ＡとＢの要素数の合計（Ｍ＋Ｎ）である。（ちょっと紛らわしい表記であるが、慣習なのでがまんしてください）
次に、エディットグラフで原点から右下方向の対角線を識別するための番号ｋを、ｙ−ｘと定義する。D = 0, 1, 2, ... について、対角線ｋでの最大のｙを V[k, D] とする。この値はＤ回の編集操作で到達可能な最遠点を表わすので、Ｄを増やしながら、最初に V[k, D] == N となる経路を求めればいいことになる。面白いことに V[k, D] は V[k-1, D-1], V[k+1, D-1] から求めることができる（証明は [1] を参照）ので、ＬＣＳを求めるアルゴリズムは以下のようになる。
ond()
{
int V[(M + N) * 2 + 1]; // 各対角線の最遠点のｙ座標値
int x, y, offset = M + N;
V[1 + offset] = 0;
for(int D = 0; D <= M + N; ++D) { // 各Ｄについて
for(int k = -D; k <= D; k+=2) {
if( k == -D || k != D && V[k - 1 + offset] < V[k + 1 + offset] )
y = V[k + 1 + offset];
else
y = V[k - 1 + offset] + 1;
x = y - k;
V[k + offset] = snake(x, y);
if( x >= M && y >= N )
return; // found !!!
}
}
}
int snake(int &x, int &y) // 対角線が存在する場合は、移動する
{
while( x < M && y < N && A[x+1] == B[y+1] ) {
x += 1;
y += 1;
}
return y;
}
O(ND) アルゴリズムでは、２つの文字列の差違；Ｄに比例した処理時間が必要だが、最遠点方向の探索を優先することで O(NP) は遥かに少ない（experimental には約２分の１）手間でＬＣＳを求めることができる。
Ｍ≧Ｎの時、Δ＝Ｍ−Ｎとし、Ｐ＝（Ｄ−Δ）／２と定義する。これは差違がＤの時に、原点からもっとも遠い対角線との距離に相当する。（下図参照）
Δ Δ＋Ｐ
(0, 0)┌─────────┬→ Ｙ
│＼ ＼ ＼ │
−Ｐ│ ＼ ＼ ＼ │
│＼ ＼ ＼ ＼│
│ ＼ ＼ ＼ │
│ ＼ ＼ ＼│
├─────────┘(M, N)
↓
Ｘ
O(ND) アルゴリズムではＤを指標にして、対角線ごとの最遠点を求めたが、O(NP) では上記のＰを指標にする。最遠点 fp[k, p] は、以下のように定義される（証明は [2] を参照）。
│ snake(k, max(fp[k-1, p] + 1, fp[k+1, p-1])) if -p <= k < Δ
fp[k, p] = │ snake(k, max(fp[k-1, p] + 1, fp[k+1, p])) if k == Δ
│ snake(k, max(fp[k-1, p-1] + 1, fp[k+1, p])) if Δ > k >= Δ + p
上記定義より、ＬＣＳを求めるアルゴリズムは以下の様に記述できる。
onp()
{
int fp[M + N + 3];
int x, y, k, offset = M + 1;
int DELTA = M - N;
for(int p=0; ; ++p) {
for(k = -p; k < DELTA; ++k)
fp[k + offset] = snake(k, max(fp[k-1+offset] + 1, fp[k+1+offset]));
for(k = DELTA + p; k > DELTA; --k)
fp[k + offset] = snake(k, max(fp[k-1+offset] + 1, fp[k+1+offset]));
fp[DELTA + offset] = snake(k, max(fp[DELTA-1+offset] + 1, fp[DELTA+1+offset]));
if( fp[DELTA + offset] == N )
return; // found !!!
}
}
前のドキュメント
次のドキュメント
Copyright (c) 1997 by Nobuhide Tsuda, All Right Reserved.
このホームページに関するご質問、ご要望、バグレポート等は
ntsuda@beam.ne.jp
までメールをいただければ幸いです。