c# - 文本差异应用程序如何工作？

Question

诸如DiffMerge之类的应用程序如何检测文本文件中的差异，以及它们如何确定新行何时是新行，而不仅仅是在与被检查文件不同的行上？

这是相当容易实现的东西吗？是否已经有图书馆可以做到这一点？

Answer 1

这是作为 UNIX 命令行工具diff基础的论文。

Answer 2

其实很简单；DIFF 程序 - 大多数时候 - 基于最长公共序列，可以使用图形算法解决。

该网页提供了 C# 中的示例实现。

Answer 3

这是一个复杂的问题。执行差异意味着找到两个文件之间的最小编辑距离。也就是说，将一个文件转换为另一个文件所必须进行的最少更改次数。这相当于找到两个文件之间最长的公共行子序列，这是各种 diff 程序的基础。最长公共子序列问题是众所周知的，你应该可以在google上找到动态规划的解决方案。

动态编程方法的问题在于它是 O(n^2)。因此，它在大文件上非常慢，并且对于大的二进制字符串不可用。编写 diff 程序的难点在于针对您的问题域优化算法，以便获得合理的性能（和合理的结果）。Hunt 和 McIlroy 的论文“差分文件比较算法”很好地描述了 Unix diff 实用程序的早期版本。

Answer 4

有图书馆。这是一个：http ://code.google.com/p/google-diff-match-patch/

StackOverflow 使用 Beyond Compare 进行比较。我相信它可以通过从命令行调用 Beyond Compare 来工作。