Algorithme de test d'erreur de frappe
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:
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.
