Comment puis-je mesurer la similarité entre deux chaînes de caractères ?

Question

Étant donné deux chaînes de caractères text1 y text2 :

public SOMEUSABLERETURNTYPE Compare(string text1, string text2)
{
     // DO SOMETHING HERE TO COMPARE
}

Exemples :

1. Première corde : StackOverflow

   Deuxième corde : StaqOverflow

   Retour : La similitude est de 91%

   Le rendement peut être en % ou quelque chose comme ça.

2. Première corde : Le test du texte simple

   Deuxième corde : Le test du texte complexe

   Retour : Les valeurs peuvent être considérées comme égales

Des idées ? Quelle est la meilleure façon de procéder ?

Answer 1

Il existe plusieurs façons de procéder. Jetez un coup d'œil à la Page Wikipedia "Mesures de similarité des chaînes de caractères pour les liens vers d'autres pages contenant des algorithmes.

Je ne sais pas. pensez à Cependant, aucun de ces algorithmes ne prend en compte les sons. Ainsi, "staq overflow" serait aussi similaire à "stack overflow" qu'à "staw overflow", bien que le premier soit plus proche en termes de prononciation.

Je viens de trouver une autre page qui donne un peu plus d'options... en particulier, l'option Soundex algorithme ( Wikipedia ) peut être plus proche de ce que vous recherchez.

Answer 2

distance de Levenshtein est probablement ce que vous recherchez.

Answer 3

Voici un peu de code que j'ai écrit pour un projet sur lequel je travaille. J'ai besoin de connaître le rapport de similarité des chaînes de caractères et le rapport de similarité basé sur les mots des chaînes de caractères. Dans ce dernier cas, je veux connaître à la fois le rapport de similarité des mots de la plus petite chaîne (donc si tous les mots existent et correspondent dans la plus grande chaîne, le résultat sera de 100%) et le rapport de similarité des mots de la plus grande chaîne (que j'appelle RealWordsRatio). J'utilise l'algorithme de Levenshtein pour trouver la distance. Le code n'est pas optimisé pour l'instant, mais il fonctionne comme prévu. J'espère que vous le trouverez utile.

public static int Compute(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

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

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

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

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

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

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

double GetSimilarityRatio(String FullString1, String FullString2, out double WordsRatio, out double RealWordsRatio)
    {
        double theResult = 0;
        String[] Splitted1 = FullString1.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries);
        String[] Splitted2 = FullString2.Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries);
        if (Splitted1.Length < Splitted2.Length)
        {
            String[] Temp = Splitted2;
            Splitted2 = Splitted1;
            Splitted1 = Temp;
        }
        int[,] theScores = new int[Splitted1.Length, Splitted2.Length];//Keep the best scores for each word.0 is the best, 1000 is the starting.
        int[] BestWord = new int[Splitted1.Length];//Index to the best word of Splitted2 for the Splitted1.

        for (int loop = 0; loop < Splitted1.Length; loop++) 
        {
            for (int loop1 = 0; loop1 < Splitted2.Length; loop1++) theScores[loop, loop1] = 1000;
            BestWord[loop] = -1;
        }
        int WordsMatched = 0;
        for (int loop = 0; loop < Splitted1.Length; loop++)
        {
            String String1 = Splitted1[loop];
            for (int loop1 = 0; loop1 < Splitted2.Length; loop1++)
            {
                String String2 = Splitted2[loop1];
                int LevenshteinDistance = Compute(String1, String2);
                theScores[loop, loop1] = LevenshteinDistance;
                if (BestWord[loop] == -1 || theScores[loop, BestWord[loop]] > LevenshteinDistance) BestWord[loop] = loop1;
            }
        }

        for (int loop = 0; loop < Splitted1.Length; loop++)
        {
            if (theScores[loop, BestWord[loop]] == 1000) continue;
            for (int loop1 = loop + 1; loop1 < Splitted1.Length; loop1++)
            {
                if (theScores[loop1, BestWord[loop1]] == 1000) continue;//the worst score available, so there are no more words left
                if (BestWord[loop] == BestWord[loop1])//2 words have the same best word
                {
                    //The first in order has the advantage of keeping the word in equality
                    if (theScores[loop, BestWord[loop]] <= theScores[loop1, BestWord[loop1]])
                    {
                        theScores[loop1, BestWord[loop1]] = 1000;
                        int CurrentBest = -1;
                        int CurrentScore = 1000;
                        for (int loop2 = 0; loop2 < Splitted2.Length; loop2++)
                        {
                            //Find next bestword
                            if (CurrentBest == -1 || CurrentScore > theScores[loop1, loop2])
                            {
                                CurrentBest = loop2;
                                CurrentScore = theScores[loop1, loop2];
                            }
                        }
                        BestWord[loop1] = CurrentBest;
                    }
                    else//the latter has a better score
                    {
                        theScores[loop, BestWord[loop]] = 1000;
                        int CurrentBest = -1;
                        int CurrentScore = 1000;
                        for (int loop2 = 0; loop2 < Splitted2.Length; loop2++)
                        {
                            //Find next bestword
                            if (CurrentBest == -1 || CurrentScore > theScores[loop, loop2])
                            {
                                CurrentBest = loop2;
                                CurrentScore = theScores[loop, loop2];
                            }
                        }
                        BestWord[loop] = CurrentBest;
                    }

                    loop = -1;
                    break;//recalculate all
                }
            }
        }
        for (int loop = 0; loop < Splitted1.Length; loop++)
        {
            if (theScores[loop, BestWord[loop]] == 1000) theResult += Splitted1[loop].Length;//All words without a score for best word are max failures
            else
            {
                theResult += theScores[loop, BestWord[loop]];
                if (theScores[loop, BestWord[loop]] == 0) WordsMatched++;
            }
        }
        int theLength = (FullString1.Replace(" ", "").Length > FullString2.Replace(" ", "").Length) ? FullString1.Replace(" ", "").Length : FullString2.Replace(" ", "").Length;
        if(theResult > theLength) theResult = theLength;
        theResult = (1 - (theResult / theLength)) * 100;
        WordsRatio = ((double)WordsMatched / (double)Splitted2.Length) * 100;
        RealWordsRatio = ((double)WordsMatched / (double)Splitted1.Length) * 100;
        return theResult;
    }

Answer 4

J'ai écrit un Implémentation du double métaphone en C# il y a quelque temps. Vous le trouverez largement supérieur à Soundex et autres.

La distance de Levenshtein a également été suggérée, et il s'agit d'un excellent algorithme pour de nombreuses utilisations, mais la correspondance phonétique n'est pas vraiment ce qu'il fait ; cela semble parfois être le cas parce que les mots phonétiquement similaires sont aussi généralement orthographiés de manière similaire. J'ai fait une analyse de divers algorithmes de correspondance floue que vous pourriez également trouver utile.

Answer 5

Pour traiter les "sosies", vous pouvez envisager de coder à l'aide d'un algorithme phonétique tel que Double Metaphone ou soundex. Je ne sais pas si le calcul des distances de Levenshtein sur des chaînes codées phonétiquement serait bénéfique ou non, mais cela pourrait être une possibilité. Sinon, vous pourriez utiliser une heuristique du type : convertir chaque mot de la chaîne sous sa forme codée et supprimer tous les mots qui apparaissent dans les deux chaînes pour les remplacer par une seule représentation avant de calculer la distance de Levenshtein.