Comment calculer la mesure de similitude de distance de 2 chaînes données?

Je viens d'aborder exactement le même problème il y a quelques semaines. Puisque quelqu'un Demande Maintenant, je vais partager le code. Dans mes tests exhaustifs, mon code est environ 10 fois plus rapide que l'exemple C# sur Wikipedia même lorsqu'aucune distance maximale n'est fournie. Lorsqu'une distance maximale est fournie, ce gain de performance augmente à 30x-100x +. Notez quelques points clés pour la performance:

• si vous devez comparer les mêmes mots encore et encore, convertissez d'abord les mots en tableaux d'entiers. Le L'algorithme de Damerau-Levenshtein inclut de nombreuses comparaisons >, ints comparent beaucoup plus rapidement que chars.
• Il comprend un mécanisme de court-circuit pour arrêter si la distance dépasse un maximum fourni
• utilisez un ensemble rotatif de trois tableaux plutôt qu'une matrice massive comme dans toutes les implémentations que j'ai vues ailleurs
• Assurez-vous que vos tableaux découpent la largeur de mot la plus courte.

Code (cela fonctionne exactement de la même manière si vous remplacez int[] par String dans le déclarations de paramètres:

/// <summary>
/// Computes the Damerau-Levenshtein Distance between two strings, represented as arrays of
/// integers, where each integer represents the code point of a character in the source string.
/// Includes an optional threshhold which can be used to indicate the maximum allowable distance.
/// </summary>
/// <param name="source">An array of the code points of the first string</param>
/// <param name="target">An array of the code points of the second string</param>
/// <param name="threshold">Maximum allowable distance</param>
/// <returns>Int.MaxValue if threshhold exceeded; otherwise the Damerau-Leveshteim distance between the strings</returns>
public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) {

    int length1 = source.Length;
    int length2 = target.Length;

    // Return trivial case - difference in string lengths exceeds threshhold
    if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; }

    // Ensure arrays [i] / length1 use shorter length 
    if (length1 > length2) {
        Swap(ref target, ref source);
        Swap(ref length1, ref length2);
    }

    int maxi = length1;
    int maxj = length2;

    int[] dCurrent = new int[maxi + 1];
    int[] dMinus1 = new int[maxi + 1];
    int[] dMinus2 = new int[maxi + 1];
    int[] dSwap;

    for (int i = 0; i <= maxi; i++) { dCurrent[i] = i; }

    int jm1 = 0, im1 = 0, im2 = -1;

    for (int j = 1; j <= maxj; j++) {

        // Rotate
        dSwap = dMinus2;
        dMinus2 = dMinus1;
        dMinus1 = dCurrent;
        dCurrent = dSwap;

        // Initialize
        int minDistance = int.MaxValue;
        dCurrent[0] = j;
        im1 = 0;
        im2 = -1;

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

            int cost = source[im1] == target[jm1] ? 0 : 1;

            int del = dCurrent[im1] + 1;
            int ins = dMinus1[i] + 1;
            int sub = dMinus1[im1] + cost;

            //Fastest execution for min value of 3 integers
            int min = (del > ins) ? (ins > sub ? sub : ins) : (del > sub ? sub : del);

            if (i > 1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2])
                min = Math.Min(min, dMinus2[im2] + cost);

            dCurrent[i] = min;
            if (min < minDistance) { minDistance = min; }
            im1++;
            im2++;
        }
        jm1++;
        if (minDistance > threshold) { return int.MaxValue; }
    }

    int result = dCurrent[maxi];
    return (result > threshold) ? int.MaxValue : result;
}

Où Swap est:

static void Swap<T>(ref T arg1,ref T arg2) {
    T temp = arg1;
    arg1 = arg2;
    arg2 = temp;
}

Il existe un grand nombre d'algorithmes de distance de similarité de chaîne qui peuvent être utilisés. Certains énumérés ici (mais pas exhaustivement énumérés sont):

• Levenstein
• Needleman Wunch
• Smith Waterman
• Smith Waterman Gotoh
• Jaro, Jaro-Winkler
• La Similarité De Jaccard
• La Distance Euclidienne
• Dés Similarité
• Similarité Cosinus
• Monge Elkan

Un la bibliothèque qui contient l'implémentation de tous ces éléments est appelée SimMetrics qui a à la fois java et c # implémentations.

J'ai trouvé que Levenshtein et Jaro-Winkler sont excellents pour les petites différences entre les chaînes telles que:

• fautes d'Orthographe; ou
• √ au lieu de o dans un personnes nom.

Cependant, en comparant quelque chose comme les titres d'articles où des morceaux significatifs du texte seraient les mêmes mais avec du "bruit" sur les bords, Smith-Waterman-Gotoh a été fantastique:

Comparez ces 2 titres (qui sont le même mais formulé différemment de différentes sources):

Une endonucléase d'Escherichia coli qui introduit des scissions de chaînes polynucléotidiques uniques dans L'ADN irradié aux ultraviolets

Endonucléase III: une endonucléase d'Escherichia coli qui introduit des Scissions de chaînes polynucléotidiques uniques dans L'ADN irradié aux ultraviolets

Ce site fournit une comparaison d'algorithme des chaînes montre:

• Levenshtein: 81
• Smith-Waterman Gotoh 94
• Jaro Winkler 78

Jaro Winkler et Levenshtein ne sont pas aussi compétents que Smith Waterman Gotoh pour détecter la similitude. Si nous comparons deux titres qui ne sont pas le même article, mais qui ont du texte correspondant:

Métabolisme des graisses dans les plantes supérieures. la fonction des acyl thioestérases dans le métabolisme des acyl-coenzymes A et protéine porteuse d'acyle-acyle s

Métabolisme des graisses dans les plantes supérieures. la détermination de protéine porteuse acyle-acyle et coenzyme acyle {[11] } A dans un mélange lipidique complexe

Jaro Winkler donne un faux positif, mais Smith Waterman Gotoh ne le fait pas:

• Levenshtein: 54
• Smith-Waterman Gotoh 49
• Jaro Winkler 89

Commeanastasiosyal a souligné, SimMetrics a le code java pour ces algorithmes. J'ai eu du succès en utilisant le code java SmithWatermanGotoh de SimMetrics .

Voici une approche alternative:

, C'est trop long pour un commentaire.

Une méthode typique pour trouver la similarité est la distance de Levenshtein, et il n'y a aucun doute une bibliothèque avec du code disponible.

Malheureusement, cela nécessite une comparaison avec chaque chaîne. Vous pourriez être en mesure d'écrire une version spécialisée du code pour court-circuiter le calcul si la distance est supérieure à un certain seuil, vous devrez toujours faire toutes les comparaisons.

Une autre idée est pour utiliser une variante de trigrammes ou n-grammes. Ce sont des séquences de n caractères (ou n mots ou n séquences génomiques ou n quoi que ce soit). Gardez un mappage des trigrammes aux chaînes et choisissez ceux qui ont le plus grand chevauchement. Un choix typique de n est "3", d'où le nom.

Par exemple, l'anglais aurait ces trigrammes:

• Fra
• ngl
• gli
• lis
• ish

Et L'Angleterre avoir:

• Fra
• ngl
• gla
• lan
• et

Eh bien, 2 sur 7 (ou 4 sur 10) correspondent. Si cela fonctionne pour vous, et vous pouvez indexer la table trigramme/chaîne et obtenir une recherche plus rapide.

Vous pouvez également combiner cela avec Levenshtein pour réduire l'ensemble de comparaison à ceux qui ont un nombre minimum de n-grammes en commun.

Voici mon implémentation de Damerau Levenshtein Distance, qui renvoie non seulement le coefficient de similarité, mais renvoie également les emplacements d'erreur dans Word corrigé (cette fonctionnalité peut être utilisée dans les éditeurs de texte). Aussi mon implémentation prend en charge différents poids d'erreurs (substitution, suppression, insertion, transposition).

public static List<Mistake> OptimalStringAlignmentDistance(
  string word, string correctedWord,
  bool transposition = true,
  int substitutionCost = 1,
  int insertionCost = 1,
  int deletionCost = 1,
  int transpositionCost = 1)
{
    int w_length = word.Length;
    int cw_length = correctedWord.Length;
    var d = new KeyValuePair<int, CharMistakeType>[w_length + 1, cw_length + 1];
    var result = new List<Mistake>(Math.Max(w_length, cw_length));

    if (w_length == 0)
    {
        for (int i = 0; i < cw_length; i++)
            result.Add(new Mistake(i, CharMistakeType.Insertion));
        return result;
    }

    for (int i = 0; i <= w_length; i++)
        d[i, 0] = new KeyValuePair<int, CharMistakeType>(i, CharMistakeType.None);

    for (int j = 0; j <= cw_length; j++)
        d[0, j] = new KeyValuePair<int, CharMistakeType>(j, CharMistakeType.None);

    for (int i = 1; i <= w_length; i++)
    {
        for (int j = 1; j <= cw_length; j++)
        {
            bool equal = correctedWord[j - 1] == word[i - 1];
            int delCost = d[i - 1, j].Key + deletionCost;
            int insCost = d[i, j - 1].Key + insertionCost;
            int subCost = d[i - 1, j - 1].Key;
            if (!equal)
                subCost += substitutionCost;
            int transCost = int.MaxValue;
            if (transposition && i > 1 && j > 1 && word[i - 1] == correctedWord[j - 2] && word[i - 2] == correctedWord[j - 1])
            {
                transCost = d[i - 2, j - 2].Key;
                if (!equal)
                    transCost += transpositionCost;
            }

            int min = delCost;
            CharMistakeType mistakeType = CharMistakeType.Deletion;
            if (insCost < min)
            {
                min = insCost;
                mistakeType = CharMistakeType.Insertion;
            }
            if (subCost < min)
            {
                min = subCost;
                mistakeType = equal ? CharMistakeType.None : CharMistakeType.Substitution;
            }
            if (transCost < min)
            {
                min = transCost;
                mistakeType = CharMistakeType.Transposition;
            }

            d[i, j] = new KeyValuePair<int, CharMistakeType>(min, mistakeType);
        }
    }

    int w_ind = w_length;
    int cw_ind = cw_length;
    while (w_ind >= 0 && cw_ind >= 0)
    {
        switch (d[w_ind, cw_ind].Value)
        {
            case CharMistakeType.None:
                w_ind--;
                cw_ind--;
                break;
            case CharMistakeType.Substitution:
                result.Add(new Mistake(cw_ind - 1, CharMistakeType.Substitution));
                w_ind--;
                cw_ind--;
                break;
            case CharMistakeType.Deletion:
                result.Add(new Mistake(cw_ind, CharMistakeType.Deletion));
                w_ind--;
                break;
            case CharMistakeType.Insertion:
                result.Add(new Mistake(cw_ind - 1, CharMistakeType.Insertion));
                cw_ind--;
                break;
            case CharMistakeType.Transposition:
                result.Add(new Mistake(cw_ind - 2, CharMistakeType.Transposition));
                w_ind -= 2;
                cw_ind -= 2;
                break;
        }
    }
    if (d[w_length, cw_length].Key > result.Count)
    {
        int delMistakesCount = d[w_length, cw_length].Key - result.Count;
        for (int i = 0; i < delMistakesCount; i++)
            result.Add(new Mistake(0, CharMistakeType.Deletion));
    }

    result.Reverse();

    return result;
}

public struct Mistake
{
    public int Position;
    public CharMistakeType Type;

    public Mistake(int position, CharMistakeType type)
    {
        Position = position;
        Type = type;
    }

    public override string ToString()
    {
        return Position + ", " + Type;
    }
}

public enum CharMistakeType
{
    None,
    Substitution,
    Insertion,
    Deletion,
    Transposition
}

CE code fait partie de mon projet: Yandex-Linguistics.NET .

J'ai écrit certains tests et il me semble que la méthode est travailler.

Mais les commentaires et remarques sont les bienvenus.

Voici un VB.net mise en œuvre:

Public Shared Function LevenshteinDistance(ByVal v1 As String, ByVal v2 As String) As Integer
    Dim cost(v1.Length, v2.Length) As Integer
    If v1.Length = 0 Then
        Return v2.Length                'if string 1 is empty, the number of edits will be the insertion of all characters in string 2
    ElseIf v2.Length = 0 Then
        Return v1.Length                'if string 2 is empty, the number of edits will be the insertion of all characters in string 1
    Else
        'setup the base costs for inserting the correct characters
        For v1Count As Integer = 0 To v1.Length
            cost(v1Count, 0) = v1Count
        Next v1Count
        For v2Count As Integer = 0 To v2.Length
            cost(0, v2Count) = v2Count
        Next v2Count
        'now work out the cheapest route to having the correct characters
        For v1Count As Integer = 1 To v1.Length
            For v2Count As Integer = 1 To v2.Length
                'the first min term is the cost of editing the character in place (which will be the cost-to-date or the cost-to-date + 1 (depending on whether a change is required)
                'the second min term is the cost of inserting the correct character into string 1 (cost-to-date + 1), 
                'the third min term is the cost of inserting the correct character into string 2 (cost-to-date + 1) and 
                cost(v1Count, v2Count) = Math.Min(
                    cost(v1Count - 1, v2Count - 1) + If(v1.Chars(v1Count - 1) = v2.Chars(v2Count - 1), 0, 1),
                    Math.Min(
                        cost(v1Count - 1, v2Count) + 1,
                        cost(v1Count, v2Count - 1) + 1
                    )
                )
            Next v2Count
        Next v1Count

        'the final result is the cheapest cost to get the two strings to match, which is the bottom right cell in the matrix
        'in the event of strings being equal, this will be the result of zipping diagonally down the matrix (which will be square as the strings are the same length)
        Return cost(v1.Length, v2.Length)
    End If
End Function