VB.NET 快速 Diff 算法

• 下载源代码 - 43.5 Kb

引言

本文介绍了一个 Visual Basic .NET 实现的 diff 算法，该算法用于比较两个文本流或类似的类对象列表，并生成一个“编辑脚本”，该脚本解释了如何通过删除、插入或复制行来从旧版本转换到当前版本。与直接重新实现经典的 C 算法不同，此版本利用了 VB.NET 的强大功能来保持代码的简洁，并采用了几个新颖的技巧来减少所需的处理量，从而提高了执行速度。

背景

不久前，我正在寻找一个用于“diff”类型程序的算法，发现了 Aprenot 的文章 A Generic - Reusable Diff Algorithm in C#。我想理解底层算法，因为大多数此类程序都是用 C 或其变体编写的，而我想使用 VB。Aprenot 的文章清晰典范，专注于代码的 *作用* 而非 *如何* 实现，我推荐任何想理解 diff 算法实际作用的人阅读它。

在后续文章 A Generic, Reusable Diff Algorithm in C# - II 中，Michael Potter 指出了 Aprenot 算法的一些问题，特别是其需要构建一个表来存储比较所有先前和当前项对的结果，这在处理时间和内存方面可能非常昂贵。我认真考虑了 Michael 的顾虑，但开发了一种不同的方法，在此进行解释。

我的这个算法版本为每行文本计算一个哈希码。在每个阶段，算法使用哈希表查找候选匹配项，检查这些候选项是否实际匹配，然后找到对角线序列的长度。每个对角线序列都保存在一个临时集合中，以便随后轻松识别最长的序列。这样，实际执行的匹配次数大大减少，并且永远不需要构建完整的匹配表。

由于我只关心比较文本文件，因此我的实现不像其他版本那样“通用”。但是，创建一个类似于我的“文本行”类的通用接口，并将“文本行”类实现为一个用于比较的 IComparable 类型接口，将是一个相对简单的任务。

算法概述

有关核心 diff 算法工作原理的非常清晰的描述，请参阅 Aprenot 的先前文章。这是“精简版”...

下图显示了两个对象数组，在本例中是字符，但它们也可以是完整的文本行或其他对象。它们沿着矩阵的轴排列，“先前”（原始）文本位于顶部，“当前”（新）文本位于侧面。黑方块表示“先前”和“当前”项相同的情况。

我们要生成一个“编辑脚本”，告诉我们对“先前”文本执行哪些操作才能将其转换为“当前”文本。这实际上是一组指令，用于从左上角框导航到右下角框。在每个阶段，我们可以执行以下三种操作之一：

• 从先前文本中删除一项或多项。在执行此操作时，我们可以将“工作位置”向右移动相应的位数。
• 插入当前文本的一项或多项。在执行此操作时，我们可以将“工作位置”向下移动相应的位数。
• 将先前文本的一项或多项原样复制。在执行此操作时，我们沿着黑色方块的对角线向下向右导航。

最高效（即最短）的编辑脚本将尽可能多地使用对角线（复制）序列。该算法的工作方式是，从给定的起始位置开始，我们向右和向下扫描，寻找对角线序列的开头。如果我们找到一个或多个，我们将移动到其起始位置（通过删除现有项或插入当前项，视情况而定），然后发出一个适当的“复制”命令。如果当前位置的右侧或下方没有对角线序列，我们只需删除我们列中的先前项，插入我们行的当前项，向下移动一个对角线位置，然后重新开始。

当我们到达右边缘或下边缘时，我们执行最后一个命令以到达右下角位置。

VB 版本中的性能改进

Aprenot 的版本是该算法的一个非常直接的实现。在构建了两个对象数组之后，它会构建一个大型内存表来表示所有比较，并对其进行导航以生成编辑脚本。

Michael Potter 正确地认识到这会消耗大量内存和处理器资源，并使用“滑动窗口”技术改进了 Aprenot 的实现，该技术减少了比较次数和比较表所需的空间。

但是，我认为这仍然需要太多的比较，于是我想出了一个不同的策略。

• 在将每个项加载到数组时，我们会派生一个“哈希码”，这个数字以某种方式（细节不重要）表示项的内容。对哈希码的要求是，它对于相同的项必须具有相同的值，同时“误报”不能太多，并且计算成本要低。
• 我们创建一个“哈希表”，它允许我们查找给定的哈希值并找到指向所有匹配的“先前”和“当前”项的指针。
• 从矩阵的给定起始位置开始，我们查找当前列的哈希码，并使用哈希表查找同一列中的任何潜在匹配行（即，我们位置下方或在此位置的可能黑方块）。我们通过实际比较来检查任何潜在匹配项，当这些匹配成功时，我们沿着对角线向下进行实际比较，直到匹配行结束。我们将每个对角线序列的位置和长度记录在一个临时表中。
• 从相同的起始位置开始，我们重复此过程以查找在同一行开始的任何匹配序列。
• 我们扫描我们构建的匹配列表以找到最长的匹配项，然后跟随它。如果没有匹配项，我们向下移动对角线。
• 我们丢弃匹配表，然后重新开始。

哈希表意味着我们永远不会进行任何可能不成功的初始比较。从好的起始点跟随对角线序列意味着我们实际上只是在“走黑线”。在大型文本文件包含一些长相同部分的情况下，此策略使用的比较次数是可能总数的一小部分。

我的代码大量使用了 VB 集合。它们是构建对象索引数组的便捷方式，并且可以通过删除所有引用来销毁，从而减少了代码量。此外，我将每个文本版本保存在一个 CText 类中，因此要对同一文本的连续版本进行重复比较，我可以简单地将“先前”文本指向上次的“当前”CText 对象，创建一个新的“当前”CText 类，然后重新开始。

代码跟随

该示例被编译为一个简单的 EXE 文件，带有一个简单的测试驱动程序窗体，但很容易将其转换为 ActiveX DLL - 只需删除窗体，更改项目类型，并确保 CTextProcessor 是公共的。以下各节将逐一描述窗体和类，按执行顺序排列。

frmDiffTest

这是一个简单的窗体，它显示文本的当前版本、先前版本、更改（编辑脚本）以及“重构”的文本，即通过将编辑脚本应用于先前版本得到的文本——如果一切正常，这应该与当前版本相同。

代码几乎是微不足道的——在窗体打开时实例化一个 CTextProcessor 类型的对象，并且 cmdProcess_Click 方法调用其公共属性和方法来设置“先前”文本，获取将先前文本转换为“当前”文本所需的编辑脚本，并将此与先前文本组合起来以检查是否正常工作。

CTextProcessor

这是控制器/外观类。它公开文本的两个版本和差异脚本的公共变量。这些映射到三个私有 CText 对象，它们管理和解析文本。更简洁的代码版本将为此使用属性过程，但现有版本对于大多数用途来说已经足够。一个名为 Matches 的私有集合保存我们在查找对角线路径时找到的匹配项的详细信息（见上文）。一组字符串常量控制编辑脚本的格式，并且应该相当容易理解。

该类有两个公共成员：

• ProcessText 用于生成编辑脚本。它首先将“先前”文本和 CText 类设置为旧的“当前”值，然后创建一个新的 CText 对象作为 moCurrentText，并将提供的文本添加到其中，这将导致 CText 对象将文本拆分为行并构建哈希表。编辑脚本对象被初始化，代码会检查当前文本和先前文本相同的简单情况。如果不相同，则控制权传递给私有函数 ProcessChanges。
• ReconstituteText 将提供的编辑脚本应用于“先前”文本，可以使用第二个参数可选地覆盖它。在进行一些初始化（包括使用 CText 对象将脚本拆分为行）后，它首先检查脚本的第一行以处理两种简单情况。如果未找到这些情况，它将逐行应用脚本的其余部分，将行从 moPreviousText 移动到临时 CText 对象，并根据指示进行复制、跳过或插入新行。最后，它使用 CText.GetFullText 返回重构的文本。

ProcessChanges() 执行实现算法的大部分实际工作。鉴于其他类设置的数据结构，它是算法的一个相当直接的实现（请参阅上面的 算法概述）。

• 在检查没有先前文本的简单情况（因此更改脚本只是新文本）后，它会进入一个循环，当到达当前和先前文本的最后一行时退出。
• 循环首先检查两个结束情况：当前文本有剩余但先前文本没有，或者反之亦然。这些情况分别通过复制或删除足够的行来处理。
• 假设我们仍在处理两组文本，然后我们扫描当前行和列以查找匹配项。Matches 集合被重新初始化，扫描由两个内部循环完成，一个使用“当前”文本的当前行，一个使用“先前”文本的当前行。CText.GetNextLine() 方法用于使用哈希表查找候选匹配项。对于每个候选匹配项，代码然后调用 ProcessMatch，后者沿着对角线行走，记录两个文本字符串实际相同的长度，并将匹配项添加到 Matches 集合。
• 调用 FindBestMatch 只是扫描 Matches 集合并返回最佳（最长）匹配项。
• 给定最佳匹配项，代码然后通过删除先前文本中的行或插入当前文本中的行（视情况而定）来导航到正确的起始点，然后向差异脚本添加一条指令以复制相应匹配项的相应数量的先前行。
• 差异脚本是通过向 moDifferenceScript CText 对象添加行来构建的，完成后，使用 GetFullText 方法将其转换为 DifferenceScript 公共变量中的文本。

其余两个私有方法 ProcessMatch 和 FindBestMatch 的代码应该不言自明。如果您想使比较方法更通用，主要的更改将是 ProcessMatch。

CText 和 CTextLine

CText 将输入文本表示为 CTextLine 对象的集合。

CTextLine 非常简单，将行号和行文本的哈希值作为公共变量公开，并通过一对属性过程公开行文本本身。唯一重要的处理是，当设置行文本时，它会调用一个私有例程（CalculateHash）来计算哈希值。CalculateHash 的细节不重要，只要它始终为相同的文本生成相同的值，具有合理数量的不同输出值，并且处理成本低廉即可。我决定使用从字符串长度以及第一个和最后一个有效字符（忽略末尾的任何 NL 或 CR）派生的字符串哈希值（尽管数值也可以）。

CText 公开文本行集合和四个方法：

• AddText 可选地重置内部变量，然后添加指定的文本。它通过在每个回车符处将文本拆分为行，然后调用 AddLine 来实现。
• AddLine 创建一个新的文本行对象，设置其文本（这将同时计算其哈希值），并将其添加到 TextLines 集合中。然后它设置该行的行号，并将该行添加到私有哈希表集合（CHashTable 对象）。
• GetFullText 只是将 TextLines 中所有行的文本按顺序附加在一起，将文本作为单个字符串返回。
• GetNextLine 调用私有 CHashTable 对象的 GetNextLine 方法，返回与目标哈希值匹配的下一个文本行（如果存在）。

CMatch

这是一个非常简单的“仅数据”类，用于保存匹配项（对角线序列）的详细信息，包括其在当前和先前文本中的起始位置以及长度。

CHashTable

这为每个 CText 对象实现了“哈希表”。它实际上是一个“CText 对象集合的集合”，首先按哈希值键控，然后按行号键控。

当 CText 调用 AddTextLine 时，后者首先检查父集合（moHashTable）中是否存在一个键等于新行哈希值的项。如果存在，则该项实际上是 CTextLine 对象的集合，这些对象将被操作。如果不存在，则创建一个新集合并将其添加到父集合中。然后代码将传入的 CTextLine 对象添加到该集合中，键为行号（字符串形式）。由于行是按它们在原始文本中出现的顺序添加的，因此每个行集合将自动按行号顺序排列。

GetNextLine 接收哈希值和起始行号作为输入值。它在 moHashTable 中查找匹配行（如果存在）的集合，然后对其进行扫描以查找行号大于或等于起始行号的第一个条目。如果找到匹配项，则将其作为行号返回给调用代码。

两个例程都使用内部例程 DoesItemExist，该例程简化了在集合中查找匹配项而不会出现未处理错误的任务。

错误处理

大多数代码只是将错误传递给堆栈。顶层例程有一个 Catch 部分，它调用 FormErrorHandler 来进行错误日志记录，然后使用 frmErrorDetails 显示错误详细信息。如果代码被重新托管在将其错误传递给调用者的组件中，则不需要 frmErrorDetails 和 FormErrorHandler。

历史

• 原始版本 - 2005 年 2 月 4 日。

  请注意，这是为概念验证原型快速开发的。肯定会存在一些错误，但希望不多！

最后

尽情享用，如有任何评论，请随时反馈。