Simple word diff algorithm

Question

I am currenlty looking for a simple and lightweight algorithm to compare two simple strings.

For example, if we take those two strings :

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

It should signals me that the 2 first letters of the second word are different, etc.

For now I have a very simple algorithm that compares words :

/// <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;
    }

So this is going to tell me which words (using a split on space characters) are different.

I've read many topics around here about implementing complex algorithm or using an existing library.

But I am retrained by the .NET compact framework (WP7) and I don't wan't something that can compare two files or two texts, I just need a word comparison.

Is there any library or algorithm that could fit ? Thanks :).

Answer 1

You might take a look at the DiffPlex project.

The core functionality looks like it's in \DiffPlex\Differ.cs It even has a Silverlight viewer but it might require some porting.

Edit:

I wanted to add that DiffPlex specifically supports word comparison as per your question. It might have not been obvious being buried among all the other character, line, etc. comparison methods.