Accueil > > > APPLICATION DE L'ALGO DE WAGNER ET FISHER
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
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
|
Derniers Blogs
[TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES[TECHDAYS 2012] SESSION WEBMATRIX 2 : LE COUTEAU SUISSE GRATUIT POUR VOS DéVELOPPEMENTS WEB - SLIDES par gpommier
Suite à la session que j'ai présenté sur WebMatrix 2, vous pouvez trouver les slides ici, ainsi que les démos en packages nuget : démos1 et démos2 J'en profite pour remercier chaleureusement tous ceux qui sont venus très nombreux à cette sess...
Cliquez pour lire la suite de l'article par gpommier [SHAREPOINT] LES SESSIONS TECHDAYS 2012.[SHAREPOINT] LES SESSIONS TECHDAYS 2012. par Patrick Guimonet
Voici donc pour ceux qui n'ont pas pu venir, ou ceux qui n'ont pas pu toutes les suivre la liste des sessions SharePoint aux TechDays 2012, que je mettrais à jour dès que les liens des vidéo seront disponibles. Ou ici : http...
Cliquez pour lire la suite de l'article par Patrick Guimonet TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3TECHDAYS PARIS 2012 : SESSION PLEINIèRE JOUR 3 par ROMELARD Fabrice
Speaker: Bernard Ourghanlian Cette session est comme chaque jour transmise en live par BrainSonic, et j'ai donc suivi cette troisième pleinière par ce moyen sur mon iPad . Elle est dédiée comme chaque année à la mise en perspective de l'é...
Cliquez pour lire la suite de l'article par ROMELARD Fabrice MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE !MISHRA READER : UN LECTEUR RSS TRèS ZUNE STYLE EN OPEN SOURCE ! par Vko
Hier durant une session dédiée aux Techdays 2012, j'ai eu le plaisir d'annoncer la sortie de la Béta 2 de Mishra Reader. C'est quoi ? Pour les utilisateurs, c'est une vraie expérience de lecture de flux RSS sur Windows. Rien à voir avec les produit...
Cliquez pour lire la suite de l'article par Vko [FRAMEWORK 4] LES TASKS ET LE THREAD UI[FRAMEWORK 4] LES TASKS ET LE THREAD UI par fathi
Je viens de passer quelques temps au TechDay's et j'ai pu voir pas mal de session intéressante. Par contre une chose m'a un peu étonné lors de certaines de ces sessions qui abordaient les améliorations du framework .NET (donc le 4.5) : en gros, bea...
Cliquez pour lire la suite de l'article par fathi
Logiciels
Academy System (17.2.1.0)ACADEMY SYSTEM (17.2.1.0)Logiciel de gestion des établissements.
- élèves/étudiants (inscription, dossier, absence...)
-... Cliquez pour télécharger Academy System Easy-Planning (1.0.0.1)EASY-PLANNING (1.0.0.1)Basé sur les mêmes principes que MyPlanning, Easy-Planning permet de créer des plannings sous la ... Cliquez pour télécharger Easy-Planning COLLECTOR PLUS (3.00B)COLLECTOR PLUS (3.00B)COLLECTOR PLUS version 3.00B est un logiciel utilisant une base de données alimentée par :
- L... Cliquez pour télécharger COLLECTOR PLUS PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO (V7.4)PONAMEDIA TV DEVIENS HELLLOOO FLASH
LA TV SUR VOTRE ORDINATEUR.
Toute une plateforme Multi... Cliquez pour télécharger PONAMEDIA PREMIUM - HELLLOOO FLASH DEMO LettresFaciles 2011 (8.0.0.1)LETTRESFACILES 2011 (8.0.0.1)LettresFaciles est un logiciel facilitant la création et la rédaction de lettres types.
Son inte... Cliquez pour télécharger LettresFaciles 2011
|