src/club/wpia/gigi/util/EditDistance.java

   1 package club.wpia.gigi.util;
   2
   3 public class EditDistance {
   4
   5     public static String getBestMatchingStringByEditDistance(String needle, Iterable<String> possibleStrings) {
   6         String best = "";
   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;
  13             }
  14         }
  15         return best;
  16     }
  17
  18     public static String getBestMatchingStringByEditDistance(String needle, String[] possibleStrings) {
  19         if (possibleStrings.length == 0) {
  20             return "";
  21         }
  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;
  29             }
  30         }
  31         return best;
  32     }
  33
  34     /**
  35      * Calculates the levenshtein edit distance between the passed strings.
  36      * Adapted from https://en.wikipedia.org/wiki/Levenshtein_distance
  37      */
  38     public static int calculateLevenshteinDistance(String s, String t) {
  39         // degenerate cases
  40         if (s == t || s.equals(t)) {
  41             return 0;
  42         }
  43         if (s.length() == 0) {
  44             return t.length();
  45         }
  46         if (t.length() == 0) {
  47             return s.length();
  48         }
  49
  50         // create two work arrays of integer distances
  51         int[] previousRow = new int[t.length() + 1];
  52         int[] currentRow = new int[t.length() + 1];
  53
  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++) {
  58             previousRow[i] = i;
  59         }
  60
  61         for (int i = 0; i < s.length(); i++) {
  62             // calculate current row from the previous row
  63
  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;
  67
  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);
  72             }
  73
  74             System.arraycopy(currentRow, 0, previousRow, 0, currentRow.length);
  75         }
  76
  77         return currentRow[t.length()];
  78     }
  79 }