Le blog

L’algorithme de Levenshtein permet de mesurer mathématiquement la « distance » entre 2 chaînes de caractères, c’est-à-dire leur similarité.

La méthode a été inventée par le scientifique russe Vladimir Levenshtein en 1965.

La « distance » mesurée correspond au nombre de caractères qu'il faut supprimer, insérer ou remplacer pour passer d’une chaîne à l’autre :

• Plus le nombre obtenu est faible, plus les chaînes sont similaires
• Plus le nombre obtenu est élevé, plus les chaînes sont différentes.

Exemple :

Pour passer de la chaîne « CHAMBRE » à la chaîne « CRABES », les étapes suivantes sont nécessaires :

• Remplacement du H en R : CRAMBRE
• Suppression du M : CRABRE
• Suppression 2^ème R : CRABE
• Ajout d'un S : CRABES

Soit au total 4 étapes. La distance de Levensthein est donc de 4.

Mise en application

Dans une application, un tel algorithme va nous permettre d’optimiser les saisies dans les zones de texte :

• optimiser les recherches par mots-clés
• proposer des chaînes similaires lors de la saisie (« auto-complétion »)
• corriger les fautes de frappes (inversion de 2 caractères, caractère manquant, etc…)
• standardiser les saisies manuelles libres (exemple : uniformiser des adresses postales)
• dédoublonner des éléments similaires
• etc…

Il suffira de comparer la chaîne saisie à une liste de chaînes mémorisées par ailleurs, et de ne proposer à l’utilisateur que celles ayant la plus faible distance avec la chaîne saisie.

Syntaxe en C#.NET

La syntaxe en différents langages peut facilement être trouvée sur le Web.

Voici un exemple en C#.NET :

private Int32 levenshtein(String a, String b)
    {
        if (string.IsNullOrEmpty(a))
        {
            if (!string.IsNullOrEmpty(b))
            {
                return b.Length;
            }
            return 0;
        }

        if (string.IsNullOrEmpty(b))
        {
            if (!string.IsNullOrEmpty(a))
            {
                return a.Length;
            }
            return 0;
        }

        Int32 cost;
        Int32[,] d = new int[a.Length + 1, b.Length + 1];
        Int32 min1;
        Int32 min2;
        Int32 min3;

        for (Int32 i = 0; i <= d.GetUpperBound(0); i += 1)
        {
            d[i, 0] = i;
        }

        for (Int32 i = 0; i <= d.GetUpperBound(1); i += 1)
        {
            d[0, i] = i;
        }

        for (Int32 i = 1; i <= d.GetUpperBound(0); i += 1)
        {
            for (Int32 j = 1; j <= d.GetUpperBound(1); j += 1)
            {
                cost = Convert.ToInt32(!(a[i-1] == b[j - 1]));

                min1 = d[i - 1, j] + 1;
                min2 = d[i, j - 1] + 1;
                min3 = d[i - 1, j - 1] + cost;
                d[i, j] = Math.Min(Math.Min(min1, min2), min3);
            }
        }

        return d[d.GetUpperBound(0), d.GetUpperBound(1)];

    }

L'appel du calcul se fait tout simplement par :

string a = "CHAMBRE";
string b = "CRABES";
int distance = levenshtein(a, b);   //retourne 4

Exemple

Prenons l’exemple d’une application gérant une liste de fournisseurs.

L’utilisateur souhaite rechercher un fournisseur par sa raison sociale, mais il n’en connait pas la syntaxe exacte.

L’algorithme de Levensthein va permettre de lui proposer des résultats, malgré une syntaxe « approximative ».

Imaginons le cas suivant:

• L’utilisateur saisit dans sa zone de recherche « SA Imo Gestion». Le nom exact du fournisseur qu’il recherche est en fait « S.A. Immo-Gestion » (différences sur les points, le tiret, le « m » manquant)
• Nous disposons en base de données de la liste des fournisseurs.
• Pour chacun d’entre eux, nous calculons sa distance de Levensthein avec la chaîne saisie par l’utilisateur :

• Dans l’application, nous allons proposer à l’utilisateur les noms de fournisseurs qui ressemblent le plus à sa saisie. Par exemple, les 3 qui présentent le plus faible écart avec le nom recherché, triés par écart croissant.
• L’utilisateur se verra ainsi proposé, dans cet ordre, les 3 fournisseurs suivants :
  • 1) S.A. Immo-Gestion  (distance = 4)
  • 2) S.A. Gestion   (distance = 5)
  • 3) Immo & Gestion  (distance = 6)

=> Le fournisseur recherché est donc bien retrouvé, malgré les fautes ou approximations de saisie.

On notera que cette technique permet de toujours proposer des résultats à l’utilisateur, là où un simple « like » ou « contains » n’aurait ramené aucun résultat.

Optimisation et remarques :

• L’algorithme de Leventshein est surtout utilisé pour comparer des chaînes courtes. Pour des chaînes plus longues, d’autres algorithmes sont plus efficaces (algorithmes de Jaccard,  Term Frequency-Inverse Document Frequency).
• Au niveau de l’utilisation des ressources, il est indispensable de veiller à l’optimisation dans l’application, afin de ne pas lancer des calculs sur des volumes trop grands.
• Une autre technique peut être de découper les « phrases » en « mots » (en découpant sur le caractère espace), et de calculer la distance de Leventshein mot par mot plutôt que sur l’ensemble de la phrase.
• Plutôt que d’utiliser un nombre entier représentant la distance, il peut être intéressant de calculer le pourcentage d’écart avec la chaîne initiale, ou inversement le pourcentage de similarité.