65.9K
CodeProject 正在变化。 阅读更多。
Home

C# 中的通用可重用 Diff 算法

aprenot
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.69/5 (25投票s)

2004年4月21日

6分钟阅读

viewsIcon

199775

downloadIcon

1440

一种可用于查找对象之间差异的通用算法。

引言

这是一个用于查找两个对象之间差异的通用算法，无论其类型如何。该算法使用 ICompare 接口来判断项目是否相同。这或许可以用于在 ASP.NET 中生成 WiKi 站点并跟踪修订。

我只想告诉所有读者，我没有计算机科学学位，也没有阅读或学习过很多关于算法设计的东西。我以前从未真正分析过 Diff 算法，但我对它们略知一二。如果有任何改进的方法，或者我完全走错了方向，请告诉我。

背景

我不太确定其他 Diff 算法（例如 UNIX Diff 实用程序）的工作细节，但我确实从关于该主题的一般阅读中获得了一些想法。Diff 引擎使用一个位矩阵，该矩阵采用两个文件的滑动窗口。该矩阵看起来有点像这样

黑色的方块是匹配项目的方块。算法从 0,0 开始，沿着 x 轴一直寻找对角线序列，即连续两个或更多匹配字符。算法寻找最长的序列，如果长度相同，则使用其中较近的一个。然后它沿着 y 轴向下看，如果它发现一个比在 x 轴上找到的任何序列都更长且更近的序列，它就使用该序列。如果它发现一个序列，它就执行任何必要的操作以到达该序列。在这种情况下，它不会在 0 x 轴或 y 轴上找到对角线序列，因此它执行其标准操作，即删除 'B' 并插入 'N'。然后它递增我们的 x 和 y 位置，所以我们现在在 1,1。同样，我们没有找到对角线序列，所以我们再次执行标准操作。然而，在 2,2 我们发现我们处于一个序列中。

一旦我们找到一个序列，首先我们将窗口滑动到我们所在的位置，因为我们不再需要任何先前的字符。然后，我们不断增加 x 和 y，直到它们到达一个不匹配的方块。在 4,4 处没有匹配项，所以我们再次切换状态，这意味着我们向下滑动窗口，并再次寻找对角线。现在，在 x 轴 4 处，我们在 4,8 处找到一个对角线，所以现在必须执行任何必要的操作才能到达那里。沿 y 方向移动是插入操作，所以我们插入“T”、“h”、“e”和“ ”。在那一点，我们进入对角线，保存状态等。

我们沿着对角线一直走到最后。很简单，对吧？

使用代码

我编写此代码的目的是使其尽可能通用，因此我围绕 3 个基本类和一个接口构建了它。实际上还有更多的类，但我稍后会介绍它们。

首先，要进行比较，您需要子类化 ComparableStreamReader。这是一个我创建的抽象类，它只有一个方法，GetNext()，该方法返回一个实现 IComparable 接口的对象。这确实是关键所在。在演示中，我包含了一个名为 ComparableStringReader 的类，它只是一个接一个地从字符串中返回字符。如果您查看代码，您会注意到它实际上返回的是带有一个字符的字符串，而不是 char 对象。我能说什么呢——string 已经实现了 IComparable，而且我很懒。但是，如果您想比较非字符串的项目，您可能需要创建自己的实现 IComparable 的自定义对象。

public class ComparableStringReader : Diff.ComparableStreamReader
{
    protected string    _source;
    protected int        _location;
    public ComparableStringReader(string source)
    {
        _source = source;
        _location = 0;
    }

    public override IComparable GetNext()
    {
        if ( _location < _source.Length ) 
            return _source.Substring(_location++, 1);
        else 
            return null;
    }
}

创建读取器类后，您只需创建 DiffEngine 类的一个实例。DiffEngine 有两个属性和一个方法 Compare()。Compare 接受两个 ComparableStreamReader，即源（原始）和目标（更改后的文档）。Compare() 返回一个 EditScript 对象，它只是 DiffCommands 对象的集合。但在我深入探讨 DiffCommand 对象之前，我想提一下这两个属性。属性 WindowSize 是一个整数，默认为 256。但是您必须小心这个数字。它越高，Diff 脚本将越精确和简洁，但它以 (n2/8) 的速率使用内存。没错。所以当为 256 时，我们只使用 8K 内存来存储矩阵（它实际上被称为编辑图）。但是，如果我们决定将它提高到 1024，我们就不会使用 128K。此外，窗口大小越大，计算所需的时间越长，大约以相同的速度（我不太确定如何使用大 O 符号，只读过它，所以我不给它）。对于大多数情况，255 应该运行良好，特别是如果您一次比较整行。

DiffEngine de = new DiffEngine();
de.WindowSize = 10;        // very small window for a small script

// create string readers
ComparableStringReader csrSource = new ComparableStringReader(txtSource.Text);
ComparableStringReader csrDest = new ComparableStringReader(txtDestination.Text);

// do the compare
EditScript es = de.Compare(csrSource, csrDest);

现在，一旦 Compare() 方法返回，它会返回一个脚本（该脚本通过 Script 属性可用）。正如我之前所说，EditScript 是一个 DiffCommand 集合。每个命令都表示必须对源（原始）执行的操作，以生成目标（更改的文档）。有三种类型的命令，它们是 DiffCommandType enum 的成员。它们是 Insert、Delete 和 Skip。Skip 和 Delete 命令使用 DiffCommand 类的 Length 属性，而 Insert 命令使用 Value 属性。Length 属性仅表示重复操作的次数。Value 属性表示要插入的对象，它也是从 ComparableStreamReader.GetNext() 返回的精确对象。

在示例中，我使用了 EditScript 来提供源字符串和目标字符串的展开视图，以便您可以看到它们的共同点。我还生成了一个**非常**简单的 Diff 脚本，可用于从原始字符串重新创建目标字符串。

B i t     Matrix
 N ot The Matrix
-1+N-1+o*2+T+h+e+ *6

在此示例中，Diff 脚本使用三个运算符 - '*' 表示**跳过**，后跟要跳过的字符数；'-' 表示**删除**，后跟要删除的字符数；'+' 表示**插入**，后跟要插入的字符。

最终，我将编写一个方法来合并源和 EditScript 以重新创建原始文件，但首先，我想做一些更好的测试，以确保此算法实际可行。如果您成功使用它，请告诉我。此外，如果您对改进算法有任何建议，也请告诉我。

关注点

此算法采用了一个可重用的 BitMatrix 类，以减少内存使用。如果您愿意，可以将其更改为仅使用 bool 值。这可能会或可能不会加速算法，因为您将使用八倍的内存（除非 C# 编译器进行了大量优化！）。

历史

  • 2004 年 4 月 21 日 - 0.9 版本发布。
© . All rights reserved.