176

我一直在寻找一种有效且有效的差异算法的解释。

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

出于个人的好奇心，我正在尝试对此进行研究，因为我确信在实现差异算法时必须进行权衡，有时当您查看差异并想知道“为什么差异程序选择这个作为更改时，这很清楚而不是那个？”...

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

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

4

5 回答 5

189

O(ND) Difference Algorithm and its Variations是一篇很棒的论文，您可能想从那里开始。它包括伪代码和执行 diff 所涉及的图形遍历的良好可视化。

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

成功实现这一点将为您的工具箱中留下一个非常有用的工具（并且可能还有一些出色的经验）。

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

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

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

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

祝你好运！

于 2009-08-21T17:23:00.227 回答
34

我将首先查看 GNU提供的 diff的实际源代码。

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

基本算法在“An O(ND) Difference Algorithm and its Variations”，Eugene W. Myers，'Algorithmica' Vol。1 1986 年第 2 期，第 251-266 页；在“文件比较程序”中，Webb Miller 和 Eugene W. Myers，“软件——实践和经验”卷。15 第 11 期，1985 年，第 1025-1040 页。该算法是独立发现的，如“近似字符串匹配算法”，E. Ukkonen，“信息和控制”卷。64，1985，第 100-118 页。

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

于 2009-04-30T06:41:07.723 回答
31

见https://github.com/google/diff-match-patch

“Diff Match 和 Patch 库提供了强大的算法来执行同步纯文本所需的操作。......目前在 Java、JavaScript、C++、C# 和 Python 中可用”

另请参阅wikipedia.org 差异页面和 - “ Bram Cohen：差异问题已解决”

于 2009-08-27T04:07:13.837 回答
13

我来这里是为了寻找差异算法，然后我自己实现了。抱歉，我不知道 vcdiff。

Wikipedia：从最长的公共子序列中，获得类似差异的输出只是一小步：如果子序列中不存在项目但原始项目中存在，则它必须已被删除。（下面的“-”标记。）如果它在子序列中不存在但出现在第二个序列中，则它必须已添加。（“+”标记。）

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]
于 2013-03-28T21:23:59.930 回答
10

根据 Emmelaich 给出的链接，在Neil Fraser 的网站（图书馆的作者之一）上也有大量的 Diff Strategies 。

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

于 2009-10-08T08:55:15.910 回答