文書比較アルゴリズム Diff/エディットグラフによる比較アルゴリズム

url

http://www.slash-zero.jp/archives/program/466
http://www.slash-zero.jp/archives/program/468
http://www.slash-zero.jp/archives/program/476http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm



■Diffとは何か

感覚的には理解できるDiffだが、厳密なアルゴリズムとしてのDiffとは何かを説明する。
AとBのDiffとは、

	AとBの「最も共通部分が長くなる組み合わせ(LCS)」を見つける作業

	または、

	要素の追加/削除のみの操作で、「最も少ない操作でAからBを作成する手順(SED)」を見つける作業

	……である。

	(以上の２つは別のアルゴリズムであり、結果は異なる場合がある)
ここでは、「最も少ない操作でAからBを作成する手順(SED)」を見つけるアルゴリズムについて記述する。

「最も少ない操作でAからBを作成する手順(SED)」を求めるためには、エディットグラフというグラフを利用した考え方が使われる。

エディットグラフは、

	縦軸にAの要素を、横軸にBの要素を並べて格子状のグラフを作る。

	それぞれの「縦軸の要素 = 横軸の要素」であるポイントで、そのポイントと左上のポイントを斜線で結ぶ。

	という手順で作成される。
	図は http://www.slash-zero.jp/archives/program/466 参照。
	このグラフ上で、

		右へ進むことは「Bから、Aに無い要素を削除する」ことである

		下へ進むことは「Aから、Bに無い要素を削除する」ことである

		斜線を進むことは「一致する箇所を走査(なにもしない)」することである

		……以上から、

			エディットグラフで左上から右下に移動する最短経路を求める作業が

			すなわち、「最も少ない操作でAからBを作成する手順(SED)」を求める作業であると言える。
エディットグラフの最短経路を求めるアルゴリズムはいくつか存在する。
■全走査アルゴリズム

エディットグラフの全経路を走査して最小コストの経路を求める方法。
■O(ND)アルゴリズム

(まだ)
■O(NP)アルゴリズム

(まだ)
■単語

LCS = LargestCommonSubsequence

	「最も共通部分が長くなる組み合わせ」
SED = ShortestEditDistance

	「最も少ない操作でAからBを作成する手順」
O(ND)アルゴリズム

	Diffのアルゴリズムの名前？ E.W.Myers 氏が考えたらしい。
O(NP)アルゴリズム

	Diffのアルゴリズムの名前？ S.W.maner, G.Myers, W.Miller 氏が考えたらしい。