APPLICATION DE L'ALGO DE WAGNER ET FISHER

---

Commentaire sur cette source (4)
Ajouter un commentaire et/ou une note

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.

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;
        }

C'est un algo très connu mais il peut être utile aux développeurs qui souhaitent incorporer cette fonctionnalité.

08 avril 2008 18:52:51 :

nettoyage du code, amélioration fonctionnelle.

• ENHANCED STRING MATCHING
• RECHERCHE OPERATIONNELLE
• DIJKSTRA EN PRATIQUE
• PID PROPORTIONNEL INTEGRAL DERIVE
• CALCUL DES NOMBRES PREMIERS PAR LA CRIBLE D'ÉRATOSTHÈNE

• ENHANCED STRING MATCHING
• DIJKSTRA EN PRATIQUE
• GENERATEUR DE LABYRINTHES ALEATOIRE
• GESTION COMPLETE D'UNE BASE DE DONNEE ACCESS
• PRIORITY QUEUE