<分区>
我一直在寻找一个有效且有效的 diff 算法的解释。
我得到的最接近的是this link to RFC 3284 (来自几篇 Eric Sink 博客文章)，它以完全易于理解的方式描述了存储差异结果的数据格式。但是，它没有提及程序如何在进行比较时获得这些结果。
出于个人的好奇心，我正试图对此进行研究，因为我确信在实现差异算法时必须进行权衡，有时当您查看差异并想知道“为什么差异程序选择了这个”时，这一点非常清楚作为一个改变而不是那个？”...
我在哪里可以找到最终输出 VCDIFF 的高效算法的描述？
顺便说一下，如果您碰巧找到 SourceGear 的 DiffMerge 使用的实际算法的描述，那就更好了。
注意:最长公共(public)子序列似乎不是 VCDIFF 使用的算法，鉴于他们使用的数据格式，看起来他们正在做一些更聪明的事情。
最佳答案
An O(ND) Difference Algorithm and its Variations (1986, Eugene W. Myers) 是一篇很棒的论文，您可能想从这里开始。它包括伪代码和执行差异所涉及的图遍历的良好可视化。
论文的第 4 节介绍了算法的一些改进，使其非常有效。
成功实现这一点将使您的工具箱中拥有一个非常有用的工具(并且可能还会获得一些出色的体验)。
生成您需要的输出格式有时会很棘手，但如果您了解算法的内部结构，那么您应该能够输出您需要的任何内容。您还可以引入启发式方法来影响输出并做出某些权衡。
Here is a page其中包括一些文档，full source code ，以及使用上述算法中的技术的 diff 算法示例。
source code似乎紧密遵循基本算法并且易于阅读。
还有一些关于准备输入的内容，您可能会发现它很有用。当您按字符或标记(单词)进行区分时，输出会有很大差异。
关于algorithm - 差异算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/805626/