1. #1
    Rédacteur/Modérateur


    Homme Profil pro
    Développeur .NET
    Inscrit en
    février 2004
    Messages
    19 840
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : février 2004
    Messages : 19 840
    Points : 40 643
    Points
    40 643

    Par défaut [Algorithme] Evaluer la similarité entre 2 chaines

    Salut,

    En développant un petit programme de blind-test, j'ai écrit un bout de code qui permet de comparer des chaines de façon "approximative".

    Le but est d'introduire une certaine tolérance dans les réponses données, car la réponse saisie par un joueur n'est souvent pas parfaitement exacte à cause des fautes de frappe et/ou d'orthographe... par exemple, si le joueur tape "pink floid" ou "pnk floyd" au lieu de "pink floyd", on peut considérer que c'est juste.

    Après pas mal de recherches sur la question, j'ai fini par tomber sur une notion appelée "distance de Levenshtein", qui correspond au nombre de transformations à effectuer sur une chaine A pour la transformer en une chaine B. Celà permet d'évaluer le degré de similarité entre les 2 chaines.

    J'ai donc implémenté en C# l'algorithme décrit sur le site. Comme la longueur des chaines rentre aussi en ligne de compte pour évaluer la similarité (2 différences sur une chaine de longueur 4 représente une plus grosse différence que sur une chaine de longueur 20...), j'ai aussi ajouté une notion de "coefficient de corrélation" entre les 2 chaines, en me basant sur les propriétés suivantes :
    • la distance de Levenshtein est toujours supérieure ou égale à la différence de longueur entre les 2 chaines
    • la distance de Levenshtein est toujours inférieure ou égale à la longueur de la plus longue chaine
    • la distance de Levenshtein entre 2 chaines identiques est 0


    Si on appelle d la distance de Levenshtein, et L la longueur de la plus longue chaine, on aura donc toujours :
    0 <= d/L <= 1
    On peut donc utiliser comme coefficient de corrélation 1 - d/L (de façon à avoir 1 pour des chaines identiques et 0 pour des chaines complètement différentes). A l'utilisation, on peut définir un "seuil de tolérance" par rapport à ce coefficient. Par exemple, on peut considérer qu'une réponse est acceptée si son coefficient de corrélation avec la bonne réponse est supérieur à 0.8.

    Cet algorithme (ou sa variante, la distance de Damerau–Levenshtein) est également utilisé dans les correcteurs orthographiques, et peut servir dès qu'on veut prendre en compte les erreurs de saisie.

    Voilà l'implémentation :

    Code C# : Sélectionner tout - Visualiser dans une fenêtre à part
    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
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
        public static class Levenshtein
        {
     
            /// <summary>
            /// Computes the Levenshtein distance between 2 strings
            /// Based on the algorithm described here :
            /// http://en.wikipedia.org/wiki/Levenshtein_distance
            /// </summary>
            /// <param name="a">first string to compare</param>
            /// <param name="b">second string to compare</param>
            /// <param name="caseSensitive">true if case should be considered, false otherwise</param>
            /// <returns>the Levenshtein distance between the 2 strings</returns>
            public static int ComputeDistance(string a, string b, bool caseSensitive)
            {
                if (!caseSensitive)
                {
                    a = a.ToLower();
                    b = b.ToLower();
                }
     
                int m = a.Length;
                int n = b.Length;
                int[,] d = new int[m + 1, n + 1];
     
                for (int i = 0; i <= m; i++)
                    d[i, 0] = i;
                for (int i = 0; i <= n; i++)
                    d[0, i] = i;
     
                for (int i = 1; i <= m; i++)
                {
                    for (int j = 1; j <= n; j++)
                    {
                        int cost;
                        if (a[i-1] == b[j-1])
                            cost = 0;
                        else
                            cost = 1;
                        d[i, j] = Min(  d[i - 1, j] + 1,
                                        d[i, j - 1] + 1,
                                        d[i - 1, j - 1] + cost);
                    }
                }
     
                return d[m, n];
            }
     
            /// <summary>
            /// Computes the correlation coefficient between 2 strings, based on the Levenshtein distance
            /// </summary>
            /// <param name="a">first string to compare</param>
            /// <param name="b">second string to compare</param>
            /// <param name="caseSensitive">true if case should be considered, false otherwise</param>
            /// <returns>The correlation coefficient between the 2 strings. This value can range from 0 (completely different strings) to 1 (identical strings)</returns>
            public static double ComputeCorrelation(string a, string b, bool caseSensitive)
            {
                int distance = ComputeDistance(a, b, caseSensitive);
                int longest = Max(a.Length, b.Length);
                return 1 - (double)distance / longest;
            }
     
            private static T Min<T>(T arg0, params T[] args) where T : IComparable
            {
                T min = arg0;
                for (int i = 0; i < args.Length; i++)
                {
                    T x = args[i];
                    if (x.CompareTo(min) < 0)
                        min = x;
                }
                return min;
            }
     
            private static T Max<T>(T arg0, params T[] args) where T : IComparable
            {
                T max = arg0;
                for (int i = 0; i < args.Length; i++)
                {
                    T x = args[i];
                    if (x.CompareTo(max) > 0)
                        max = x;
                }
                return max;
            }
        }

    Pour l'utiliser (toujours dans le contexte de mon blind-test) :
    Code C# : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
     
    double threshold = 0.8;
    double coef = Levenshtein.ComputeCorrelation(song.Artist, txtArtist.Text, false);
    if (coef > threshold)
        MessageBox.Show("Bonne réponse !");
    else
        MessageBox.Show("Mauvaise réponse !");

    En espérant que ça serve à quelqu'un...

  2. #2
    Candidat au Club
    Homme Profil pro
    Débutant
    Inscrit en
    juin 2014
    Messages
    4
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 18
    Localisation : France, Marne (Champagne Ardenne)

    Informations professionnelles :
    Activité : Débutant

    Informations forums :
    Inscription : juin 2014
    Messages : 4
    Points : 3
    Points
    3

    Par défaut Merci beaucoup

    Merci beaucoup , j'ai cherché cela en vain pendant des heures et je vais pouvoir implémenter cette algorithme en Python

  3. #3
    Rédacteur/Modérateur


    Homme Profil pro
    Développeur .NET
    Inscrit en
    février 2004
    Messages
    19 840
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : février 2004
    Messages : 19 840
    Points : 40 643
    Points
    40 643

    Par défaut

    Citation Envoyé par KinderConcept Voir le message
    Merci beaucoup , j'ai cherché cela en vain pendant des heures et je vais pouvoir implémenter cette algorithme en Python
    Salut,

    Si tu veux l'implémenter toi-même en Python, ce sera sans doute plus simple de partir du pseudo code sur Wikipedia que d'un implémentation en C#

  4. #4
    Membre à l'essai
    Profil pro
    Inscrit en
    décembre 2011
    Messages
    24
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : décembre 2011
    Messages : 24
    Points : 19
    Points
    19

    Par défaut

    Super. Ca marche nickel

Discussions similaires

  1. Réponses: 2
    Dernier message: 03/05/2014, 16h10
  2. [XL-2000] Evaluer la similitude entre 2 chaines de caractères
    Par Monjarno dans le forum Macros et VBA Excel
    Réponses: 5
    Dernier message: 07/07/2010, 09h35
  3. Réponses: 2
    Dernier message: 13/04/2010, 08h23
  4. Similarité entre deux chaines binaires
    Par arkandias dans le forum Général Algorithmique
    Réponses: 7
    Dernier message: 31/12/2007, 00h05
  5. [Linux] [NASM] Entrée de chaines
    Par vi4ever dans le forum Assembleur
    Réponses: 4
    Dernier message: 27/07/2004, 22h28

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo