2 个回答
weakish
  • 24.5k
✓ 已被采纳

就是用了 @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算法是比较字与字的不同(比较适合于文档),其实也是一样的原理,只是把按行切割改成按单词或字符切割而已(当然,具体到某种语言,为了得出更有意义的结果,会有一些调整)。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏