[Java] Distance de Levenshtein
Implémentation en Java du calcul de la distance de Levenshtein entre 2 chaines de caractères:
Code:
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];
} |
Je vous laisse implémenter le code de la methode min(). :mrgreen:
