次のドキュメントViViの文書比較(diff)機能で使用しているアルゴリズムについて解説する。氏らの論文によるもので、氏は筆者のためにわざわざ論文をWebサイトで入手可能な形式にしてくださった。この場を借りてお礼申し上げる。オリジナル論文は以下のWebサイトから入手可能である。Distance)を求める問題と等価である。以下のアルゴリズムではこれらの問題をエディットグラフ上の最短距離取得問題に還元し、解を求める。Aが“あいうあううあ”、Bが“ういあいあう”の場合エディットグラフは以下の様になる。経路で距離が最小のものを求める問題に還元される。上記の例では、下図の太字の経路が最小コストを与えるものである。原始的なアルゴリズムエディットグラフでの最小距離を求めるもっとも原始的なアルゴリズムは、すべてのノードを順にスキャンし、コストを求めている方法である。プログラムは単純なので省略する。原始的なアルゴリズムに比較して計算量がかなり少ないという特徴がある。文字列Aの要素数をM、Bの要素数をNとする。DはこれらのSEDである。Nは文字列AとBの要素数の合計(M+N)である。(ちょっと紛らわしい表記であるが、慣習なのでがまんしてください)次に、エディットグラフで原点から右下方向の対角線を識別するための番号kを、y−xと定義する。なる経路を求めればいいことになる。参照)ので、LCSを求めるアルゴリズムは以下のようになる。約2分の1)手間でLCSを求めることができる。M≧Nの時、Δ=M−Nとし、P=(D−Δ)/2と定義する。これは差違がDの時に、原点からもっとも遠い対角線との距離に相当する。上記のPを指標にする。p上記定義より、LCSを求めるアルゴリズムは以下の様に記述できる。メールをいただければ幸いです。