Calculate String Similarity in Java
This post will calculate the similarity between two Strings in Java.
There are several good algorithms like Levenshtein distance and Jaro-Winkler distance which can be used to calculate the similarity between two strings. We can implement these algorithms ourselves, or use the implementation offered by third-party libraries.
1. Custom Implementation
The Levenshtein distance (or Edit distance) algorithm tells how different two strings are from one another by counting the minimum number of operations required to transform one string to another.
We can use Levenshtein distance to determine the similarity between two strings. The following code implements Levenshtein distance and uses it to calculate the similarity between two strings in the range [0, 1]. The code can be easily modified to calculate similarity in percentage.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
public class Main { public static int getLevenshteinDistance(String X, String Y) { int m = X.length(); int n = Y.length(); int[][] T = new int[m + 1][n + 1]; for (int i = 1; i <= m; i++) { T[i][0] = i; } for (int j = 1; j <= n; j++) { T[0][j] = j; } int cost; for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { cost = X.charAt(i - 1) == Y.charAt(j - 1) ? 0: 1; T[i][j] = Integer.min(Integer.min(T[i - 1][j] + 1, T[i][j - 1] + 1), T[i - 1][j - 1] + cost); } } return T[m][n]; } public static double findSimilarity(String x, String y) { if (x == null || y == null) { throw new IllegalArgumentException("Strings must not be null"); } double maxLength = Double.max(x.length(), y.length()); if (maxLength > 0) { // optionally ignore case if needed return (maxLength - getLevenshteinDistance(x, y)) / maxLength; } return 1.0; } public static void main(String[] args) { double similarity = findSimilarity("Techie Delight", "Tech Delight"); System.out.println(similarity); // 0.8571428571428571 } } |
2. Using Apache Commons Library
Apache Commons Lang StringUtils utility class provides various algorithms to calculate the similarity between two strings.
1. StringUtils.getLevenshteinDistance() method
To find the Levenshtein distance between two strings, we can use the StringUtils.getLevenshteinDistance() method which returns the minimum number of operations required to transform one string to another.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import org.apache.commons.lang3.StringUtils; public class Main { public static double findSimilarity(String x, String y) { double maxLength = Double.max(x.length(), y.length()); if (maxLength > 0) { // optionally ignore case if needed return (maxLength - StringUtils.getLevenshteinDistance(x, y)) / maxLength; } return 1.0; } public static void main(String[] args) { double similarity = findSimilarity("Techie Delight", "Tech Delight"); System.out.println(similarity); // 0.8571428571428571 } } |
2. StringUtils.getJaroWinklerDistance() method
To calculate the Jaro-Winkler distance between two strings, we can use the StringUtils.getJaroWinklerDistance() method. The Jaro measure is the weighted sum of the percentage of matched characters from each file and transposed characters. Winkler increased this measure for matching initial characters.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import org.apache.commons.lang3.StringUtils; public class Main { public static double findSimilarity(String x, String y) { if (x == null && y == null) { return 1.0; } if (x == null || y == null) { return 0.0; } return StringUtils.getJaroWinklerDistance(x, y); } public static void main(String[] args) { double similarity = findSimilarity("Techie Delight", "Tech Delight"); System.out.println(similarity); // 0.93 } } |
That’s all about calculating similarity between two Strings in Java.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)