public static double levensteinDistance()

in opennlp-similarity/src/main/java/opennlp/tools/similarity/apps/utils/LevensteinDistanceFinder.java [46:108]

• 62 lines of code
• 14 McCabe index (conditional complexity)

  public static double levensteinDistance(String str1, String str2,
      int letterInsDelCost, int digitInsDelCost, int letterReplaceCost,
      int digitReplaceCost) {
    int length1 = str1.length() + 1;
    int length2 = str2.length() + 1;
    int[] upper = new int[length2];
    int[] left = new int[length1];
    upper[0] = 0;
    left[0] = 0;
    for (int i = 1; i < length1; i++) {
      int cost = letterInsDelCost; // 1 is a cost for deleting a character
      if (Character.isDigit(str1.charAt(i - 1))) {
        cost = digitInsDelCost;
      }
      left[i] = left[i - 1] + cost;
    }
    for (int j = 1; j < length2; j++) {
      int cost = letterInsDelCost; // 1 is a cost for inserting a character
      if (Character.isDigit(str2.charAt(j - 1))) {
        cost = digitInsDelCost;
      }
      upper[j] = upper[j - 1] + cost;
      int min;
      for (int i = 1; i < length1; i++) {
        cost = letterInsDelCost; // 1 is a cost for inserting a character
        if (Character.isDigit(str1.charAt(i - 1))) {
          cost = digitInsDelCost;
        }
        int fromLeft = left[i] + cost;
        cost = letterInsDelCost; // 1 is a cost for deleting a character
        if (Character.isDigit(str2.charAt(j - 1))) {
          cost = digitInsDelCost;
        }
        int fromUp = upper[j] + cost;
        int delta = 0;
        if (str1.charAt(i - 1) != str2.charAt(j - 1)) {
          // 1 is a cost for replacing a character
          delta = letterReplaceCost;
          if (Character.isDigit(str1.charAt(i - 1))
              || Character.isDigit(str2.charAt(j - 1))) {
            delta = digitReplaceCost;
          }
        }
        int cross = left[i - 1] + delta;
        if (fromLeft < fromUp) {
          if (fromLeft < cross) {
            min = fromLeft;
          } else {
            min = cross;
          }
        } else {
          if (fromUp < cross) {
            min = fromUp;
          } else {
            min = cross;
          }
        }
        left[i - 1] = upper[j];
        upper[j] = min;
      }
    }
    return upper[length2 - 1];
  }