1 package club.wpia.gigi.util;
3 public class EditDistance {
5 public static String getBestMatchingStringByEditDistance(String needle, Iterable<String> possibleStrings) {
7 int bestDistance = Integer.MAX_VALUE;
8 for (String possibleString : possibleStrings) {
9 int newDistance = calculateLevenshteinDistance(possibleString, needle);
10 if (newDistance < bestDistance) {
11 bestDistance = newDistance;
12 best = possibleString;
18 public static String getBestMatchingStringByEditDistance(String needle, String[] possibleStrings) {
19 if (possibleStrings.length == 0) {
22 String best = possibleStrings[0];
23 int bestDistance = Integer.MAX_VALUE;
24 for (String possibleString : possibleStrings) {
25 int newDistance = calculateLevenshteinDistance(possibleString, needle);
26 if (newDistance < bestDistance) {
27 bestDistance = newDistance;
28 best = possibleString;
35 * Calculates the levenshtein edit distance between the passed strings.
36 * Adapted from https://en.wikipedia.org/wiki/Levenshtein_distance
38 public static int calculateLevenshteinDistance(String s, String t) {
40 if (s == t || s.equals(t)) {
43 if (s.length() == 0) {
46 if (t.length() == 0) {
50 // create two work arrays of integer distances
51 int[] previousRow = new int[t.length() + 1];
52 int[] currentRow = new int[t.length() + 1];
54 // initialize previousRow
55 // this row is A[0][i]: edit distance for an empty s
56 // the distance is just the number of characters to delete from t
57 for (int i = 0; i < previousRow.length; i++) {
61 for (int i = 0; i < s.length(); i++) {
62 // calculate current row from the previous row
64 // first element of currentRow is A[i+1][0]
65 // edit distance is delete (i+1) chars from s to match empty t
66 currentRow[0] = i + 1;
68 // use formula to fill in the rest of the row
69 for (int j = 0; j < t.length(); j++) {
70 int cost = s.charAt(i) == t.charAt(j) ? 0 : 1;
71 currentRow[j + 1] = Math.min(Math.min(currentRow[j] + 1, previousRow[j + 1] + 1), previousRow[j] + cost);
74 System.arraycopy(currentRow, 0, previousRow, 0, currentRow.length);
77 return currentRow[t.length()];