差分algorithm
我一直在寻找一个有效的差异algorithm解释疯狂。
我得到的最接近的是RFC 3284的链接 （来自几个Eric Sink博客文章），它以完全可理解的术语描述了存储差异结果的数据格式 。 然而，没有提到一个程序在做差异时如何达到这些结果。
我试图从个人的好奇心来研究这个问题，因为我确定在执行差异algorithm的时候一定要权衡一下，有时候当你看差异的时候就很清楚了，难怪“差异程序为什么select这个作为一个改变而不是那个？“…
有谁知道在哪里可以find一个有效的algorithm，最终会输出VCDIFF的描述？
顺便说一下，如果您碰巧find了SourceGear的DiffMerge使用的实际algorithm的描述，那就更好了。
注意：最长的公共子序列看起来不是VCDIFF使用的algorithm，看起来他们正在做更聪明的事情，因为它们使用的是数据格式。
谢谢！
一个O（ND）差分algorithm及其变化是一个神奇的文件，你可能想从那里开始。 它包括伪代码和一个很好的可视化的graphics遍历参与做差异。
本文的第四部分介绍了algorithm的一些改进，使其非常有效。
成功实现这个function将为您在工具箱中提供一个非常有用的工具（也可能有一些非常好的体验）。
生成你需要的输出格式有时可能会非常棘手，但是如果你对algorithm内部有了解，那么你应该能够输出任何你需要的东西。 您还可以引入启发式方法来影响输出并进行一定的权衡。
这里是一个包含一些文档， 完整的源代码和使用上述algorithm中的技术的差异algorithm的例子的页面。
源代码似乎紧跟在基本algorithm之上，易于阅读。
准备input也有一点，您可能会觉得有用。 当通过字符或标记（单词）进行区分时，输出会有很大差异。
祝你好运！
我将首先看看GNU 提供的 diff的实际源代码 。
为了理解源代码的实际工作原理，该包中的文档引用了启发它的论文：
基本algorithm在“AnO（ND）差值algorithm及其变体”中描述，Eugene W.Myers，'Algorithmica'Vol。 1986年第1期，第251-266页; 在“文件比较程序”中，Webb Miller和Eugene W. Myers，“Software – Practice and Experience”Vol。 1985年第11号，第1025-1040页。 该algorithm是独立发现的，如E. Ukkonen的“信息与控制”（Information and Control）卷“algorithm近似string匹配algorithm” 64，1985，第100-118页。
阅读论文，然后查看实现的源代码应该足够了解它是如何工作的。
请参阅http://code.google.com/p/google-diff-match-patch/
“Diff Match和Patch库提供强大的algorithm来执行同步纯文本所需的操作…目前可用于Java，JavaScript，C ++，C＃和Python”
另请参阅wikipedia.org Diff页面和 – “ Bram Cohen：diff问题已解决 ”
我来到这里寻找差异algorithm，然后做了我自己的实现。 对不起，我不知道vcdiff。
维基百科 ：从最长的公共子序列来说，获得差异性输出只是一个小小的步骤：如果一个项目在子序列中不存在，但存在于原始项目中，它必须被删除。 （下面的' – '标记。）如果它在子序列中不存在但在第二个序列中存在，则必须添加（“+”标记）。
这里的LCSalgorithm的好animation。
在这里链接到一个快速的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]
基于Emmelaich给出的链接， Neil Fraser网站（图书馆作者之一）的Diff Strategies也有很大差异。
他涵盖了基本的策略，并在文章的最后进展到Myer的algorithm和一些图论。
