汎用Diffライブラリ

仕事上の必要性にかられ、汎用Diffライブラリを作ってみました。



Diff関連の資料をいろいろと調べたところ、「An O(NP) Sequence Comparison Algorithm」のアルゴリズムがよさそうだったのでこれをもとに実装しています。
実装にあたっては、可読性＞メモリ使用量＞性能の優先順位をおいて実装しているので性能的には改善の余地があるとは思っています。ただ、自分としてはとにかくシンプルに拡張できることが重要だったのであまり凝った作りにはしていません。

実際に使う場合は、以下の図にあるDiffSourceを実装することで様々なDiffをとることができます。標準の実装として文字列用のDiffStringSourceというクラスが用意してあるので文字列のDiffであればこちらを使用してください。



以下は文字列用のDiffStringSourceを使用したときの結果イメージを示しています。図のようにDiffSequenceに開始、終了インデックスが格納されDiffSequenceのリストとして結果を取得できます。



ソースと結果イメージは次のようになります。
サンプルソース：

public class DiffTest { public static void main(String[] args) throws Exception { DiffSource s1 = new DiffStringSource("abcdefg"); DiffSource s2 = new DiffStringSource("abzge"); Diff diff = new Diff(); List diffList = diff.diff(s1, s2); int i = 0; for(DiffSequence seq : diffList){ if(seq instanceof CommonSequence){ System.out.println(i+":共通部分"); System.out.println( " source("+seq.getSourceStartIndex() +","+seq.getSourceEndIndex() +") = "+seq.getSourceElements()); System.out.println( " target("+seq.getTargetStartIndex() +","+seq.getTargetEndIndex() +") = "+seq.getTargetElements()); }else{ System.out.println(i+":差異部分"); System.out.println( " source("+seq.getSourceStartIndex() +","+seq.getSourceEndIndex() +") = "+seq.getSourceElements()); System.out.println( " target("+seq.getTargetStartIndex() +","+seq.getTargetEndIndex() +") = "+seq.getTargetElements()); } i++; } } }

結果：
0:共通部分
  source(0,2) = ab
  target(0,2) = ab
1:差異部分
  source(2,4) = cd
  target(2,4) = zg
2:共通部分
  source(4,5) = e
  target(4,5) = e
3:差異部分
  source(5,7) = fg
  target(5,5) =