差异算法？

Question

我一直在疯狂地解释有效且高效的diff算法。

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

我试图出于个人好奇心进行研究，因为我敢肯定在实施diff算法时必须权衡取舍，当您查看diff并想知道“为什么diff程序为什么选择此作为更改时，这很清楚而不是那个？” ...

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

注意：最长的公共子序列似乎不是VCDIFF使用的算法，在给定使用的数据格式的情况下，它们看起来似乎在做些更聪明的事情。

Answer 1

O（ND）差异算法及其变体是一篇很棒的论文，您可能要从那里开始。它包括伪代码和进行比较时图形遍历的漂亮可视化。本文的第4节介绍了对该算法的一些改进，使其非常有效。成功实现这一点将为您提供一个非常有用的工具，并且可能会提供一些出色的经验。生成所需的输出格式有时可能很棘手，但是如果您了解算法的内部原理，那么您应该可以输出所需的任何内容。您还可以引入试探法来影响输出并进行某些折衷。这是一个页面，其中包含一些文档，完整的源代码以及使用上述算法中的技术的diff算法示例。该源代码似乎紧跟基本算法和易于阅读。还有一些准备输入的内容，您可能会发现这很有用。当您按字符或标记（单词）进行区分时，输出会有巨大差异。祝好运！