C# 通用、可重用差异算法 - II

• 下载源代码文件 - 24 Kb
• 下载演示项目 - 14 Kb

引言

在我日常访问 CodeProject 时，我偶然发现了 Aprenot 的一个精彩文章：C# 通用 - 可重用差异算法。Aprenot 识别两个对象序列的最长公共序列的方法在处理小型数据集时效果非常好。但是，随着数据集的增大，该算法会开始受到现实的限制。

算法的核心是一个表，它存储了第一个集合中每个项目与第二个集合中每个项目的比较结果。尽管这种方法始终能产生完美的差异解决方案，但它可能会消耗大量的 CPU 和内存。作者通过一次只比较两个数据集的一小部分来解决这些问题。然而，这种解决方案假定数据集之间的更改非常接近，当数据集很大且更改分散时，它会报告效率低下的结果。

本文将介绍一种基于 aprenot 提出的算法。该算法的目标如下：

1. 保持通用和可重用的原始概念。
2. 正确处理大型数据集。
3. 大大降低必要的比较次数。
4. 大大降低内存要求。

问题定义

给定一个包含 100,000 个项目的 the 列表，需要将其与一个大小相似的列表进行比较，您很快就会看到使用一个表来存储结果的问题。如果结果表中的每个元素宽度为 1 位，您将需要超过 1GB 的内存。要填充该表，您将需要执行 100 亿次比较。

一些术语

总会有两组项目需要比较。为了区分这两组，它们将被称为源（Source）和目标（Destination）。我们通常提出的问题是：需要对源列表做什么才能使其看起来像目标列表？

通用和可重用

为了保持原始算法的通用性，需要一个通用的结构。我选择利用 C# 的 interface（接口）。

public interface IDiffList
{
     int Count();
     IComparable GetByIndex(int index);
}

目标列表和源列表都必须继承 IDiffList。假设列表的索引从 0 到 Count()-1。就像原始文章一样，使用 IComparable 接口来比较列表中的项目。

源代码中包含了两个利用此接口的结构；DiffList_TextFile 和 DiffList_BinaryFile。它们都知道如何将各自的文件加载到内存中，并将它们各自的项目作为 IComparable 结构返回。这些对象的源代码示例应该足以扩展该系统以适应其他对象类型。例如，该系统可以轻松地扩展到比较 DataSet 之间的行或驱动器之间的目录结构。

整体解决方案

前面提出的问题与排序算法中的差异非常相似。Shell sort 代码编写起来很快，但在数据集变大时效率非常低。Quick sort 在大型数据集上效率高得多。它使用递归将数据分成非常小的块。

此算法采用的方法类似于 quick sort。它将数据分成非常小的块，并通过递归处理这些小块。算法执行的步骤如下：

1. 查找当前项目的最长匹配序列 (LMS)。
2. 将此 LMS 存储在结果堆中。
3. 使用递归处理 LMS 上方剩余的所有数据。
4. 使用递归处理 LMS 下方剩余的所有数据。

这些步骤会递归地重复，直到没有更多数据需要处理（或未找到更多匹配项）。乍一看，您应该能够轻松理解递归逻辑。哪些内容需要进一步解释的是步骤 1。我们如何在不将所有内容与所有内容进行比较的情况下找到 LMS？由于此过程是递归调用的，我们难道不会最终重新比较某些项目吗？

查找最长匹配序列

首先，我们需要定义在哪里寻找 LMS。系统需要维护源列表和目标列表中的一些边界。这通过简单的整数索引来实现，称为 destStart、destEnd、sourceStart 和 sourceEnd。起初，这些将包含每个列表的整个范围。递归将在每次调用时缩小它们的范围。

为了找到 LMS，我们使用暴力循环并结合一些智能短路。我选择遍历目标项目，并将它们与可用的源项目进行比较。伪代码如下所示：

For each Destination Item in Destination Range
     Jump out if we can not mathematically find a longer match
     Find the LMS for this destination item in the Source Range
     If there is a match sequence
          If it’s the longest one so far – store the result.
          Jump over the Destination Items that are included in this sequence.
     End if
Next For

If we have a good best match sequence
     Store the match in a final match result list
     If there is space left above the match in both 
     the Destination and Source Ranges
          Recursively call function with the upper ranges
     If there is space left above the match in both 
     The Destination and Source Ranges
          Recursively call function with upper ranges
Else
     There are no matches in this range so just drop out
End if

跳转（Jumps）是该算法速度如此之快的原因。第一个数学跳转查看一些简单数学的结果：

maxPossibleDestLength = (destEnd – destIndex) + 1;
if (maxPossibleDestLength <= curBestLength) break;

此公式计算当前目标项目可能产生的理论上最佳匹配。如果它小于（或等于）当前最佳匹配长度，那么就没有理由继续遍历目标范围中的其余项目。

第二次跳转更像是一次信念的飞跃。我们通过跳过当前匹配序列内部的目标索引来忽略重叠的匹配序列，因此极大地减少了比较次数。这是一个非常大的速度提升。如果我们测试的列表包含大量重复数据，我们可能无法获得完美的解决方案，但我们会快速找到一个有效的解决方案。我在测试中发现，我不得不手动创建一组文件来演示不完美的解决方案。实际上，这种情况应该非常罕见。您可以注释掉源代码中的这个跳转，然后运行自己的测试。我必须警告您，这会大大增加大型数据集的计算时间。

在递归过程中，很有可能同一个目标项目需要再次被测试。测试的唯一区别是源范围的宽度。由于算法的目标是降低比较次数，因此我们需要存储之前的匹配结果。DiffState 是存储结果的结构。它包含源范围中第一个匹配项的索引和长度，以便我们知道匹配的范围有多大。DiffStateList 按目标索引存储 DiffState。循环会简单地请求特定目标索引的 DiffState，而 DiffStateList 要么返回一个预先计算好的，要么返回一个新未计算的。会执行一个简单的测试，以查看是否需要根据当前的目标和源范围重新计算 DiffState。DiffState 也会在适当的时候存储“无匹配”的状态。

如果 DiffState 需要重新计算，则会调用类似于上述的算法。

For each Source Item in Source Range
     Jump out if we can not mathematically find a longer match
     Find the match length for the Destination Item 
              on the particular Source Index
     If there is a match
          If it’s the longest one so far – store the result
          Jump over the Source Items that are included in the match
     End if
End for 

Store the longest sequence or mark as 'No Match'

跳转再次为我们带来了更快的速度，避免了不必要的项目比较。我发现第二次跳转将大型数据集的运行速度提高了 2/3。查找特定目标项目在特定源索引处的匹配长度，只需按顺序比较这些点的项目列表并返回连续匹配的数量即可。

收集结果

算法运行完毕后，您将得到一个包含有效匹配对象的 ArrayList。我使用一个名为 DiffResultSpan 的对象来存储这些匹配项。对这些对象进行快速排序可以将它们排列成所需的顺序。DiffResultSpan 还可以存储比较中必要的删除、添加和替换状态。

要构建最终的有序 DiffResultSpan 列表 ArrayList，我们只需遍历匹配项，填充它们之间的空白（未匹配）索引。我们将结果作为有序的 DiffResultSpan 列表返回，每个列表都包含一个 DiffResultSpanStatus。

public enum DiffResultSpanStatus
{
     NoChange, //matched
     Replace,
     DeleteSource,
     AddDestination
}

public class DiffResultSpan : IComparable
{
     private int _destIndex;
     private int _sourceIndex;
     private int _length;
     private DiffResultSpanStatus _status;

     public int DestIndex {get{return _destIndex;}}
     public int SourceIndex {get{return _sourceIndex;}}
     public int Length {get{return _length;}}
     public DiffResultSpanStatus Status {get{return _status;}}

     //.... other code removed for brevity
}

现在您可以根据应用程序的需要处理 ArrayList 了。

算法的弱点

当使用上述算法，并且数据集完全不同时，它将比较两个数据集中的所有项目，然后才发现没有任何匹配项。这对于大型数据集来说可能是一个非常耗时的过程。另一方面，如果数据集是等效的，它将在主循环的一次迭代中找到这一点。

虽然它应该总是能找到一个有效的差异，但算法有可能找不到最佳答案。我包含了一组文本文件来演示这个弱点（source.txt 和 dest.txt）。有一个由 5 个匹配项组成的序列被系统忽略了，因为它被一个较小的先前序列覆盖了。

算法更新 2004 年 6 月 10 日

为了解决上述第二个弱点，Diff Engine 添加了三个级别的优化。测试确定，大型、高度冗余的数据会产生极差的差异结果。添加了以下 enum（枚举）：

public enum DiffEngineLevel
{
     FastImperfect, //original level
     Medium,
     SlowPerfect
}

此枚举可以传递给附加的 ProcessDiff() 方法。该引擎仍然完全向后兼容，并将默认为原始的 Fast 方法。只有通过测试才能确定 Medium 或 SlowPerfect 级别是否对您的应用程序是必要的。这些设置之间的速度差异非常大。

这些级别的差异会影响我们在找到现有匹配运行时何时或是否跳过数据段。如果您有兴趣，可以在 ProcessRange() 方法中找到这些更改。它们从 Engine.cs 的第 107 行开始。

包含的文件

项目 DiffCalc 是用于测试算法的简单前端。它能够对两个文件进行文本或二进制 diff。

DLL 项目 DifferenceEngine 是所有工作完成的地方。

• Engine.cs: 包含如上所述的实际 diff 引擎。
• Structures.cs: 包含引擎使用的结构。
• TextFile.cs: 包含用于处理文本文件的结构。
• BinaryFile.cs: 包含用于处理二进制文件的结构。

特别说明

Structures.cs 中的第一行被注释掉了。如果您取消注释此行，通过使用 HashTable 而不是分配的数组来存储中间结果，您将降低算法的内存需求。它确实会使速度降低百分之一或二。我认为这是由于必需的反射。我希望未来的 .NET Generics 能够解决这个问题。

摘要

如果您退一步来看这个算法，您会发现它实际上是在构建 aprenot 原始文章中描述的表。它只是试图智能地跳过表的大部分区域。事实上，两个列表越相似，算法运行得越快。它还以更高效的结构而不是行和列来存储它计算出的内容。

希望其他人也能找到这个代码的好用途。我敢肯定，随着时间的推移，还会出现一些新的优化。当您发现它们时，请给我留言。

历史

• 2004 年 5 月 18 日 修复了 Engine.cs 第 106 行的“越界”错误。感谢 Lutz Hanusch 识别出此 bug。
• 2004 年 5 月 27 日 演示中的 Results.cs 第 96 行缺少了增量器。感谢 Cash Foley 识别出此 bug。
• 2004 年 6 月 10 日 速度优化导致了冗余数据上出现非常糟糕的 diff 结果。已添加两个较慢的 diff 引擎级别来解决此问题。感谢 Rick Morris 识别出此弱点。