Similarity String Comparison in Java

user_2309 0
Viewed 139807

I want to compare several strings to each other, and find the ones that are the most similar. I was wondering if there is any library, method or best practice that would return me which strings are more similar to other strings. For example:

  • "The quick fox jumped" -> "The fox jumped"
  • "The quick fox jumped" -> "The fox"

This comparison would return that the first is more similar than the second.

I guess I need some method such as:

double similarityIndex(String s1, String s2)

Is there such a thing somewhere?

EDIT: Why am I doing this? I am writing a script that compares the output of a MS Project file to the output of some legacy system that handles tasks. Because the legacy system has a very limited field width, when the values are added the descriptions are abbreviated. I want some semi-automated way to find which entries from MS Project are similar to the entries on the system so I can get the generated keys. It has drawbacks, as it has to be still manually checked, but it would save a lot of work

string-comparison java
12 Answers

Yes, there are many well documented algorithms like:

  • Cosine similarity
  • Jaccard similarity
  • Dice's coefficient
  • Matching similarity
  • Overlap similarity
  • etc etc

A good summary ("Sam's String Metrics") can be found here (original link dead, so it links to Internet Archive)

Also check these projects:

user_892660
user_1049760
user_601880

This is typically done using an edit distance measure. Searching for "edit distance java" turns up a number of libraries, like this one.

user_908480

Sounds like a plagiarism finder to me if your string turns into a document. Maybe searching with that term will turn up something good.

"Programming Collective Intelligence" has a chapter on determining whether two documents are similar. The code is in Python, but it's clean and easy to port.

user_372130

You can use this "Levenshtein Distance" algorithm without any library:

 public static int getLevenshteinDistance(CharSequence s, CharSequence t) {
    if (s == null || t == null) {throw new IllegalArgumentException("Strings must not be null");}
    int n = s.length();
    int m = t.length();

    if (n == 0) {
            return m;
        }
    else if (m == 0) {
            return n;
        }

    if (n > m) {
            // swap the input strings to consume less memory
            final CharSequence tmp = s;
            s = t;
            t = tmp;
            n = m;
            m = t.length();
        }

    final int[] p = new int[n + 1];
    // indexes into strings s and t
    int i; // iterates through s
    int j; // iterates through t
    int upper_left;
    int upper;

    char t_j; // jth character of t
    int cost;

    for (i = 0; i <= n; i++) {
            p[i] = i;
        }

    for (j = 1; j <= m; j++) {
            upper_left = p[0];
            t_j = t.charAt(j - 1);
            p[0] = j;

            for (i = 1; i <= n; i++) {
                    upper = p[i];
                    cost = s.charAt(i - 1) == t_j ? 0 : 1;
                    // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
                    p[i] = Math.min(Math.min(p[i - 1] + 1, p[i] + 1), upper_left + cost);
                    upper_left = upper;
                }
        }

    return p[n];
   }

From Here

user_115463660
user_135044870
Related