Created
December 7, 2021 17:55
-
-
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
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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