Levenshtein - Damerau-Levenshtein

Question

Burada oturuyorum ve Java'daki ana programım için bazı algoritmaları programlıyorum (şimdiye kadar ilk kez). Ben yeni bir programlama için pseudocode ile çok güzel olan wiki sayesinde levenshtein algoritmasını sadece iyi programladım, artı güzel bir öğretici: D

Daha sonra Damerau'ya geçmeye karar verdim ve ekstra satırları ekledim ama sonra DL algo olmadığını okudum ama OptimalStringAlignmentDistance yerine. Bunu DL'e eklemek için ne kadar eklemem gerektiğini anlamak için actionscript kodunu okumaya çalıştım ama bunun yerine kafam karıştı. Java'ya benzeyen kodları olan farklı yerlere gittim ama hepsi de yanlış sözde kodu kullanıyor.

Yarısından sonra harcadıktan sonra pes ettim ve burada sormaya karar verdim. Bu kodu Java'da Damerau-Levenshtein'a yükseltme konusunda bana yardımcı olabilecek biri var mı?

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

İşte sorun koşullu içinde dizesinden önceki karakterleri referans olduğunu Damerau–Levenshtein distance algorithm

Answer 1

için Vikipedi sayfası. Orijinal kodunda sahip:

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

sorun değerleri t_j-1 ve s_i-1olduğunu. Bunlar s ve t eksi 1'in karakterini söyler, burada algoritma (ith eksi 1) karakterlerini istediğinizi söyler. Örneğin dize s "AFW" ve ben bu yüzden senin okumalısınız koşullu sonra

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

1 ise:

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

DÜZENLEME: Unforutnately Ben kodu okumasını algoritmayı anlamıyorum, ancak

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

bir SparseArray düşünüyorum: burada örnek eşleşen bir çıkış verir Java, içinde wikipedia sayfasından ActionScript örnek bir çevirisidir DA için kullanılabilir, bu şekilde alfabenin tam boyutunu bilmek gerekli değildir.

SparseArray<Integer> DA = new SparseArray<Integer>(); 
    ... 
    int i1 = DA.get(b.charAt(j - 1), 0);