|
 Trouver une ressource
Vous ne trouvez pas de réponse à votre problème ? Alors posez la question dans le forum. Souvenez-vous qu'il n'y a jamais de question bête, mais rester dans l'ignorance parce que l'on n'ose pas poser une question, ça c'est une erreur !
 APPLICATION DE L'ALGO DE WAGNER ET FISHER
 Information sur la source
 Description
L'algorithme de Wagner et Fisher permet de déterminer la proximité syntaxique entre deux mots. Ainsi, si vous recherchez le mot "trucage" dans une bdd ou un tableau, l'algo définit quel(s) mot(s) est (sont) le plus proche syntaxiquement du mot recherché (parmi les solutions possibles). En l'occurence, si nous avons comme données "chat", "tricherie", "bidule", l'algo définira "tricherie" comme le mot le plus proche. La méthode prend un tableau de Strings, et le mot à comparé en entrée, et renvoie une arrayList triée par ordre alphabétique. J'ai rajouté une amélioration non présente dans l'algo de base. A voir si cela améliore réellement : je classe le tableau de Strings par ordre croissant de taille des Strings. Et lors de l'évaluation de la "distance / longueur" entre un mot de la table et le mot à comparé, j'incrémente de 1 à n (donc, selon la taille du String) : Si la chaîne est la plus petite du tableau, la "distance" est incrémentée de n (avec n = tab.count), si elle est la plus grande elle est incrémentée de 1. Cela a amélioré nettement les résultats lors de mes tests. A vous de voir si cela vous est utile. Voilou.
 Source
- private ArrayList WagnerAndFisher(ref String[] tabMots, String mot)
- {
- int tailleTab = tabMots.Length;
- int longMot = mot.Length;
- int[] longueur = new int[tailleTab];
- String temp;
- Boolean modif = false;
- do
- {
- modif = false;
- for (int i = 1; i < tabMots.Length; i++)
- {
- if (tabMots[i].Length > tabMots[i - 1].Length)
- {
- modif = true;
- temp = tabMots[i];
- tabMots[i] = tabMots[i - 1];
- tabMots[i - 1] = temp;
- }
- }
- }while (modif);
-
- for (int cptMots = 0; cptMots < tailleTab; cptMots++)
- {
- int longMotTest = tabMots[cptMots].Length;
- char[] tab_char = new char[longMotTest];
- tab_char = tabMots[cptMots].ToUpper().ToCharArray();
- int[,] matrice = new int[longMotTest, longMot];
- matrice[0, 0] = 0;
- int m1;
- int m2;
- int m3;
- for (int i = 1; i < longMotTest; i++)
- {
- matrice[i, 0] = matrice[i - 1, 0] + 1;
- }
- for (int j = 1; j < longMot; j++)
- {
- matrice[0, j] = matrice[0, j - 1] + 1;
- }
- for (int i = 1; i < longMotTest; i++)
- {
- for (int j = 1; j < longMot; j++)
- {
- if (tab_char[i] == mot[j])
- {
- m1 = matrice[i - 1, j - 1];
- }
- else
- {
- m1 = matrice[i - 1, j - 1] + 1;
- }
- m2 = matrice[i - 1, j] + 1;
- m3 = matrice[i, j - 1] + 1;
- if ((m1 <= m2) && (m1 <= m3))
- {
- matrice[i, j] = m1;
- }
- else if ((m2 <= m1) && (m2 <= m3))
- {
- matrice[i, j] = m2;
- }
- else if ((m3 <= m2) && (m3 <= m1))
- {
- matrice[i, j] = m3;
- }
- }
- }
- longueur[cptMots] = matrice[longMotTest - 1, longMot - 1] + cptMots;
- }
- int min = longueur[0];
- String[] resultat = new String[tailleTab];
- int cpt = 0;
- for (int i = 0; i < tailleTab; i++)
- {
- if (min > longueur[i])
- {
- min = longueur[i];
- resultat[0] = tabMots[i];
- cpt = 1;
- }
- else if (min == longueur[i])
- {
- resultat[cpt] = tabMots[i];
- cpt = cpt + 1;
- }
-
- }
- ArrayList listeRetour = new ArrayList();
- for (int i = 0; i < resultat.Length; i++)
- {
- listeRetour.Add(resultat[i]);
- }
-
- listeRetour.Sort();
- return listeRetour;
- }
private ArrayList WagnerAndFisher(ref String[] tabMots, String mot)
{
int tailleTab = tabMots.Length;
int longMot = mot.Length;
int[] longueur = new int[tailleTab];
String temp;
Boolean modif = false;
do
{
modif = false;
for (int i = 1; i < tabMots.Length; i++)
{
if (tabMots[i].Length > tabMots[i - 1].Length)
{
modif = true;
temp = tabMots[i];
tabMots[i] = tabMots[i - 1];
tabMots[i - 1] = temp;
}
}
}while (modif);
for (int cptMots = 0; cptMots < tailleTab; cptMots++)
{
int longMotTest = tabMots[cptMots].Length;
char[] tab_char = new char[longMotTest];
tab_char = tabMots[cptMots].ToUpper().ToCharArray();
int[,] matrice = new int[longMotTest, longMot];
matrice[0, 0] = 0;
int m1;
int m2;
int m3;
for (int i = 1; i < longMotTest; i++)
{
matrice[i, 0] = matrice[i - 1, 0] + 1;
}
for (int j = 1; j < longMot; j++)
{
matrice[0, j] = matrice[0, j - 1] + 1;
}
for (int i = 1; i < longMotTest; i++)
{
for (int j = 1; j < longMot; j++)
{
if (tab_char[i] == mot[j])
{
m1 = matrice[i - 1, j - 1];
}
else
{
m1 = matrice[i - 1, j - 1] + 1;
}
m2 = matrice[i - 1, j] + 1;
m3 = matrice[i, j - 1] + 1;
if ((m1 <= m2) && (m1 <= m3))
{
matrice[i, j] = m1;
}
else if ((m2 <= m1) && (m2 <= m3))
{
matrice[i, j] = m2;
}
else if ((m3 <= m2) && (m3 <= m1))
{
matrice[i, j] = m3;
}
}
}
longueur[cptMots] = matrice[longMotTest - 1, longMot - 1] + cptMots;
}
int min = longueur[0];
String[] resultat = new String[tailleTab];
int cpt = 0;
for (int i = 0; i < tailleTab; i++)
{
if (min > longueur[i])
{
min = longueur[i];
resultat[0] = tabMots[i];
cpt = 1;
}
else if (min == longueur[i])
{
resultat[cpt] = tabMots[i];
cpt = cpt + 1;
}
}
ArrayList listeRetour = new ArrayList();
for (int i = 0; i < resultat.Length; i++)
{
listeRetour.Add(resultat[i]);
}
listeRetour.Sort();
return listeRetour;
}
 Conclusion
C'est un algo très connu mais il peut être utile aux développeurs qui souhaitent incorporer cette fonctionnalité.
 Historique
- 08 avril 2008 18:52:51 :
- nettoyage du code, amélioration fonctionnelle.
 Sources de la même categorie
Sources en rapport avec celle ci
 Commentaires et avis
 Discussions en rapport avec ce code source dans le forum
recherche algo de trie alphabetique en C [ par mikolemarseillais ]
salut à tousje souhaite créer une fonction en C qui pourra trier les donnés d'un fichier(par ex: trier par nom) par ordre alphabetique.Merci de m'aide
Recherche de Caractère dans une chaîne [ par DrChal ]
DrChalSalut ,Je cherche le moyen de rechercher un mot dans une chaîne de caractère.En VB, on avait la fonction InStr, existe t-elle en C#?Pouvez vous
Recherche du nom d'utilisateur dans l'entête HTTP [ par projetbts ]
Bonjour,Je tente de récupérer le nom d'utilisateur qui tente une connection sur mon serveur HTTP. Pour cela, je récupére les entêtes HTTP fourni dans
Recherche dans une chaine de caractères [ par jdaviaud ]
j'ai encore une fois besoin de vos lumières :(j'ai stocké du code html dans une variable string et je veux en extraire tous les contenus des tags img
Je comprends pas cette algorithme [ par kaiwoo ]
private bool AUneVirgule (double nb){long tmp = (long)nb;if (tmp == nb)return false;elsereturn true;}Pour info, il a été fait par un super membre du f
Débutant recherche des explications sur C# [ par mikaelkeal ]
Salut tt le monde,Je suis un développeur ASP, en mon patron veut que je développe une application en C# sur des pokets PC.Et je n'y connais rien (je l
Recherche aide ou code pour gestion d'un Treeview [ par shadowgirl ]
Salut à tous, Je cherche quelqu'un qui pourrait m'aider ou me passer du code pour gérer un Treeview, avec la classe Treeview. (Expand, selected ....)
Dans un dataSet j'aimerais faire une recherche [ par oboudou ]
Dans un dataSet j'aimerais faire une recherche. Mais mon probléme est que j'importe mes données de xml. Donc je n'ai pas de clée primaire défini (en f
REcherche d'un dossier [ par caj ]
Bonjour tout le monde,Je suis à la recherche d'une methode en c# pour pouvoir trouver le chemin d'accés pour un repertoire en particulier (recherche s
DataSet et recherche [ par dmk2003 ]
BonjourJe vous pose mon probleme !!!J'ai un dataset contenant toutes mes information client et j'aimerai chercher un client dans mon dataset (jusqua l
|
 Téléchargements
Logiciels à télécharger sur le même thème :
Comparez les prix Nouvelle version
HTC G1
Entre 449€ et 449€
|