“diff”算法如何工作，例如在 VCDIFF 和 DiffMerge 中？ [已关闭]

Question

我一直在疯狂地寻找一种有效且高效的 diff 算法的解释。

我得到的最接近的是这个 RFC 3284 的链接（来自 Eric Sink 的几篇博客文章），它以完全可以理解的术语描述了存储差异结果的数据格式。然而，它没有提及程序如何在进行差异时达到这些结果。

我出于个人好奇心而尝试研究这一点，因为我确信在实现 diff 算法时必须进行权衡，有时当您查看 diff 并想知道“为什么 diff 程序选择它作为改变而不是那个？”...

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

注意：最长公共子序列似乎不是VCDIFF使用的算法。考虑到他们使用的数据格式，看起来他们正在做一些更聪明的事情。

Answer 1

An O(ND) Difference Algorithm and its Variations (1986, Eugene W. Myers) 是一篇很棒的论文，您可能想从这里开始。它包括伪代码和进行差异时涉及的图形遍历的良好可视化。

本文第 4 节介绍了对该算法的一些改进，使其非常有效。

成功实现这一点将为您的工具箱中留下一个非常有用的工具（也可能带来一些出色的体验）。

生成您需要的输出格式有时可能很棘手，但如果您了解算法的内部原理，那么您应该能够输出您需要的任何内容。您还可以引入启发式方法来影响输出并做出某些权衡。

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

源代码似乎紧密遵循基本算法并且易于阅读。

还有一些关于准备输入的内容，您可能会发现这很有用。当您按字符或标记（单词）进行比较时，输出存在巨大差异。

Answer 2

我首先会查看 diff 的实际 源代码 ，GNU 使其可用。

为了理解源代码的实际工作原理，该包中的文档引用了启发它的论文：

基本算法在“An O(ND) Difference Algorithm and its Variations”中描述，Eugene W. Myers，“Algorithmica”卷。 1 第 2 期，1986 年，第 251-266 页；并在“一个文件 Comparison Program”，Webb Miller 和 Eugene W. Myers，“Software--Practice and Experience”第 15 卷第 11 期，1985 年，第 1025-1040 页。该算法是独立发现的，如“近似字符串匹配算法”中所述，E. Ukkonen，《信息与控制》第 64 卷，1985 年，第 100-118 页。

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

Answer 3

参见 差异匹配和补丁

“差异匹配和补丁库 提供强大的算法来执行 同步所需的操作 纯文本。 ...目前可用 Java、JavaScript、C++、C# 和 蟒蛇”

另请参阅维基百科Diff页面和“Bram Cohen：差异问题已解决”

Answer 4

我来这里寻找 diff 算法，然后做了我自己的实现。抱歉，我不知道vcdiff。

Wikipedia：从最长的公共子序列中，只需一小步即可获得类似 diff 的输出：如果某个项目在子序列中不存在，但在原始序列中存在，则它一定已被删除。 （下面的“–”标记。）如果它在子序列中不存在，但出现在第二个序列中，则必须已将其添加进去。（“+”标记。）

这里有LCS 算法的漂亮动画。

在此处链接到快速 LCS Ruby 实现。

我缓慢而简单的 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 的网站（该库的作者之一）上还提供了差异策略的详细概述。

他介绍了基本策略，并在文章结尾处介绍了迈尔斯算法和一些图论。