Levenshtein a Damerau-Levenshtein
Estoy sentado aquí y estoy programando algunos algoritmos para mi programa principal en Java (bueno, el primero hasta ahora). Programé el algoritmo levenshtein muy bien gracias a que wiki es tan bueno con el pseudocódigo para los principiantes más un buen tutorial: D
Luego decidí actualizar a Damerau y agregué las líneas adicionales, pero luego leí que no es DL algo, sino OptimalStringAlignmentDistance. Intenté leer el código de ActionScript para comprender qué más necesitaba agregar para llegar a DL, pero me confundí en su lugar. He estado en diferentes lugares con código que se parece a Java, pero todos usan el pseudocódigo incorrecto también.
Después de pasar la mitad del día, me di por vencido y decidí preguntar aquí. ¿Hay alguien que pueda ayudarme con la actualización de este código a Damerau-Levenshtein en 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));
// }
}
Aquí está la página de Wikipedia para el Damerau – Levenshtein algoritmo de distancia