差异算法？

Question

我一直看起来疯狂的解释一个有效的差异算法.

我得到的最接近的是RFC 3284的链接(来自几个Eric Sink博客文章),它以完全可以理解的术语描述了存储diff结果的数据格式.但是,它并没有提到程序如何在进行差异时达到这些结果.

我试图从个人的好奇心来研究这个问题,因为我确信在实现差异算法时必须进行权衡,当你看到差异并且想知道"为什么差异程序选择这个作为一个变化时,这很清楚而不是那个？"......

在哪里可以找到最终输出VCDIFF的高效算法的描述？
顺便说一下,如果您碰巧找到了SourceGear的DiffMerge使用的实际算法的描述,那就更好了.

注意:最长的公共子序列似乎不是VCDIFF使用的算法,考虑到它们使用的数据格式,它们看起来更聪明.

Answer 1

O(ND)差异算法及其变化是一篇很棒的论文,你可能想要从那里开始.它包括伪代码和执行差异所涉及的图遍历的可视化.

本文的第4部分介绍了算法的一些改进,使其非常有效.

成功实现这一点将为您提供工具箱中非常有用的工具(也可能是一些非常好的经验).

生成所需的输出格式有时会很棘手,但如果您对算法内部有了解,那么您应该能够输出所需的任何内容.您还可以引入启发式方法来影响输出并进行某些权衡.

这是一个页面,其中包括一些文档,完整的源代码,以及使用上述算法中的技术的diff算法的示例.

该源代码似乎紧跟基本算法和易于阅读.

还有一点准备输入,你可能会觉得有用.当您按字符或标记(单词)进行区分时,输出会有很大差异.

祝好运!

Answer 2

我首先看一下GNU 提供的 diff 的实际 源代码.

为了理解源代码的实际工作原理,该软件包中的文档引用了启发它的文章:

基本算法在"An O(ND)差分算法及其变体"中描述,Eugene W.Myers,'Algorithmica'Vol.1986年第1号,第251-266页; 在"文件比较程序"中,Webb Miller和Eugene W. Myers,"软件 - 实践与经验"卷.15 No. 11,1985,pp.1025-1040.如"用于近似串匹配的算法",E.Ukkonen,"Information and Control"Vol.中所述,独立地发现该算法.64,1985,pp.100-118.

阅读论文然后查看实现的源代码应该足以理解它是如何工作的.

Answer 3

请参阅https://github.com/google/diff-match-patch

"Diff Match和Patch库提供了强大的算法来执行同步纯文本所需的操作....目前提供Java,JavaScript,C++,C#和Python"

另请参阅wikipedia.org 差异页面 - " Bram Cohen:差异问题已解决 "

Answer 4

我来到这里寻找diff算法,然后我自己实现了.对不起,我不知道vcdiff.

维基百科:从一个最常见的子序列来看,获得类似差异的输出只是一小步:如果一个项目在子序列中不存在但存在于原始项目中,则必须将其删除.(下面的' - '标记.)如果子序列中不存在但存在于第二个序列中,则必须将其添加到.('+'标记.)

这里有LCS算法的精彩动画.

链接到这里的快速LCS ruby​​实现.

我的缓慢而简单的红宝石适应性如下.

def lcs(xs, ys)
  if xs.count > 0 and ys.count > 0
    xe, *xb = xs
    ye, *yb = ys
    if xe == ye
      return [xe] + lcs(xb, yb)
    end
    a = lcs(xs, yb)
    b = lcs(xb, ys)
    return (a.length > b.length) ? a : b
  end
  return []
end

def find_diffs(original, modified, subsequence)
  result = []
  while subsequence.length > 0
    sfirst, *subsequence = subsequence
    while modified.length > 0
      mfirst, *modified = modified
      break if mfirst == sfirst
      result << "+#{mfirst}"
    end
    while original.length > 0
      ofirst, *original = original
      break if ofirst == sfirst
      result << "-#{ofirst}"
    end
    result << "#{sfirst}"
  end
  while modified.length > 0
    mfirst, *modified = modified
    result << "+#{mfirst}"
  end
  while original.length > 0
    ofirst, *original = original
    result << "-#{ofirst}"
  end
  return result
end

def pretty_diff(original, modified)
  subsequence = lcs(modified, original)
  diffs = find_diffs(original, modified, subsequence)

  puts 'ORIG      [' + original.join(', ') + ']'
  puts 'MODIFIED  [' + modified.join(', ') + ']'
  puts 'LCS       [' + subsequence.join(', ') + ']'
  puts 'DIFFS     [' + diffs.join(', ') + ']'
end

pretty_diff("human".scan(/./), "chimpanzee".scan(/./))
# ORIG      [h, u, m, a, n]
# MODIFIED  [c, h, i, m, p, a, n, z, e, e]
# LCS       [h, m, a, n]
# DIFFS     [+c, h, +i, -u, m, +p, a, n, +z, +e, +e]

Answer 5

根据Emmelaich给出的链接,在Neil Fraser的网站上(图书馆的一位作者之一),Diff Strategies也有很大的发展.

他介绍了基本策略,并在文章的最后进展到Myer的算法和一些图论.