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

Damerau-Levenshtein アルゴリズムを使用して、指定された文字列の距離類似性を計算します

文字列間の類似性を判断することは、スペルチェックやテキスト比較などのさまざまなアプリケーションにおいて重要です。ダメラウ・レーベンシュタイン距離は、ある文字列を別の文字列に変換するために必要な編集 (挿入、削除、置換、または転置) の最小回数を計算する効率的な尺度です。

Damerau-Levenshtein アルゴリズムのパフォーマンスの最適化

ダメラウ・レーベンシュタイン距離を計算する際に最適なパフォーマンスを得るには、次の重要な点を考慮してください:

• 文字列を整数の配列に変換します: 整数の配列の比較は、文字配列よりもはるかに高速です。
• 短絡メカニズム: 現在の距離が指定されたしきい値を超える場合、計算を停止します。
• 配列のコレクションを回転します: メモリのオーバーヘッドを減らすために、大きな行列の代わりに 3 つの配列を使用します。
• 配列のスライスを最適化します: 配列が短い文字列に揃えられていることを確認します。

コードの実装

次の最適化された C# コード スニペットは、Damerau-Levenshtein アルゴリズムを実装しています。

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

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