Levenshtein到Damerau-Levenshtein
我坐在这里为Java主程序编程一些算法（到目前为止第一个算法）。 我编写了levenshtein算法就好了，这要归功于wiki对于newbeginners的假代码非常好以及一个很好的教程：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 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)); // } } 这是Damerau-Levenshtein距离算法的维基百科页面
您的问题是引用条件中字符串中的前一个字符。 在原始代码中，您有：
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; }
我认为SparseArray可以用于DA，这样就没有必要知道字母表的确切大小。
SparseArray DA = new SparseArray (); ... int i1 = DA.get(b.charAt(j - 1), 0);