1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| /**
* compute the Levenshtein distance between two strings
* @author Xavier Philippeau
*
* @param s0 String 0
* @param s1 String 1
* @return the Levenshtein distance
*/
public int levenshtein(String s0, String s1) {
int len0 = s0.length()+1;
int len1 = s1.length()+1;
// the array of distances
int[] cost = new int[len0];
int[] newcost = new int[len0];
// initial cost of skipping prefix in String s0
for(int i=0;i<len0;i++) cost[i]=i;
// dynamicaly computing the array of distances
// transformation cost for each letter in s1
for(int j=1;j<len1;j++) {
// initial cost of skipping prefix in String s1
newcost[0]=j-1;
// transformation cost for each letter in s0
for(int i=1;i<len0;i++) {
// matching current letters in both strings
int match = (s0.charAt(i-1)==s1.charAt(j-1))?0:1;
// computing cost for each transformation
int cost_replace = cost[i-1]+match;
int cost_insert = cost[i]+1;
int cost_delete = newcost[i-1]+1;
// keep minimum cost
newcost[i] = min(cost_insert, cost_delete, cost_replace);
}
// swap cost/newcost arrays
int[] swap=cost; cost=newcost; newcost=swap;
}
// the distance is the cost for transforming all letters in both strings
return cost[len0-1];
} |
Partager