Discussion :

[keumlebarbare]

Bonjour,

Je suis entrain de créer un petit moteur de recherche qui utilise java. Je veux avec java lors de la saisie d'un mot, aller chercher dans une liste si il est présent, et si il ne l'est pas, aller chercher le mot le plus proche.

J'ai donc mis en place l'algorithme de wagner et fisher, qui calcule le cout le plus faible entre deux mots, mais il n'est pas assez restricitifs, et j'aimerais qu'il privilégie des solutions par rapport à d'autres.

Exemple:

je rentre ilste

il me sort en cout identique:

ils
liste
reste
peste


Voici l'algorithme:

Code :

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
	private float testWagnerFisher(String mot1, String mot2) {
		int l1 = mot1.length(); // longueur mot1
		int l2 = mot2.length(); // longueur mot1
		float[][] distance = new float[l1 + 1][l2 + 1]; // Matrice de calcul des couts
		int i, j;
		int cout;
 
		// Initialisation ligne/colonne		
		for (i = 0; i <= l1; i++) {
			distance[i][0] = i;
		}
 
		for (j = 0; j <= l2; j++) {
			distance[0][j] = j;
		}
 
		//on remplit la matrice
		for (i = 1; i <= l1; i++) {
			for (j = 1; j <= l2; j++) {
				if (mot1.charAt(i - 1) == mot2.charAt(j - 1)) {
					//le caractere est identique
					cout = 0;
				} else {
					cout = 1;
				}
				distance[i][j] = Math.min(distance[i - 1][j - 1] + cout, Math
						.min(distance[i - 1][j] + 1, distance[i][j - 1] + 1));
			}
		}
		return distance[l1][l2];
	}

Si vous connaissez un moyen qui ne soit pas trop gourmand en complexité pour privilégier la sortie de liste par rapport à 'ils' et 'reste', je vous en serais très reconnaissant

Si besoin de plus d'explications, je vous les fournirais sans le moindre problème.

[lj617]

Salut,

une heuristique intéressante dans ce cas est de considéré la somme des élément de la matrice et de retenir le mot pour lequel la différence est la plus petite par rapport a la matrice du mot recherché

Par Exemple

D:\java>java WagnerFisher ilste ilste ils ilst ilsti liste peste reste
Distance between : ilste/ilste => 0.0
|0.0|1.0|2.0|3.0|4.0|5.0|
|1.0|0.0|1.0|2.0|3.0|4.0|
|2.0|1.0|0.0|1.0|2.0|3.0|
|3.0|2.0|1.0|0.0|1.0|2.0|
|4.0|3.0|2.0|1.0|0.0|1.0|
|5.0|4.0|3.0|2.0|1.0|0.0|
Sum = 70.0

Distance between : ilste/ils => 2.0
|0.0|1.0|2.0|3.0|
|1.0|0.0|1.0|2.0|
|2.0|1.0|0.0|1.0|
|3.0|2.0|1.0|0.0|
|4.0|3.0|2.0|1.0|
|5.0|4.0|3.0|2.0|
Sum = 44.0

Distance between : ilste/ilst => 1.0
|0.0|1.0|2.0|3.0|4.0|
|1.0|0.0|1.0|2.0|3.0|
|2.0|1.0|0.0|1.0|2.0|
|3.0|2.0|1.0|0.0|1.0|
|4.0|3.0|2.0|1.0|0.0|
|5.0|4.0|3.0|2.0|1.0|
Sum = 55.0

Distance between : ilste/ilsti => 1.0
|0.0|1.0|2.0|3.0|4.0|5.0|
|1.0|0.0|1.0|2.0|3.0|4.0|
|2.0|1.0|0.0|1.0|2.0|3.0|
|3.0|2.0|1.0|0.0|1.0|2.0|
|4.0|3.0|2.0|1.0|0.0|1.0|
|5.0|4.0|3.0|2.0|1.0|1.0|
Sum = 71.0

Distance between : ilste/liste => 2.0
|0.0|1.0|2.0|3.0|4.0|5.0|
|1.0|1.0|1.0|2.0|3.0|4.0|
|2.0|1.0|2.0|2.0|3.0|4.0|
|3.0|2.0|2.0|2.0|3.0|4.0|
|4.0|3.0|3.0|3.0|2.0|3.0|
|5.0|4.0|4.0|4.0|3.0|2.0|
Sum = 97.0

Distance between : ilste/peste => 2.0
|0.0|1.0|2.0|3.0|4.0|5.0|
|1.0|1.0|2.0|3.0|4.0|5.0|
|2.0|2.0|2.0|3.0|4.0|5.0|
|3.0|3.0|3.0|2.0|3.0|4.0|
|4.0|4.0|4.0|3.0|2.0|3.0|
|5.0|5.0|4.0|4.0|3.0|2.0|
Sum = 110.0

Distance between : ilste/reste => 2.0
|0.0|1.0|2.0|3.0|4.0|5.0|
|1.0|1.0|2.0|3.0|4.0|5.0|
|2.0|2.0|2.0|3.0|4.0|5.0|
|3.0|3.0|3.0|2.0|3.0|4.0|
|4.0|4.0|4.0|3.0|2.0|3.0|
|5.0|5.0|4.0|4.0|3.0|2.0|
Sum = 110.0

Le mot 'ilste' a une différence nulle par rapport a lui-même et la somme des éléments de sa matrice est '70'
Dans ce cas on sélectionnera 'ils' si on regarde les valeurs absolues des différences et 'liste' si on ne considère que les mots pour lesquels cette différence est positive ...

A+

[keumlebarbare]

Je ne suis pas sur d'avoir pigé l'astuce

En effet, je comprends l'idée de la somme des algos, mais par exemple, si on a vue et veux, et que l'on tappe vuex, cela ne fonctionnera pas si j'ai bien compris, si?

Merci de ton aide en tout cas !

[foufou67]

c'est interressant de savoir que l'on a un espace topologique gere par une distance definis dans ton algo et comme ensemble des matrices, si on se sert de ton idée pour les images on peut faire un logiciel de type reconnaisance de personne. ;-)

[lj617]

Salut,

Dans l'exemple que tu donnes, le système choisira 'vue' puisque ce mot a une distance inférieure (1.0) a celle de 'veux' (2.0) par rapport a 'vuex'. L'heuristique donnée servait seulement a départager des mots de même distance par rapport au mot cible en se basant sur la distance de Wagner & Fisher.
A l'heure actuelle il existe d'autres méthodes pour calculer la similitude de deux textes (autre que la distance d'édition de Wagner & Fisher) et une des plus intéressante se base sur les algorithmes de compression

A+

[keumlebarbare]

Pour la gestion de ilste et liste, j'ai mis une pondération sur chaque opération.

Code :

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
	private float operation(String x, String y) {
		// Cas d'une suppression
		if(x!=null && y==null) {
			return 1;
		}
		else {
			// Cas d'une insertion
			if(x==null && y!=null) {
				return 1;
			}
			else { 
			// Cas d'une substitution
				if(x.equals(y)){
					return 0;
				}
				else{
					return (float)1.1;
				}
			}
		}
	}

Cela me donne:

Code :

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

1
2
3
4
5
6
7
8
saisie : ilste
j'ai saisi ilste
------------
Mot : ilste
 - peste 2.2
 - reste 2.2
 - liste 2.1
 - ils 2.2

Donc là je suis bon, mais pour le vuex:

Code :

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

1
2
3
4
5
j'ai saisi vuex
------------
Mot : vuex
 - veux 2.2
 - vue 1.1

Donc je vais tenter d'identifier avant le calcul de wagner et fisher si un mot existe dans le lexique avec deux lettres permutées.