6

私はここに座って、メイン プログラムのいくつかのアルゴリズムを Java でプログラミングしています (これまでのところ最初のアルゴリズムです)。初心者向けの疑似コードと素敵なチュートリアルを備えた wiki のおかげで、レーベンシュタイン アルゴリズムをうまくプログラムできました :D

次に、Damerau にアップグレードして余分な行を追加することにしましたが、それは DL アルゴではなく OptimalStringAlignmentDistance であると読みました。actionscript コードを読んで、DL にするにはさらに何を追加する必要があるかを理解しようとしましたが、混乱してしまいました。私はJavaに似たコードでさまざまな場所に行ったことがありますが、それらはすべて間違った擬似コードも使用しています。

半日過ごして諦めてこちらにお願いすることにしました。このコードを Java の Damerau-Levenshtein にアップグレードするのを手伝ってくれる人はいますか?

    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));
    //    }
}

ダメラウ・レーベンシュタイン距離アルゴリズムのウィキペディアのページは次のとおりです。

4

2 に答える 2

11

問題は、条件内の文字列から前の文字を参照することです。元のコードには次のものがあります。

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です。これらは、s と t から 1 を引いた i 番目の文字を意味します。アルゴリズムは、(i 番目から 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);
}

編集:残念ながら、コードを読み取ってアルゴリズムを理解していませんが、Java のウィキペディアページから ActionScript の例を翻訳したものを次に示します。これにより、例に一致する出力が得られます。

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;
  }
于 2011-05-17T18:36:48.170 に答える
0

SparseArray は DA に使用できると思います。そうすれば、アルファベットの正確なサイズを知る必要はありません。

SparseArray<Integer> DA = new SparseArray<Integer>();
  ...
    int i1 = DA.get(b.charAt(j - 1), 0);
于 2014-03-21T01:46:23.617 に答える