Application de l'algo de wagner et fisher

Soyez le premier à donner votre avis sur cette source.

Snippet vu 8 212 fois - Téléchargée 17 fois

Contenu du snippet

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 / Exemple :


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é.

A voir également

Ajouter un commentaire

Commentaires

artosane
Messages postés
6
Date d'inscription
mercredi 20 avril 2005
Statut
Membre
Dernière intervention
9 avril 2008

ouaip, le levenshtein est bien performant paraît-il.

Il s'appuie sur le Wagner et Fisher il me semble, mais ce n'est pas tout à fait le même.

Je vais matter ce qu'il donne dans mon application.
cs_Bidou
Messages postés
5487
Date d'inscription
dimanche 4 août 2002
Statut
Modérateur
Dernière intervention
20 juin 2013
44
artosane
Messages postés
6
Date d'inscription
mercredi 20 avril 2005
Statut
Membre
Dernière intervention
9 avril 2008

ouaip, pas de soucis. Je comptais le faire hier soir, mais à vrai dire je viens d'imaginer une optimisation. Parce que, bien qu'il soit intéressant, cet algo est peu performant lorsqu'il s'agit de traiter des chaînes de longueurs très inégales.

Je compte donc augmenter le poids de proximité des chaînes longues et décrémenter plus les chaînes sont courtes. Ce qui permettrait d'avoir de biens meilleurs résultats.

Je mettrai à jour lorsque cela sera fait.
sebmafate
Messages postés
4936
Date d'inscription
lundi 17 février 2003
Statut
Modérateur
Dernière intervention
14 février 2014
32
Mettre un algo intéressant : ok
Mais le rendre réutilisable : c'est mieux.

Merci de mettre à jour pour qu'il soit facilement intégrable.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (artosane)