Comment puis-je calculer efficacement la distance Damerau-Levenshtein entre deux cordes ?

Utilisez l'algorithme de Damerau-Levenshtein pour calculer la similarité de distance d'une chaîne donnée

Déterminer la similarité entre les chaînes est crucial dans diverses applications telles que la vérification orthographique et la comparaison de texte. La distance Damerau-Levenshtein est une mesure efficace qui calcule le nombre minimum de modifications (insertions, suppressions, substitutions ou transpositions) requises pour transformer une chaîne en une autre.

Optimisation des performances de l'algorithme de Damerau-Levenshtein

Pour des performances optimales lors du calcul de la distance Damerau-Levenshtein, tenez compte des points clés suivants :

• Convertir une chaîne en un tableau d'entiers : La comparaison de tableaux d'entiers est beaucoup plus rapide que les tableaux de caractères.
• Mécanisme de court-circuit : Si la distance actuelle dépasse le seuil spécifié, arrêtez le calcul.
• Rotation de la collection de tableaux : Utilisez trois tableaux au lieu de grandes matrices pour réduire la surcharge de mémoire.
• Optimisez le découpage des tableaux : Assurez-vous que les tableaux sont alignés avec des chaînes plus courtes.

Mise en œuvre du code

L'extrait de code C# optimisé suivant implémente l'algorithme de Damerau-Levenshtein :

<code class="language-csharp">public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold) {
    int length1 = source.Length;
    int length2 = target.Length;

    if (Math.Abs(length1 - length2) > threshold) { return int.MaxValue; }

    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  1 && j > 1 && source[im2] == target[jm1] && source[im1] == target[j - 2])
                min = Math.Min(min, dMinus2[im2] + cost);
            dCurrent[i] = min;
            if (min  threshold) { return int.MaxValue; }
    }

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

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!