先週末から差分抽出アルゴリズムに取り組んでいます。
二つの列の差分を調べるというのは、LCS(Longest Common Subsequence:最長共通部分列)やSES(Shortest Edit Script:最短編集スクリプト)を求める処理です。
例えば、abcdとabbbcという列があった場合、(ab)(c)というのがLCSで、共通(ab)追加(bb)共通(c)削除(d)みたいなのがSESです。追加2、削除1なので、編集回数は3で、これを編集距離(Edit Length)が3と呼びます。
で、実際にこれをどう解くかなのですが、以下、見つけた限りの資料。
- 津田伸秀のホームページ 文書比較アルゴリズム
- /0 diff(1)
- /0 diff(2)
- /0 diff(3)
- 「An O(ND) difference algorithm and its variations」で検索(論文のpdfが見つかります)
- 「An O(NP) Sequence Comparison Algorith」で検索(論文のpdfが見つかります)
- ウノウラボ Unoh Labs: diff with C++(C++用のライブラリを公開しています)
- Diff - やる気向上作戦(C++用のライブラリを公開しています)
- Subversionの差分抽出部分のソースコード(O(NP)のアルゴリズムで処理しています)
- Longest common subsequence problem - Wikipedia
- 動的計画法と配列アラインメント IBM developerWorks
で、結局私はどうしたかというと、「An O(NP) Sequence Comparison Algorith」の最後に書いてあるコードを元に編集距離を求めるプログラムを試してみて、そこから共通部分の検出時に記録をとるような処理を追加してLCSを求めました。
でも、複数ある答え(LCS,SES)のうち、一つしか求められないのが痛いところです。長い列と短い列の差分をとった場合、細切れな差分が出来てしまう場合があります。たとえば、ravsogiupihrhawegoiurseagroihuとroihuの差分をとった場合、削除(25文字)、共通(roihuとなってほしいのですが、実際には共通(r)、削除(3文字)、共通(o)、削除(1文字)、共通(i)、削除(3文字)、共通(h)、削除(8文字)、共通(u)、削除(10文字)のようになってしまいます。どちらも編集距離25なので、間違ってはいないのですが……。CVSを使っているとよく括弧だけの行が全然関係ない変更していない行とマッチして、気持ち悪い差分を出力してしまうことがありますが、これが原因なんですね。とりあえず、今回の用途では、4文字以上連続でマッチしないと共通と認識しないようにすることで回避してみました。普通どうするものなんでしょう。