Skip to content

Instantly share code, notes, and snippets.

@TobiasKrok
Created December 7, 2021 17:55
Show Gist options
  • Save TobiasKrok/f4e607a30e0ff180d53b411ec03469ce to your computer and use it in GitHub Desktop.
Save TobiasKrok/f4e607a30e0ff180d53b411ec03469ce to your computer and use it in GitHub Desktop.
Java Levenshtein implementation that accepts a map of string to compare and calculates deviation
public static Map<String, Double> levenshtein(String value, List<String> otherValues, boolean caseSensitive) {
Map<String, Double> result = new HashMap<>();
char[] sourceArr = value.toCharArray();
int soureArrLength = sourceArr.length;
if(soureArrLength == 0) return result;
for (String otherValue : otherValues) {
char[] targetVal = otherValue.toCharArray();
int targetValLength = targetVal.length;
if (targetValLength == 0) {
result.put(value, 0.0);
continue;
}
int[][] d = new int[soureArrLength + 1][targetValLength + 1];
for (int m = 0; m <= soureArrLength; m++) {
d[m][0] = m;
}
for (int n = 0; n <= targetValLength; n++) {
d[0][n] = n;
}
for (int j = 1; j <= soureArrLength; j++) {
int cost;
for (int k = 1; k <= targetValLength; k++) {
char sourceChar = caseSensitive ? sourceArr[j - 1] : Character.toUpperCase(sourceArr[j - 1]);
char targetChar = caseSensitive ? targetVal[k - 1] : Character.toUpperCase(targetVal[k - 1]);
if ( sourceChar != targetChar ) {
cost = 1;
} else {
cost = 0;
}
d[j][k] = min(d[j - 1][k] + 1, d[j][k - 1] + 1, d[j - 1][k - 1] + cost);
}
}
result.put(otherValue,1d - (double)Math.min(d[soureArrLength][targetValLength], soureArrLength) / (soureArrLength));
}
return result;
}
public static Map<String, Double> levenshtein(String value, List<String> otherValues) {
return levenshtein(value, otherValues, false);
}
public static int min(int a, int b, int c) {
int mi;
mi = a;
if (b < mi) {
mi = b;
}
if (c < mi) {
mi = c;
}
return mi;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment