2

I'm looking for a way to do programmatically detect the delta ratio between two strings. I can use string length, but this doesn't give much useful information for like-sized but different inputs. There is a java diff tool on google code Java Diff Utils, but it hasn't been updated since 2011 and I don't need to actually modify the Strings themselves.

I'm attempting to do change detection with threshold values, for instance: Updated string is 42% different than existing string, are you sure you want to proceed?

Does anyone know of a library that could be used for this, or is java-diff-utils my only option? I couldn't find much in apache commons, and googling is returning irrelevant information.

Quad64Bit
  • 568
  • 7
  • 16
  • 5
    Sounds like you want "Levenshtein distance". – cHao Aug 08 '13 at 12:51
  • Actually this is closer to what you want: http://stackoverflow.com/questions/2325588/text-similarity-algorithm – assylias Aug 08 '13 at 12:52
  • 1
    You can use Apache Common for Levenshtein distance calculation: http://commons.apache.org/proper/commons-lang/javadocs/api-3.1/org/apache/commons/lang3/StringUtils.html#getLevenshteinDistance%28java.lang.CharSequence,%20java.lang.CharSequence,%20int%29 – kaos Aug 08 '13 at 12:56
  • 1
    Here is another discussion on SO:http://stackoverflow.com/questions/1997750/cosine-similarity. This one was found to be helpful for another with similar question. – Jeremy Johnson Aug 08 '13 at 12:57
  • Perfect, your answers were very helpful! – Quad64Bit Aug 19 '13 at 18:34

1 Answers1

3

You could use the Levenshtein Distance to calculate how much different two strings are amongst themselves. There's some quite complex math there but the actual code is rather short. You can easily rewrite the code in that wiki in Java.

The difference will be measured in integers, saying how many steps you'd take to turn one string into the other. A step may be a character addition, removal, or replacement with another character. It will tell you the amount of steps it takes, but not which steps, nor in which order. But then again, since you only want to measure the total difference, I'm sure that's enough information for your needs.

edit: one of the commenters (kaos) provided a link to an implementation of Levenshtein Distance in the Apache Commons.

Geeky Guy
  • 9,229
  • 4
  • 42
  • 62