Comparing two large strings to see how much they match [duplicate]

Question

Is there an easy way of comparing any two different size of string text to see how much percentage they're alike?

I'm trying this but I'm running into to this issue below. The left text area is the text to copy. The right is the user trying to copy the text ( in this example the user didn't get everything typed correctly, there's misspelled words and some words that the user forgot to type in).

After a countdown expires I try to calculate the percentage of how much the user correctly copied the given text in the left. And below on the left I have the text of the upper left text box put into an array using the split(" ") command on the text field. And the bottom right I do the same for the user entered text.

Before calculating how much percentage the user typed correctly I try to have a summation of how much words the user typed correctly as my code below shows:

for(var counter = 0; counter < userArr.length; counter++)
{
    if(userArr[counter] === textArr[counter])
    {
        correct++;
    }
}

At index 3 in the array the user mistyped something which is ok. But at index 6 the user completely missed typing a word. So that throws the rest of the indexes off by at least one to get the amount of words typed correctly. Without that I can't calculate the percentage typed correctly.

To me it seems I'd have to create a bunch of conditional checks within the for loop to account for that. But seems to be a bit messy.

So back to my original question, is there an easy way to so this calculations without creating a big mess of if statements? i.e. Is there an open source method, or built in javascript method to handle this?

Answer 1

I believe you are looking for Edit Distance it provides a numerical way to analyze the closeness of two words, which of course can be extrapolated onto full sentences.

Answer 2

If you're not using an existing library function (like the Linux command-line utility diff, the T-SQL word NEAR, or even the PHP function array_intersect()), you can develop your own algorithm for this...and there are many variations possible...although some can be complex. Here's a rough draft of one solution I came up with. It has a time complexity of O(log(n)) (which means a decreasing amount of looping within a loop, which isn't particularly fast).

1. Break the words in the strings into array elements based on whitespace and other punctuation, as the author above did.
2. Begin iterating the 1st array.
3. Compare its 1st element to the 1st element of the 2nd array.
4. If the elements match, bump up your pointers (2nd to 2nd, etc.) and continue to do this as long as you find consecutive matches.
5. When you reach a mismatch, store the starting and ending points of the series of consecutive matches (which we'll call a "common section") in a separate array. For example, array elements 4 through 12 in the 1st array might match elements 7 through 15 in the 2nd array.
6. At that first instance of a mismatch, reset your pointers and go back to iterating the arrays at points that haven't yet been included in a "common section"...and skip over ones that are already marked as "covered" (either flagged in a sub-element or covered by a range of one of the existing "common sections").
7. Once you're done iterating the arrays, "untangle" any out-of-order "common sections" by favoring the longest ones and/or ones that result in the greatest coverage area.
8. Count up your elements matched versus unmatched by your final set of "common sections" and calculate a percentage covered.

Answer 3

You are looking for one of the various forms of edit distance. The formal definition of the edit distance is:

Given two strings a and b on an alphabet Σ (e.g. the set of ASCII characters, the set of bytes [0..255], C T A G, etc.), the edit distance d(a, b) is the minimum-weight series of edit operations that transforms a into b.

From this, you don't have 26 or 28 strings, you have one string. Its a big one - but you look at it in its entirety.

There are many types of edit distance that are focused on different transformations and alphabets. For example, the Levenshtein distance works on the transformations of insert, delete, and substitute on an arbitrary string, where as the Hamming distance is the number of locations where two strings differ. The Damerau–Levenshtein distance adds the transposition of two adjacent characters to the Levenshtein distance (so it that hte to the is a distance of 1, not 2) and is more useful for spell checking and DNA variation (though the Needleman–Wunsch algorithm may work better for strings of DNA).