NDiffDiff：文本文件的行和字符的 Diff 实现
5.00/5 (4投票s)
Lean and Mean 比赛的参赛作品
屏幕截图显示，按顺序
- 可见的添加
- 可见的文本更改
- 换行符删除
- 可见的删除
黑底白字行显示了文件的匹配部分，带有行号和计数。
引言
本文是为 精简高效 竞赛的参赛作品，该竞赛于 2009 年 8 月在 Code Project 上进行。
这是我继 NLineDiff 和 NLineDiffConsole 之后的第三篇文章。
第二个测试文件 *“grid2.html”* 显示有 5 处更改。我仍然没有找到最后一处：“对底层 HTML 标记的不可见更改”，但我认为我可以更好地处理“可见文本更改”，即在 *grid2.html* 的第 172 行插入“ lang="Text"”，以及在 *grid1.html* 的第 181 行末尾删除“换行符”。
背景
我将再次使用我在 70 年代初由 Douglas McIlroy 编写并由 Eugene W. Myers 在其论文中描述的 diff 算法的实现，该论文可在下载中找到。
然而这一次，运行了多个 diff。第一个 diff 像以前一样在完整行上运行。这揭示了两个输入文件之间的差异。这些差异可以分为由相同行分隔的多个部分。这些部分可以归类为文件 A 的删除、文件 B 的插入，或两者兼有。
有趣的部分是既有删除行又有插入行的部分。在这些部分中，行内可能存在匹配的文本，以及更小的实际差异。对于行的情况，所有差异都可以被认为是文件 A 的删除或文件 B 的插入。
对于这些部分中的每一个，diff 算法都会在部分的字符上运行。这次，我们寻找两个版本之间的相似之处。这些被记录并以更柔和的颜色显示在输出中，从而突出显示差异。
Using the Code
下载是一个 WinForms 应用程序，其中包含两个作为嵌入资源的测试文件，它们是默认加载的。您还可以通过提供两个命令行参数的路径来 diff 任意两个文件。该应用程序运行所有必需的 diff 并显示结果和一些计时测量。
输出
在我第一篇文章中，我使用了一个 WebBrowser 控件来渲染输出。这次，我制作了一个自定义控件，它继承自 ScrollableControl。它并不算很巧妙，但它可以在 10 毫秒多一点的时间内渲染测试文件的输出。
删除的文本显示为红色，而文件 A 的匹配文本显示为浅红色。类似地，插入的文本为绿色，而文件 B 的匹配文本为浅绿色。我认为这很好地突出了实际更改。
结果
由于这是为“精简而强大”竞赛提交的文章，这里有一些指标：
时间
屏幕截图中显示了测试用例的代表性时间测量。渲染输出的时间很长，但我很高兴多个 diff 仍然在 2 毫秒内完成。因此，结果的时间约为 **15 毫秒**，包括 JIT 时间约为 **70 毫秒**。
空间
最大的空间需求仍然是将文件作为 string[] 存储在内存中。对于测试用例，这大约需要 390 KB。两个主要的 Int32 数组的长度都约为 ( N + M )，其中 N 是文件 A 中的行数，M 是文件 B 中的行数。因此，计算出的空间需求对于结果来说仍然约为 420 KB。很难计算显示所占用的空间，但可以说这应该是框架的责任。
Process.PeakWorkingSet64 的变化始终在 1.5 MB 以下。
关注点
我选择复制 diff 算法的源代码来处理 string[] 和 char[] 的两种情况。这是因为算法的热路径是相等运算符。我本来可以使用泛型参数，用 where T : IEquatable<T> 限制它并调用 Equals，但这会大大减慢算法的速度。此外，JIT 编译器仍然需要处理这两种版本，所以没有收益。
我确实保留了两个大的 Int32 数组，并将它们重用于 char diff。这很有帮助，因为在 .NET 中，内存分配，尤其是垃圾回收，是非常昂贵的。另外，在这种特定的测试用例中，两个 char diff 所需的空间比第一个行 diff 要少，这也很有帮助。
自定义控件的渲染是线程安全的。这是必需的，因为 diff 是在后台线程上运行的，它需要在该线程上渲染输出。它使用 CreateGraphics，这是 Control 中 5 个线程安全成员之一。
历史
- 2009 08 31：初版