使用最长公共子串的通用差分比较生成器

• 下载源代码 - 31.01 KB

引言

我最近的任务是创建一个系统，比较法律文件的两个版本，并显示所做的任何编辑。我选择通过使用递归的“分而治之”方法来解决这个问题，利用最长公共子串算法的修改版本。

背景

最长公共子串算法 (LCS) 已经存在一段时间了，并且最近作为比较 DNA 序列的一种方式重新引起了人们的兴趣。关于其工作原理的详细介绍可以在这里找到。LCS 的大多数标准实现都返回最长公共子串的长度；我修改了我的实现，使其也返回 LCS 在两个输入列表中的起始位置。

我的代码的总体思路是，它接受 2 个 IList<T> 的实例作为输入，其中 T 实现了 IComparable<T>。找到这些列表的最长公共子序列，并将其存储在一个标记为“未更改”序列的 DiffItem 对象中。这有效地将两个列表分成 3 个区域：LCS 之前的所有内容、LCS 和之后的所有内容。反过来，LCS 之前列表的前导区域会计算其 LCS，从而再次将该区域分成 3 个部分；对尾随序列执行相同的操作。一旦任何一个列表中都没有更多未检查的部分，递归就会停止。

使用代码 

主要函数是 Diff 类的 static 方法，称为 GetDiff，它接受 2 个 IList<T> 并返回一个 List<DiffItem>。 DiffItem 类只是一个持有类，包含一个 List<T> 和一个 DiffType 枚举值，该值可以是 Unchanged、Inserted 或 Deleted。这个 DiffItem 的集合可用于执行以下操作

• 要仅查看原始列表中的元素，请遍历集合并仅返回 Unchanged 和 Deleted 项
• 要仅查看新列表的元素，请遍历集合并仅返回 Unchanged 和 Added 项
• 要显示已更改内容的比较，请正常遍历集合并输出 Unchanged 项，并对 Added 和 Deleted 项应用一些修改或格式设置

附加的解决方案包含 2 个项目。 DiffDesc 包含算法的核心类，而 DiffDescTest 是一个测试控制台应用程序，它在执行目录中查找两个文本文件，分别名为“Original.txt”和“Changed.txt”。它加载这些文件，将每个文件拆分为一个 string 列表，其中每个 string 都是一个单词（以空格和换行符分隔）。创建 DiffItems 集后，将在执行目录中生成一个名为“Differential.htm”的报告，该报告显示两个输入以及显示更改的最终标记，类似于下面显示的。

Original	Changed	差异
这是第一句话，不会被更改。这句话将被删除。最后，这些结尾词也将保持不变。	这是第一句话，不会被更改。我是新插入的内容！！！最后，这些结尾词也将保持不变。	这是第一句话，不会被更改。这句话将被删除。我是新插入的内容！！！最后，这些结尾词也将保持不变。

兴趣点 

我的第一个实现执行的是字符比较，而不是整个单词的比较；但是我发现这“太敏感了”，检测到实际上没有任何语义意义的更改。即使它执行单词比较，我有时仍然会看到一些令人惊讶的输出。鉴于该解决方案的原始意图领域，即比较法律文件，这是有道理的；我的大脑不是将文档视为一系列单词，而是将其视为一系列概念或断言。真正要问的问题是“这两个文件的含义发生了什么变化”，而不是单词或字符的最小编辑距离。但是，真正的语义差异检测器超出了这个项目的范围。如果有人让这样的东西运行起来，在您去银行的路上给我发个消息！

我正在考虑的另一个增强是，我将要比较的文档很可能包含 HTML 标记。这意味着，当我在差异报告中插入 span 时，它们会破坏正确的 HTML 嵌套规则，因为该算法不知道标记和内容之间的区别。我倾向于一种解决方案，其中拆分文档的第一个准备阶段将能够只获取内容，但会记住内容区域之间的标记，以便可以将其重新插入到最终输出中。

历史

• 2009/4/25：发布原始版本