文本差异化应用程序是如何工作的？

Question

7

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

这是否很容易实现？是否已经有库可以完成这个任务？

- scottm

4个回答

4

其实很简单；大多数情况下，DIFF程序都是基于最长公共子序列问题，可以使用图算法解决。

这个网页提供了C#的示例实现。

- beef2k

4

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

动态规划方法的问题在于它的时间复杂度是O(n^2)。因此，在处理大文件和大型二进制字符串时速度非常慢，无法使用。编写差异程序的难点在于针对您的问题领域优化算法，以获得合理的性能（和合理的结果）。Hunt和McIlroy的论文“差分文件比较算法”提供了Unix diff实用程序早期版本的良好描述。

- Peter Ruderman

我将要比较的文件非常小，只有10-50行，因此算法的速度不是问题。 - scottm

而Kristo已经提到了一篇将其简化为O(ND)的论文。 - beef2k

4

StackOverflow 在其差异比较中使用Beyond Compare。我相信它通过从命令行调用Beyond Compare来进行。

- Nosredna

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michael Kristofik · Accepted Answer

这是 UNIX 命令行工具 diff 的基础论文，论文链接。