-
Notifications
You must be signed in to change notification settings - Fork 5
/
Levenshtein.java
49 lines (43 loc) · 1.31 KB
/
Levenshtein.java
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
46
47
48
49
package org.genericsystem.reinforcer.tools;
public class Levenshtein {
/**
* Computes the Levenshtein distance between two strings.
*
* @param a - the first string
* @param b - the second string
* @return an {@code int} representing the cost
*/
public static int distance(String a, String b) {
if (null == a || null == b)
throw new IllegalArgumentException("Levenshtein distance requires two not null strings");
if (a.equals(b))
return 0;
if (a.isEmpty())
return b.length();
if (b.isEmpty())
return a.length();
a = a.toLowerCase();
b = b.toLowerCase();
// i == 0
int[] costs = new int[b.length() + 1];
for (int i = 0; i < costs.length; i++)
costs[i] = i;
for (int i = 1; i <= a.length(); i++) {
// j == 0; nw = lev(i - 1, j)
costs[0] = i;
int nw = i - 1;
for (int j = 1; j <= b.length(); j++) {
int cj = Math.min(1 + Math.min(costs[j], costs[j - 1]), a.charAt(i - 1) == b.charAt(j - 1) ? nw : nw + 1);
nw = costs[j];
costs[j] = cj;
}
}
return costs[b.length()];
}
public static double similarity(String string1, String string2) {
return 1 - normedDistance(string1, string2);
}
public static double normedDistance(String string1, String string2) {
return distance(string1, string2) / (double) Math.max(string1.length(), string2.length());
}
}