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

Calculer efficacement la similarité de distance entre les cordes

Dans des applications telles que la vérification orthographique et l'analyse de texte, il est souvent nécessaire de calculer la similarité de distance entre deux chaînes. L'algorithme de Damerau-Levenshtein est une méthode couramment utilisée qui mesure le nombre de modifications nécessaires pour transformer une chaîne en une autre.

Implémentation de code haute performance

Afin d'optimiser les performances, nous adoptons une implémentation améliorée de l'algorithme Damerau-Levenshtein. Il contient les technologies d'amélioration des performances suivantes :

1. Convertissez les chaînes en tableaux de points de code pour accélérer les comparaisons.
2. Grâce au mécanisme de court-circuit, le calcul sera terminé si la distance dépasse le seuil spécifié.
3. Utilisez trois tableaux pivotés au lieu de matrices pour optimiser les opérations de découpage de tableaux pour les chaînes courtes.

Exemple de code

Le code suivant démontre un algorithme de Damerau-Levenshtein amélioré qui fonctionne beaucoup plus rapidement que les implémentations existantes :

<code class="language-c#">public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold)
{
    // ... 代码略 ...

    //// 旋转数组
    dSwap = dMinus2;
    dMinus2 = dMinus1;
    dMinus1 = dCurrent;
    dCurrent = dSwap;

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

    for (int j = 1; j  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>

Considérations relatives aux performances

Les améliorations de performances implémentées dans le code ci-dessus entraînent des améliorations significatives de la vitesse :

• Environ 10 fois plus rapide que l'exemple C# sur Wikipédia (même sans la limite de distance maximale).
• En fournissant la distance maximale, l'avantage de performance peut être augmenté de 30 à 100 fois.

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!