java diff 及wiki相关基础知识

2008-04-18 08:43:45　来源:中国自学编程网　作者:佚名点击:

diff的原理在于找两个字符串之间的最大相同子串(Longest Common Subsequence)以及编辑距离，比较有名的实现是UnixLinux上常用的diff(GNU Diff)。

     diff的原理在于找两个字符串之间的最大相同子串(Longest Common Subsequence)以及编辑距离，比较有名的实现是UnixLinux上常用的diff(GNU Diff)。

    实现

    Java里Diff的实现我找了一下，主要是两个，java-diff 和bsmi上的Diff ，前者为LGPL，后一个为GPL。其实代码也都不多，都实现了LCS算法。前一个协议上对我们比较有利，而且文档、测试和例子多一些。

    JavaDiff里主要有两个类，Diff和Difference类。前者是算法，后者是差异的表示类。下面讲一下例子：

Object[] a = new Object[] ...{        "a",        "b",        "c",        "d",        "e"    };    Object[] b = new Object[] ...{        "a",        "x",        "y",        "b",        "c",        "j",        "e",    };    Difference[] expected = new Difference[] ...{        new Difference(1, -1,  1,  2),        new Difference(3,  3,  5,  5),    };    Diff diff = new Diff(a, b);    List diffOut = diff.diff();
差别有三处，用两个Difference对象表示。一个Difference对象表示替换，增加，删除。Difference的构造函数：

    public Difference(int delStart, int delEnd, int addStart, int addEnd)
如果delEnd或者addEnd为-1的话，就代表没有删除或者增加行为。

    回到例子，两个字符串之间的差别在于，目标字符串在第1-2行(从0算起)增加了x,y，第3行的d被第5行的j替换。Difference虽然只说明了行号和动作，但我们可以推算出来增加了什么，删除了什么，替换了什么。下面是另一个更长的例子，来自测试用例：

public void testStrings1()    ...

{ Object[] a = new Object[] ...

{ "a", "b", "c", "e", "h", "j", "l", "m", "n", "p" };

Object[] b = new Object[] ...{ "b", "c", &nbs

9 7 3 1 2 4 8 :