6

This question already has an answer here:

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). enter image description here

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. enter image description here

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?

marked as duplicate by user40980, Ixrec, gnat Nov 21 '15 at 16:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    Any chance Levenshtein distance is what you're looking for? – Ixrec Nov 21 '15 at 2:07
  • I'm looking into that right now. It seems promising. Though I'd have to take some more time to see if that is indeed the way to go. – CD VA Programmer Nov 21 '15 at 2:22
  • Many languages have the function built in, or have it available in a common library. For example, PHP has the levenshtein() function which takes two strings and also allows tuning of the cost of each type of manipulation. – techdude Jan 12 '17 at 16:31
2

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.

  • T-SQL (which is for Microsoft SQL Server databases) has the NEAR term which does something like this. I've tried it and the results were unfortunately underwhelming to me based on my expectations of Google-like spelling correction. Here's the link: msdn.microsoft.com/en-us/library/ms142568.aspx – John Doe Nov 21 '15 at 5:05
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.
  • Thank you for your response. I'm looking into the diff and array_intersect() methods now. Both look like great ways to figure this out. However I'd have to look into this some more to see if there's any else I need to take into account when using either of those two methods. And not to pry but if you do remember your solution it would be a great help if you can share. I'll first look into the diff and array_intersect methods and alternative items found on the web. – CD VA Programmer Nov 21 '15 at 2:29
  • The algorithm you describe is not O(log n). It's O(n) just to split the strings into words. It looks to me like your proposed solution is O(n^2). – Jim Mischel Dec 3 '15 at 20:15
  • Thanks, I have a question. If a program does a pass through a data set...completes that first pass...and then does another pass...that's just 2O(n) or effectively O(n), right? – John Doe Dec 4 '15 at 0:43
0

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).

Not the answer you're looking for? Browse other questions tagged or ask your own question.