C# 的 O(ND) 差异算法

• 下载源代码 - 42.2 Kb

最新版本可在 GitHub 上找到： https://github.com/mathertel/Diff/

引言

本文档讨论的是文本文件的比较，以及识别它们之间差异的最著名、最优秀的算法。您可以在下载的文件中找到实现了一个具有简单易用 API 的小型类，可以完成这项工作。您应该将此算法收录到您的算法库中。

除了实现算法的类之外，还有一个示例 Web 应用程序，可以比较两个文件并生成一个合并并着色文档的 HTML 输出。

该算法最早于 20 年前发表，标题为“An O(ND) Difference Algorithm and its Variations”，作者 Eugene Myers，发表在 Algorithmica Vol. 1 No. 2, 1986, p 251。您可以在 此处找到副本。在这篇文章中，您可以找到该算法的抽象递归定义，并使用一些需要迁移到现有编程语言的伪代码。

互联网上公开提供了许多 C、Java 和 Lisp 版本的该算法实现。在我编写 C# 版本之前，我发现几乎所有这些实现都来自同一来源（GNU diffutils），该来源是在（非自由的）GNU 公共许可证下提供的，因此在未经 GNU 许可证的约束下，不能将其作为商业或可再分发应用程序的源代码重用。

存在一些使用其他（较差）启发式算法的非常古老的 C 实现。微软也发布了一个使用某些树结构的 diff 工具（WinDiff）的源代码。此外，直接从 C 源文件迁移到 C# 并不容易，因为典型的 C 解决方案中有大量的指针算术，而我想要一个托管的解决方案。我尝试了很多来源，但没有找到针对 .NET 平台的可用解决方案。

这些就是我从头开始实现原始已发布算法的原因，并在 GNU 许可证限制之外，根据 知识共享署名 2.0 德国许可协议提供。此实现的历程可以追溯到 2002 年，当时我发布了一个 Visual Studio 插件，该插件也比较文件，请参见 Visual Studio 2005 插件，增加了 diff 工具、explore 命令、Subversion 支持和 Web 项目报告。在过去 3 年里我没有发现任何 bug，所以我认为代码相当稳定。

我不需要高性能的 diff 工具。我会根据需要进行一些性能调整，所以请告诉我。我在源代码中也提供了一些关于该主题的提示。

工作原理（简述）

您可以在 此处找到下载文件的在线工作版本。

• 比较两个大型文本文件的字符并不容易实现，而且往往很慢。比较数字要容易得多，因此第一步是为所有文本行计算唯一的数字。如果文本行相同，则计算相同的数字。
• 在计算这些数字之前，需要考虑一些选项，这些选项通常对某种类型的文本很有用：去除空格字符和不区分大小写比较。
• 核心算法本身将比较两个数字数组，准备工作在私有的 DiffCodes 方法中完成，并使用 Hashtable。
• 方法是 DiffText 和 DiffInts。
• 算法的核心由两个方法构建
  • LCS：这是最长公共子序列算法的递归分治实现。
  • SMS：此方法查找最短中间蛇（Shortest Middle Snake）。
• 为了获得可用的性能，我对原始算法做了一些修改。原始算法使用递归方法描述，并比较零索引序列，将这些序列的部分作为参数传递。提取子数组和重新连接它们非常消耗 CPU 和内存。为了避免将这些序列作为数组复制，在传递序列的同时传递使用的数组以及下界和上界，这样序列就不会一直被复制。这种情况使得 LCS 和 SMS 函数更加复杂。
• 我在 LCS 函数中添加了一些代码，以便对完全相同、完全删除或插入的子数组能快速响应，而不是递归地将其分析到单个数字的情况。
• 结果存储在两个数组中，用于标记两个数据数组中的修改（删除或插入）行。然后分析这些位以生成描述找到的差异的对象数组。
• 如果您想了解更多信息，请阅读原始文章。

API

要使用此功能，您只需调用 DiffText 方法之一。它们都接收一对字符串，并返回一个描述两个字符串之间插入和删除的项目数组。没有报告“更改”。取而代之的是，您可以找到一个“插入”和“删除”对。

DiffText(string TextA, string TextB)

查找两个文本之间的差异，通过文本行进行比较，没有任何转换。返回一个包含差异的项目数组。

DiffText(string TextA, string TextB, bool trimSpace, bool ignoreSpace, bool ignoreCase)

查找两个文本之间的差异，通过文本行进行比较，并进行一些可选的转换。返回一个包含差异的项目数组。

Diff(int[] ArrayA, int[] ArrayB)

查找两个整数数组之间的差异。返回一个包含差异的项目数组。

算法的示例应用程序

该示例是一个小型 Web 应用程序，它计算两个文本文件之间的差异，并使用 HTML 显示结果。

要设置示例，您需要创建一个 Web 项目，并将 zip 文件中的所有文件复制到该目录。算法的实现位于“diff.cs”类中。

进一步可能的优化（如果您真的需要速度）

（第一条规则：不要做；第二条规则：现在不要做。）

DataA 和 DataB 数组作为参数传递，但在创建后从未更改，因此可以作为类的成员来避免参数开销。在 SMS 中，for-D 和 for-k 循环中有大量的边界算术，可以通过递增和递减局部变量来完成。DownVector 和 UpVector 数组在每次调用 SMS 时都会被创建和销毁。通过将它们转移到类的成员来重用它们是可能的。

请参阅 TODO：提示。

Web 应用程序的安全问题

• 使用此网站实现可以使客户端查看您网站的 **所有** 源代码。请务必不要在公共服务器上直接使用它。
• 您应该实现参数检查，并且只允许对可显示的（基于文本的）文件进行 diff 输出。

许可证

此作品根据 知识共享署名 2.0 德国许可协议 或 BSD-3-Clause 许可协议 获得许可。

内置自检

该类现在具有内置自检功能，无需更改代码即可运行。如果您将 diff 和 debug 类文件一起编译，您将获得一个 EXE 文件，该文件测试了一些简单的 diff 场景，这些场景用于发现版本 1 和 2 中的 bug（通常是 OutOfArrayBounds）。

编译命令是

csc /target:exe /out:diffTest.exe /debug /d:SELFTEST Diff.cs Debug.cs

感谢您的反馈以及报告的两个未正确 diff 的情况。（总是我的错，不是算法的问题）。

历史

这项工作首次发布在 此处。

• 2002.09.20
  • 在某些情况下出现了“挂起”现象。
  • 现在，我对 SMS 算法有了更多的了解。
  • 曾出现过重叠的框；那些框被以不同的方式分析。一个返回点就足够了。
  • 在 debug 模式下，在 CreateDiffs 中添加了一个断言，该断言会计算两个数组中相等（未修改）行的数量。它们必须是相同的。
• 2003.02.07
  • 在某些情况下，Up/Down 向量数组出现越界错误。
  • 这两个向量现在使用不同的偏移量访问，这些偏移量使用起始 k-Line 进行调整。
  • 添加了一个测试用例。
• 2003.04.09
  • 另一个导致异常的测试被发现，但似乎已通过 2002.09.20 的工作得到修复。
• 2006.03.10
  • 重构了 API，将 diff 类的方法设置为静态方法，以简化使用。
  • 自检现在使用标准的 debug 类。
• 2023
  • 源代码可在 Github 上获取： https://github.com/mathertel/Diff/