Word by word diff comparison of two strings in .NE

问题:

I need to do Word by word comparison of two strings. Something like diff, but for words, not for lines.

Like it is done in wikipedia http://en.wikipedia.org/w/index.php?title=Horapollo&action=historysubmit&diff=21895647&oldid=21893459

In result I want return the two arrays of indexes of words, which are different in two string.

Are there any libraries/frameworks/standalone_methods for .NET which can do this?

P.S. I want to compare several kilobytes of text

回答1:

Actually, you probably want to implement a variation of the Local Alignment/Global Alignment algorithms we use in DNA sequence alignments. This is because you probably cannot do a word-by-word comparison of the two strings. I.e:

The quick brown fox jumps over the lazy dog
The quick fox jumps over the lazy dog

In other words, if you cannot identify insertions and deletions of whole words, your comparison algorithm can become very sc(r)ewed. Take a look at the Smith-Waterman algorithm and the Needleman-Wunsch algorithm and find a way to adapt them to your needs. Since such a search space can become very large if the strings are long, you could also check out BLAST. BLAST is a very common heuristic algorithm, and is pretty much the standard in genetic searches.

回答2:

It seems I've found needed solution:

DiffPlex is a combination of a .NET Diffing Library with both a Silverlight and HTML diff viewer. http://diffplex.codeplex.com/

But It has one bug. In those lines "Hello-Kitty" "Hello - Kitty", the word "Hello" will be marked as difference. Although the difference is space symbol.

回答3:

Use RegularExpressions.

Like in the example:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;
using System.Collections.Specialized;

namespace WindowsApplication10
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void button2_Click(object sender, EventArgs e)
        {
            decimal discrimation = 0.75M;
            string formHeading = "The brown dog jumped over the red lazy river, and then took a little nap! Fun!";
            string userSearch = "The brown dog jumped over the red lazy river, and then took a little ";
            //string userSearch = "brown dog nap fun";
            decimal res = CompareText(formHeading, userSearch);

            if (res >= discrimation)
            {
                MessageBox.Show("MATCH!" + res.ToString());
            }
            else 
            {
                MessageBox.Show("does not match! " + res.ToString());
            }
        }


        /// <summary>
        /// Returns a percentage of 1 on how many words were matched
        /// </summary>
        /// <returns></returns>
        private decimal CompareText(string formHeading, string userSearch)
        {
            StringCollection formHeadingWords = new StringCollection();
            StringCollection userSearchWords = new StringCollection();
            formHeadingWords.AddRange(System.Text.RegularExpressions.Regex.Split(formHeading, @"\W"));
            userSearchWords.AddRange(System.Text.RegularExpressions.Regex.Split(userSearch, @"\W"));

            int wordsFound = 0;
            for (int i1 = 0; i1 < userSearchWords.Count; i1++)
            {
                if (formHeadingWords.Contains(userSearchWords[i1]))
                    wordsFound += 1;
            }
            return (Convert.ToDecimal(wordsFound) / Convert.ToDecimal(formHeadingWords.Count));
        }
    }
}

回答4:

you can replace all the words in your 2 texts with unique numbers, take some ready made code for Edit distance computation and replace it's character to character comparison with number to number comparison and you are done!

I am not sure if there exists any library for exactly what u want. But you will surely find lots of code for edit distance.

Further, depending on whether you want to actually want to allow substitutions or not in the edit distance computation, you can change the conditions in the dynamic programming code.

See this. http://en.wikipedia.org/wiki/Levenshtein_distance

回答5:

You might try this, though I am not sure it's what you are looking for StringUtils.difference() (http://commons.apache.org/lang/api-release/org/apache/commons/lang/StringUtils.html#difference%28java.lang.String,%20java.lang.String%29)

Alternately, the Eclipse (eclipse.org) project has a diff comparison feature, which means they must also have code to determine the differences, you might browse through their API or source to see what you can find.

Good luck.

回答6:

It seems I will use/port algorithm used here

http://www.google.com/codesearch/p?hl=en&sa=N&cd=6&ct=rc#Jc4aufN53J8/src/main/net/killingar/WordDiff.java&q=worddiff

回答7:

One more library for c# is diff-match-patch - http://code.google.com/p/google-diff-match-patch/.

The bad thing it finds difference in characters. The good thing, there is instruction what you have to add to diff the words.