How to compare almost similar Strings in Java? (String distance measure)

Question

I would like to compare two strings and get some score how much these look alike. For example "The sentence is almost similar" and "The sentence is similar".

I'm not familiar with existing methods in Java, but for PHP I know the levenshtein function.

Are there better methods in Java?

What do you mean by "similar"? Pronounced similar? Is visually similar? — Viktor Klang, Jan 18 '10 at 08:44
@Astor, judging from the example I'd say that neither visual nor pronunciation similarity are the wanted measure here. — Joey, Jan 18 '10 at 08:59
This is a good example of a "good question", but folks who desire to close all kind of questions on stackoverflow ... the question is clear. Why then close it? — Brain, Jun 27 '20 at 09:19

Philipp · Answer 1 · 2016-03-30T12:28:52.223

59

The following Java libraries offer multiple compare algorithms (Levenshtein,Jaro Winkler,...):

Apache Commons Lang 3: https://commons.apache.org/proper/commons-lang/
Simmetrics: http://sourceforge.net/projects/simmetrics/

Both libraries have a java documentation (Apache Commons Lang Javadoc,Simmetrics Javadoc).

//Usage of Apache Commons Lang 3
import org.apache.commons.lang3.StringUtils;   
public double compareStrings(String stringA, String stringB) {
    return StringUtils.getJaroWinklerDistance(stringA, stringB);
}

 //Usage of Simmetrics
import uk.ac.shef.wit.simmetrics.similaritymetrics.JaroWinkler    
public double compareStrings(String stringA, String stringB) {
    JaroWinkler algorithm = new JaroWinkler();
    return algorithm.getSimilarity(stringA, stringB);
}

edited Mar 30 '16 at 12:28

answered Oct 07 '11 at 10:12

Philipp

4,645
3
47
80

1

super lib, easy to use and good results – bluevoid Mar 28 '14 at 09:27
3

Its available in Apache commons-lang now: http://commons.apache.org/proper/commons-lang/apidocs/org/apache/commons/lang3/StringUtils.html#getJaroWinklerDistance%28java.lang.CharSequence,%20java.lang.CharSequence%29 – Ian Jones Jul 07 '14 at 10:20
1

A library based on this is now on GitHub https://github.com/Simmetrics/simmetrics. It is also available on Maven Central – peater Jun 24 '15 at 17:54

score 21 · Accepted Answer · edited Nov 26 '14 at 07:28

21

The Levensthein distance is a measure for how similar strings are. Or, more precisely, how many alterations have to be made that they are the same.

The algorithm is available in pseudo-code on Wikipedia. Converting that to Java shouldn't be much of a problem, but it's not built-in into the base class library.

Wikipedia has some more algorithms that measure similarity of strings.

edited Nov 26 '14 at 07:28

Philipp

4,645
3
47
80

answered Jan 18 '10 at 08:44

Joey

344,408
85
689
683

score 16 · Answer 3 · answered Jan 18 '10 at 08:43

16

yeah thats a good metric, you could use StringUtil.getLevenshteinDistance() from apache commons

answered Jan 18 '10 at 08:43

jspcal

50,847
7
72
76

It is not available in Java Mobile Edition, is it? But thanks for your response! – hsmit Jan 18 '10 at 08:46
you can use it with ME, just add the jar. – jspcal Jan 18 '10 at 08:52
1

hmmm, no, I'm not really so sure it's completely usable with J2ME, it has been compiled with a J2SE – Valentin Rocher Jan 18 '10 at 09:06
1

it doesn't use anything ME doesn't support. you can make and copy in the jar – jspcal Jan 19 '10 at 10:14

score 3 · Answer 4 · answered Nov 20 '15 at 11:24

You can find implementations of Levenshtein and other string similarity/distance measures on https://github.com/tdebatty/java-string-similarity

If your project uses maven, installation is as simple as

<dependency>
  <groupId>info.debatty</groupId>
  <artifactId>java-string-similarity</artifactId>
  <version>RELEASE</version>
</dependency>

Then, to use Levenshtein for example

import info.debatty.java.stringsimilarity.*;

public class MyApp {

  public static void main (String[] args) {
    Levenshtein l = new Levenshtein();

    System.out.println(l.distance("My string", "My $tring"));
    System.out.println(l.distance("My string", "My $tring"));
    System.out.println(l.distance("My string", "My $tring"));
  }
}

score 2 · Answer 5 · answered Dec 03 '18 at 00:34

Shameless plug, but I wrote a library also:

https://github.com/vickumar1981/stringdistance

It has all these functions, plus a few for phonetic similarity (if one word "sounds like" another word - returns either true or false unlike the other fuzzy similarities which are numbers between 0-1).

Also includes dna sequencing algorithms like Smith-Waterman and Needleman-Wunsch which are generalized versions of Levenshtein.

I plan, in the near future, on making this work with any array and not just strings (an array of characters).

How to compare almost similar Strings in Java? (String distance measure)

5 Answers5

Linked