简单的单词差异算法

Question

我目前正在寻找一种简单且轻量的算法来比较两个简单的字符串。

例如，如果我们采取这两个字符串：

• "The quick brown fox jumps over the lazy dog"
• "The plick brown fox tumps over the crazy dog"

它应该告诉我第二个单词的前两个字母不同等等。

现在我有一个非常简单的算法来比较单词：

/// <summary>
    /// Make a diff between two strings and returns words indices
    /// </summary>
    /// <param name="a"></param>
    /// <param name="b"></param>
    /// <returns></returns>
    public static List<int> Diff(string a, string b)
    {
        List<int> indices = new List<int>();

        string[] asplit = a.Split(' ');
        string[] bsplit = b.Split(' ');

        for (int i = 0; i < asplit.Length; i++)
        {
            if (bsplit.Length > i)
            {
                if (asplit[i].CompareTo(bsplit[i]) != 0)
                {
                    indices.Add(i);
                }
            }
        }

        return indices;
    }

这将告诉我哪些单词（使用空格字符拆分）是不同的。

我已经阅读了许多关于实现复杂算法或使用现有库的主题。

但是我受到了.NET compact framework (WP7)的限制，我不想要能够比较两个文件或两个文本的东西，我只需要进行单词比较。

有没有适合的库或算法呢？谢谢:)

- Valryon

---

如果在句子中间插入一个单词会导致匹配出现偏差，那么应该报告每个后续单词都不同吗？ - James Michael Hare

解决此问题的标准方法是实现最长公共子序列算法。这是一个相当直接的算法。我在这里有一个 JScript 实现：http://blogs.msdn.com/b/ericlippert/archive/2004/07/21/189974.aspx 将其转换为 C# 是留给读者作为练习的。 - Eric Lippert

@James Michael Hare：假设我有“我的小马”和“我的甜小马”，它应该只报告“甜”。我认为我的算法太简单了，无法处理这种情况。 - Valryon

@eric-lippert 感谢分享你的代码片段。我会尝试弄清楚它是如何工作的，看看它是否对我有帮助。 - Valryon

Answer 1

你可以看一下DiffPlex项目。

核心功能似乎在\DiffPlex\Differ.cs中。它甚至有一个Silverlight查看器，但可能需要一些移植。 编辑： 我想补充说明，DiffPlex特别支持单词比较，符合你的问题。它可能被淹没在其他字符、行等比较方法中，因此不太明显。

- Austin Thompson

---

这看起来非常不错，我会尝试集成仅核心功能，并查看它是否对我的小需求过于繁琐。 谢谢！ - Valryon

它非常有效，再次感谢。Diff核心非常轻巧而强大，具有易于理解的界面。使用附加示例（来自http://diffplex.codeplex.com/discussions/254392的UnidiffSeqFormater），我能够在几行代码中执行复杂的字符差异。 - Valryon