Левенштейн Дамерау-Левенштейн

Question

Я сижу здесь и программирую некоторые алгоритмы для моей основной программы на Java (ну, пока первый).Я запрограммировал алгоритм Левенштейна очень хорошо благодаря тому, что вики был так хорош с псевдокодом для новичков плюс хороший учебник: D

Затем я решил перейти на Damerau и добавил дополнительные строки, но потом прочитал, что это не DLalgo, но OptimalStringAlignmentDistance вместо этого.Я попытался прочитать код ActionScript, чтобы понять, что еще мне нужно было добавить, чтобы сделать это для DL, но вместо этого запутался.Я был в разных местах с кодом, похожим на Java, но все они тоже используют неправильный псевдокод.

Потратив полдня, я сдался и решил спросить здесь.Есть ли кто-нибудь, кто может помочь мне с обновлением этого кода до Дамерау-Левенштейна в Java?

    public class LevensteinDistance {
        private static int Minimum(int a, int b, int c) {
            return Math.min(Math.min(a, b), c);
        }

        private static int Minimum (int a, int b) {
            return Math.min(a, b);
        }

        public static int computeLevensteinDistance(String s, String t){
            int d[][];
            int n; // length of s
            int m; // length of t
            int i; // iterates through s
            int j; // iterates through t
            char s_i; // ith character of s
            char t_j; // jth character of t
            int cost; // cost

            n = s.length ();
            m = t.length ();
            if (n == 0) {
                return m;
            }
            if (m == 0) {
                return n;
            }
            d = new int[n+1][m+1];

            for (i = 0; i <= n; i++) {
                d[i][0] = i;
            }

            for (j = 0; j <= m; j++) {
                d[0][j] = j;
            }

            for(i = 1; i <= n; i++) {
                s_i = s.charAt (i - 1);
                for(j = 1; j <= m; j++) {
                    t_j = t.charAt (j - 1);

                    if(s_i == t_j){
                        cost = 0;
                    }else{
                        cost = 1;
                    }
                    d[i][j] = Minimum(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);

                    if(i > 1 && j > 1 && s_i == t_j-1 && s_i-1 == t_j){ 
                        d[i][j] = Minimum(d[i][j], d[i-2][j-2] + cost);
                    }
                }
            }
        return d[n][m];
    }

    //    public static void main(String[] args0){
    //      String a = "I decided it was best to ask the forum if I was doing it right";
    //      String b = "I thought I should ask the forum if I was doing it right";
    //      System.out.println(computeLevensteinDistance(a, b));
    //    }
}

Вот страница Википедии для алгоритма расстояния Дамерау – Левенштейна

Answer 1

Ваша проблема заключается в ссылке на предыдущие символы из строки в вашем условном выражении. В исходном коде у вас есть:

if(i > 1 && j > 1 && s_i == t_j-1 && s_i-1 == t_j){ 
  d[i][j] = Minimum(d[i][j], d[i-2][j-2] + cost);
}

Проблема в значениях t_j-1 и s_i-1 . Они говорят, что i-й символ s и t минус 1, где алгоритм говорит, что вы хотите (ih минус 1) символов. Например, если строка s равна «AFW», а i равно 1, тогда

s_i - 1 = E; //the character value (s[1]='F') minus 1 = 'E'
s.charAt(i-1) = A; //i-1 = 0, s[0] = 'A'

поэтому ваше условное выражение должно выглядеть так:

if(i > 1 && j > 1 && s_i == t.charAt(j-1) && s.charAt(i-1) == t_j) { 
  d[i][j] = Minimum(d[i][j], d[i-2][j-2] + cost);
}

EDIT: К сожалению, я не понимаю алгоритм чтения кода, однако здесь приведен перевод примера ActionScript со страницы википедии на Java, который дает вывод, соответствующий вашему примеру:

public static int damerauLevenshteinDistance(
      String a, String b, int alphabetLength) {
    final int INFINITY = a.length() + b.length();
    int[][] H = new int[a.length()+2][b.length()+2];  
    H[0][0] = INFINITY;
    for(int i = 0; i<=a.length(); i++) {
      H[i+1][1] = i;
      H[i+1][0] = INFINITY;
    }
    for(int j = 0; j<=b.length(); j++) {
      H[1][j+1] = j;
      H[0][j+1] = INFINITY;
    }      
    int[] DA = new int[alphabetLength];
    Arrays.fill(DA, 0);
    for(int i = 1; i<=a.length(); i++) {
      int DB = 0;
      for(int j = 1; j<=b.length(); j++) {
        int i1 = DA[b.charAt(j-1)];
        int j1 = DB;
        int d = ((a.charAt(i-1)==b.charAt(j-1))?0:1);
        if(d==0) DB = j;
        H[i+1][j+1] =
          min(H[i][j]+d,
              H[i+1][j] + 1,
              H[i][j+1]+1, 
              H[i1][j1] + (i-i1-1) + 1 + (j-j1-1));
      }
      DA[a.charAt(i-1)] = i;
    }
    return H[a.length()+1][b.length()+1];
  }

  private static int min(int ... nums) {
    int min = Integer.MAX_VALUE;
    for (int num : nums) {
      min = Math.min(min, num);
    }
    return min;
  }

Answer 2

Я думаю, что SparseArray можно использовать для DA, поэтому нет необходимости точно знать размер алфавита.