diff(1)
仕事でdiffとる必要があって、とりあえず実装後に色々勉強して理解できたので、忘れないうちにどこかに文章化しておくテスト。
って、ここかよ＜文章化
（いや、ネット上に日本語で細かく解説してくれてるサイトが無かったので・・・）
取り合えず、予定としては
diff(1) → 基本の考え方
diff(2) → アルゴリズム１：O(ND)アルゴリズム
diff(3) → アルゴリズム２：O(NP)アルゴリズム
の予定で。
・・・まぁ、全部書ければいいな・・・と（遠い目）
集合 A(0…M) = { a b d e f a b c e d }
集合 B(0…N) = { d a b a b c b c b a e d }
のdiffを取る事を考える。
diffの考え方の基本は、最も共通部分が長くなる組み合わせ（以降LCS = LargestCommonSubsequence)を見つけて、LCSからの差分を求めるのが基本な考え方。
また、要素の追加、削除のみを許可した場合に、AからBへ最も少ない編集回数で変換が行える組み合わせ（以降SED = ShortestEditDistance)を見つける方向でも良い。
ちなみに、残念ながらLCSの結果=SEDの結果とはならない。
A = { a a b } B = { a b } なんて場合、LCSならA={a(ab)} B={(ab)}な感じだけど、SEDではAからBへは1番目のaを除いても、2番目のaを除いても同じ編集回数になるから
SEDを求めるために、[1]の論文の筆者Myers氏が（たぶん（え）。[1]の論文亀参照なのでハッキリ判らんのよ・・・）、素晴らしい考察方法を提示をしてくれたので紹介。
まず、集合A、集合Bの要素をx,yグラフ上の軸上に、それぞれA(0)=(1,0)…A(m)=(m+1,0)、B(0)=(0,1)…B(n)=(0,n+1)となるように並べる。
その後、A(x)=B(y)になる任意の点(x,y)に対し、(x-1,y-1)-(x,y)を結ぶ直線を引く。
こうして完成した図を「エディットグラフ」と呼ぶ。
（x軸y軸が通常のイメージと入れ替わってるのは、元の論文もこうだったらしいので・・・）
ここで、x軸方向、y軸方向へ進む場合を編集距離1、斜めに引いた直線上を進む場合を編集距離0として、原点(0,0)から(M,N)への最短編集距離となる経路を求める事を考えれば、その経路がそのままSEDとなる。
（図上、赤色の直線）
この最短経路を求める方法は何パターンも考えられる（たとえば、原点から本当に１歩１歩辿って行って総当りとか・・・）が、次回以降はMyers氏が考察したアルゴリズム[1]と、それを改良し無駄を排除をしたアルゴリズム[2]をまとめて見ようかと。
参考資料：
[1] E.W.Myers, “An O(ND) difference algorithm and its variations”, Algorithmixa, 1 (1986), pp.251-266
[2] S.W.maner, G.Myers, W.Miller, “An O(NP) Sequence Comparison Algorith”, August 1989
[3] 文書比較アルゴリズム http://hp.vector.co.jp/authors/VA007799/viviProg/doc5.htm
（2007/11/16 見直したらx軸y軸とA(0..M),B(0…N)の関係が変だったので修正)
(2008/05/26 参考資料のタイトル間違えてるってこっそり指摘されたのでこっそり修正)
トラックバック URL :
参考にさせていただきました。
本当にdiffに関する日本語の文書は少ないので、細かく説明されているこのエントリの存在は大きな助けになりました。ありがとうございます。
コメント by くらげ — 2008/8/1 Fri @ 17:26:28
[…] diff(1) PLAIN TEXT […]
ピンバック by o(np)のdiffアルゴリズム（貼っただけ - 進・日進月歩 — 2009/10/12 Mon @ 23:55:57