Comparer des chaînes avec une tolérance

Question

Je recherche un moyen de comparer une chaîne de caractères avec un tableau de chaînes de caractères. Faire une recherche exacte est bien sûr assez facile, mais je veux que mon programme tolère les fautes d'orthographe, les parties manquantes de la chaîne, et ainsi de suite.

Y a-t-il un genre de framework qui peut effectuer une telle recherche? J'ai en tête un algorithme de recherche qui renverra quelques résultats triés par pourcentage de correspondance ou quelque chose du genre.

Answer 1

Vous pourriez utiliser l'algorithme de distance de Levenshtein.

"La distance de Levenshtein entre deux chaînes est définie comme le nombre minimum d'éditions nécessaires pour transformer une chaîne en une autre, les opérations d'édition autorisées étant l'insertion, la suppression ou la substitution d'un seul caractère." - Wikipedia.com

Celui-ci vient de dotnetperls.com:

using System;

/// 
/// Contient la correspondance approximative de chaînes
/// 
static class LevenshteinDistance
{
    /// 
    /// Calcul de la distance entre deux chaînes.
    /// 
    public static int Compute(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        // Étape 1
        if (n == 0)
        {
            return m;
        }

        if (m == 0)
        {
            return n;
        }

        // Étape 2
        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }

        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }

        // Étape 3
        for (int i = 1; i <= n; i++)
        {
            //Étape 4
            for (int j = 1; j <= m; j++)
            {
                // Étape 5
                int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                // Étape 6
                d[i, j] = Math.Min(
                    Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }
        // Étape 7
        return d[n, m];
    }
}

class Program
{
    static void Main()
    {
        Console.WriteLine(LevenshteinDistance.Compute("tante", "fourmi"));
        Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha"));
        Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax"));
    }
}

Vous pouvez préférer utiliser l'algorithme de distance de Damerau-Levenshtein, qui permet également aux caractères d'être transposés, ce qui est une erreur humaine courante lors de la saisie de données. Vous trouverez une implémentation en C# de celle-ci ici.

Answer 2

Il n'y a rien dans le framework .NET qui vous aidera avec ça immédiatement.

Les fautes d'orthographe les plus courantes sont celles où les lettres sont une représentation phonétique correcte du mot, mais pas l'orthographe correcte du mot.

Par exemple, on pourrait argumenter que les mots épée et épeé (oui, c'est un mot) ont les mêmes racines phonétiques (ils sonnent pareil quand vous les prononcez).

Cela dit, il existe plusieurs algorithmes que vous pouvez utiliser pour traduire des mots (même mal orthographiés) en variantes phonétiques.

Le premier est Soundex. Il est assez simple à implémenter et il existe un bon nombre d'implémentations .NET de cet algorithme. C'est plutôt simple, mais cela vous donne des valeurs réelles que vous pouvez comparer entre elles.

Un autre est Metaphone. Bien que je ne puisse pas trouver une implémentation native .NET de Metaphone, le lien fourni renvoie vers plusieurs autres implémentations qui pourraient être converties. La plus facile à convertir serait probablement l' implémentation Java de l'algorithme Metaphone.

Il convient de noter que l'algorithme Metaphone a été révisé. Il y a Double Metaphone (qui dispose d'une implémentation .NET) et Metaphone 3. Metaphone 3 est une application commerciale, mais a un taux de précision de 98% comparé à un taux de précision de 89% pour l'algorithme Double Metaphone lorsqu'il est exécuté sur une base de données de mots anglais courants. Selon vos besoins, vous pourriez vouloir rechercher (dans le cas de Double Metaphone) ou acheter (dans le cas de Metaphone 3) la source de l'algorithme et la convertir ou y accéder via la couche P/Invoke (il existe de nombreuses implémentations en C++).

Metaphone et Soundex diffèrent en ce sens que Soundex produit des clés numériques de longueur fixe, tandis que Metaphone produit des clés de longueurs différentes, donc les résultats seront différents. Au final, les deux feront le même type de comparaison pour vous, vous devez juste déterminer celui qui convient le mieux à vos besoins, en fonction de vos exigences et de vos ressources (et de votre tolérance aux fautes d'orthographe, bien sûr).

Answer 3

Votre autre option est de comparer phonétiquement en utilisant Soundex ou Metaphone. Je viens de terminer un article qui présente du code C# pour les deux algorithmes. Vous pouvez le consulter sur http://www.blackbeltcoder.com/Articles/algorithms/phonetic-string-comparison-with-soundex.

Answer 4

Voici deux méthodes qui calculent la Distance de Levenshtein entre les chaînes de caractères.

La distance de Levenshtein entre deux chaînes de caractères est définie comme le nombre minimum de modifications nécessaires pour transformer une chaîne en une autre, avec les opérations de modification autorisées étant l'insertion, la suppression ou la substitution d'un seul caractère.

Une fois que vous avez le résultat, vous devrez définir quelle valeur vous voulez utiliser comme seuil pour une correspondance ou non. Exécutez la fonction sur un ensemble de données d'exemple pour avoir une bonne idée de son fonctionnement et vous aider à décider de votre seuil spécifique.

    /// 
    /// Calcule la distance de Levenshtein entre deux chaînes de caractères - le nombre de changements nécessaires pour que la première chaîne devienne la seconde.
    /// 
    /// La première chaîne, utilisée comme source.
    /// La deuxième chaîne, utilisée comme cible.
    /// Le nombre de changements nécessaires pour convertir la première chaîne en la seconde.
    /// 
    /// De http://www.merriampark.com/ldcsharp.htm
    /// 
    public static int LevenshteinDistance(string first, string second)
    {
        if (first == null)
        {
            throw new ArgumentNullException("first");
        }
        if (second == null)
        {
            throw new ArgumentNullException("second");
        }

        int n = first.Length;
        int m = second.Length;
        var d = new int[n + 1, m + 1]; // matrice

        if (n == 0) return m;
        if (m == 0) return n;

        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }

        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }

        for (int i = 1; i <= n; i++)
        {

            for (int j = 1; j <= m; j++)
            {
                int cost = (second.Substring(j - 1, 1) == first.Substring(i - 1, 1) ? 0 : 1); // coût
                d[i, j] = Math.Min(
                    Math.Min(
                        d[i - 1, j] + 1,
                        d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }

        return d[n, m];
    }

Answer 5

Vous pouvez trouver des implémentations des algorithmes soundex et de la distance levenshtein dans le projet open source CommonLibrary.NET.