基于LCS的VB.NET通用差异比较

• 下载源代码 - 36.8 KB

引言

本文旨在说明如何以编程方式确定两个任意对象列表之间的差异，然后解释差异列表以创建“差异脚本” - 一个包含要在原始列表上执行的操作列表的脚本，以便最终得到目标列表。

背景

在我22年的开发生涯中，我遇到了很多情况，我认识到一个源和目标正在被更新。我一直梦想着差异更新将比覆盖整个目标更有效。

开发软件是让我完全理解（掌握）某种情况或问题的复杂性的方式。编写随附的源代码使我能够理解差异算法以及它如何和为什么起作用。在我的调查中，我使用了这个优秀的网站CodeProject和来自各种作者的文章，以及来自维基百科的现成信息。

使用代码

随附的代码包含一组一起工作的泛型类。

调用差异脚本引擎（它创建差异脚本）的方式如下

Dim a as string() = {"a", "b", "c"}
Dim b as string() = {"b", "c", "a"}
Dim script As DiffScript(Of String)
script = DiffEngine(Of String).MakeDiffScript(a, b)

这创建了一个差异脚本，其中包含一个修改条目，一个移动操作（将“a”项）移动到 c (3) 之后的位置。

工作原理

基本算法是最长公共子序列 (LCS) 算法，如本网站和其他文章以及维基百科中所述。

我包含了一种索引机制，该机制会将任意项的列表转换为要比较的整数列表。如果需要，索引允许将整数重新映射回原始值。

索引机制还会比较两个列表的开头和结尾，看看它们是否相等。LCS是一种相当密集的算法，并且仅在开始和结束相同的不同项目的“块”上执行。

关注点

在`DiffTestCode`和`IndexTestCode`类中，有一些测试代码，在您的实现中您不需要。

随附的代码使用了LCS算法的修改版本。唯一进行的修改是在回溯方法中。原始算法总是倾向于删除或添加操作（导致---+++），我对其进行了修改，使其在另一个 - 操作之前更倾向于在同一位置进行 + 操作。此修改使识别替换操作变得更容易。

源代码有大量注释，请查看源代码中的注释以获取更多信息。

历史

这是文章的第 1 版。我不希望代码发生很大变化，但你永远不知道。我确实打算在我有一些时间时扩展这篇文章；目前，大多数注释都位于源代码本身中。

随意在您自己的项目中使用该代码，并向我发送一些反馈 :P