差分algorithm

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

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

我试图从个人的好奇心来研究这个问题,因为我确定在执行差异algorithm的时候一定要权衡一下,有时候当你看差异的时候就很清楚了,难怪“差异程序为什么select这个作为一个改变而不是那个?“…

有谁知道在哪里可以find一个有效的algorithm,最终会输出VCDIFF的描述?
顺便说一下,如果您碰巧find了SourceGear的DiffMerge使用的实际algorithm的描述,那就更好了。

注意:最长的公共子序列看起来不是VCDIFF使用的algorithm,看起来他们正在做更聪明的事情,因为它们使用的是数据格式。

谢谢!

    5 Solutions collect form web for “差分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和一些图论。