Diff 算法？

我一直在疯狂地寻找一个有效的差异算法的解释。

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

出于个人好奇，我试图研究这个问题，因为我确信在实现一个 diff 算法时一定会有一些权衡，当你看到一些差异并想知道“为什么 diff 程序选择这个作为改变而不是那个?”...

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

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

92906 次浏览
小开

我将首先查看用于 diff 的实际 源代码，这是 GNU 生成的 有空。

为了了解源代码实际上是如何工作的，包中的文档引用了启发它的论文:

基本算法在“一个 O (ND)差分算法及其变化”，尤金 · W · 迈尔斯，“算法”第1卷第2期，1986年，第251-266页; 和“ A 文件 “比较计划”，韦伯 · 米勒和尤金 · W · 迈尔斯，《软件——实践和经验》 ，第15卷，第11期，1985年，第1025-1040页。该算法是独立发现的，如《字符串近似匹配的算法》 ，E. Ukkonen，《信息与控制》 ，1985年第64卷，100-118页所述。

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

小开
最佳答案

O (ND)差分算法及其变化(1986，Eugene W. Myers) 是一篇很棒的论文，你可能想从那里开始。它包括伪代码以及完成 diff 所涉及的图遍历的可视化。

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

成功地实现这一点将使您的工具箱中有一个非常有用的工具(可能还有一些非常好的经验)。

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

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

源代码似乎严格遵循基本算法，并且易于阅读。

还有一些关于准备输入的内容，您可能会发现这些内容很有用。当您按字符或标记(单词)进行区分时，输出会有很大的差异。

祝你好运！

小开

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

”差异匹配和补丁库 提供健壮的算法来执行 同步所需的操作 纯文本... 目前可用 在 Java，JavaScript，C + + ，C # 和 巨蟒

还可以看到 维基百科 Diff 页面和-“ 布拉姆 · 科恩: 难题已经解决了”

小开

基于 Emmelaich 给出的链接，尼尔 · 弗雷泽的网站(图书馆的作者之一)上也有一个很好的 Diff Strategies。

他涵盖了基本的策略，并在文章的最后进展到 Myer 的算法和一些图论。

小开

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

Wikipedia : 从一个最长的普通子序列得到类似 diff 的输出只是一个很小的步骤: 如果一个项目在子序列中不存在，但在原始序列中存在，那么它一定已经被删除了。(下面的“-”标记)如果它在子序列中不存在，但在第二个序列中存在，那么它必须被添加进去。(“ +”标记。)

这里是 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]

提交答案