2 つの弦間のダメラウ・レーベンシュタイン距離を効率的に計算するにはどうすればよいでしょうか?

文字列の距離の類似性を効率的に計算します

スペルチェックやテキスト分析などのアプリケーションでは、多くの場合、2 つの文字列間の距離の類似性を計算する必要があります。 Damerau-Levenshtein アルゴリズムは、ある文字列を別の文字列に変換するために必要な変更の数を測定する、一般的に使用される方法です。

高性能コードの実装

パフォーマンスを最適化するために、改良されたDamerau-Levenshteinアルゴリズムの実装を採用しています。これには、次のパフォーマンス向上テクノロジーが含まれています:

1. 比較を高速化するために文字列をコード ポイントの配列に変換します。
2. 短絡メカニズムを使用すると、距離が指定されたしきい値を超えると計算が終了します。
3. 行列の代わりに 3 つの回転配列を使用して、短い文字列の配列スライス操作を最適化します。

サンプルコード

次のコードは、既存の実装よりもはるかに高速に実行される、改良されたダメラウ・レーベンシュタイン アルゴリズムを示しています。

<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>

パフォーマンスに関する考慮事項

上記のコードに実装されたパフォーマンスの強化により、速度が大幅に向上します。

Wikipedia の C# の例より約 10 倍高速です (最大距離制限がない場合でも)。
最大距離を提供する場合、パフォーマンスの利点は 30 倍から 100 倍に増加する可能性があります。

以上が2 つの弦間のダメラウ・レーベンシュタイン距離を効率的に計算するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。