Diff について (1)

Diff に興味を持ったので、Diff のことをボチボチ調べ始めました。

周辺情報 => 論文 => ソースコード、の順に読んでいくと思います。

今回は「An O(ND) Difference Algorithm and Its Variations」という論文にいろいろ略語が出てきたので、それを書きながら整頓したときのメモ。

メモ

- Difference : 違い
-- 複数のファイル間の差文をとるプログラム

- Diffをとることは以下のいずれかを求めるのと同義
1, LCS(Longest Common Subsequence)
　- LCSを見つけて、差分を求める
2, SES(Shortest Edit Script)
- 「追加」と「削除」と「現状維持」のみを許可した場合に、文字列Aから文字列Bへ最も少ない編集回数(Shortest Edit Distance)で変換が行える処理組み合わせを求める

- ただし、LCSとSESの両アプローチの結果は一致しない。
-- 「aab」と「ab」の間で
--- LCSは後ろ側のabに決まる
--- SESは前のaを消しても、後ろのaを消してもじ編集距離。

- Levenshtein Distance（Edit Distance）
-- 文字列Aを文字列Bに変換するために、必要な文字の追加と削除の合計回数

- LCS
-- 文字列Aと文字列Bの最長共通部分列
--- 部分列と部分文字列はちがう
-- 両方の文字列に共通で出現する文字を出現順が崩れないように抽出
--- 抽出できる共通部分列のうち最長のものがLCS

- SES
-- 文字列Aから文字列Bへの変換を最小の編集回数でおこなうための手順
-- 要素の追加・削除の操

- Edit Graph
-- 文字列A・Bを行と列に配置した格子状の有向グラフ。
-- Aのx番目の文字A(x)と、B(y)が「A(x)=B(y)」になる任意の点(x, y)について、(x-1, y-1)から(x,y)へ斜め線を引く

-- SESとの関係

Edit Graphのたどり方	SESへの作用	意味	コスト
y軸方向に1進む	SESの追加	BからAに無い要素を削除	1
x軸方向に1進む	SESの削除	AからBに無い要素を削除	1
斜め線上を1進む	SESが共通	一致する箇所を走査	0

- SESの計算
-- Edit Graphのスタートからゴールまでの最短距離を求める問題
--- SED(Shortest Edit Distance : 最小編集距離)を持つSESを求める

- 最終的なSESのコスト = Levenshtein Distance

- 素朴に考えると2回のスキャンが必要。
-- 1, 一回すべての格子上の点で文字が一致するかを判定し、配列などに記録
-- 2, 先ほどの一致点の判定データを元に、(0,0)から(M, N)のSEDをもつSESをもとめる

次は「O(ND) Difference Algorithm」のメモを書きます。