Discussion :

[tomlev]

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

[KinderConcept]

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

[tomlev]

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#

[joss63]

Super. Ca marche nickel