Word by word comparison of two strings

Question

Hello,

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

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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