Discussion :

[pseudocode]

Implémentation en Java du calcul de la distance de Levenshtein entre 2 chaines de caractères:

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

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().

[souki22]

Bonjour,

Et si on veut afficher à chaque étape le mot s1 après lui avoir effectué une opération jusqu'à ce qu'il vaille le mot s2 ?

Bien cordialement.

[ToTo13]

Que veux tu faire exactement ?
Tester si s1 et s2 sont égaux, si ce n'est pas le cas alors le modifier puis l'afficher.
Puis itérer jusqu'à ce que s1 = s2 ?