Diff 算法的原理是什么, 怎样学习和理解?

Question

网上能搜索到论文, 但是... 求讲解
An O(ND) Difference Algorithm and Its Variations (1986)
An O(ND) Difference Algorithm and Its Variations∗

Answer 1

就是用了 @smlg 提到的LCS。我用伪CoffeeScript代码翻译下吧：

首先我们把文件old、new转化为两个列表，列表的每个元素是文件的某一行：

A = [1行、2行、3行、4行、...]
B = [1行、2行、3行、4行、...]

然后我们计算A和B最长的相似元素的长度lcs（递归就是力量）

lcs = (A, B) ->
    result = 0
    if A.length is 0 or B.length is 0
        result
    else if A[0] is B[0]
        result = 1 + lcs(A[1..], B[1..])
    else
        result = Math.max(lcs(A, B[1..]), lcs(A[1..], B))

(之所以叫伪CoffeeScript,因为真实环境下，文件足够大的话，会因为递归太多而爆栈……）

拿到了lcs，然后根据计算lcs时找到的能对上的头，就可以得出两个文件最大的相同部分，用C表示，那么，A、B就被切分成了：

A-、C、A+
B-、C、B+

然后，我们再用同样的方法比较A-、B-，以及A+、B+，一直这样递归下去，一段段地比较，最后把所有的结果拼起来，diff就出炉啦~

当然，实际的算法肯定会有很多优化的，比如找lcs会用更高效的算法（动态规划什么的），中间结果的缓存等等。

还有一种diff算法是比较字与字的不同（比较适合于文档），其实也是一样的原理，只是把按行切割改成按单词或字符切割而已（当然，具体到某种语言，为了得出更有意义的结果，会有一些调整）。

Answer 2

可以看一下LCS http://en.wikipedia.org/wiki/Longest_common_subsequence_problem