文字列の類似性比較のために、Damerau-Levenshtein アルゴリズムを最適化するにはどうすればよいでしょうか?

距離類似性尺度に基づく文字列比較

紹介:

計算言語学と自然言語処理では、2 つの文字列間の類似性を判断することがさまざまなアプリケーションにとって重要です。広く使用されているメトリックの 1 つは距離類似性メトリックです。これは、ある文字列を別の文字列に変換するために必要な変更の数を定量化します。この記事は、パフォーマンスの最適化に焦点を当てて、指定された 2 つの文字列間の距離類似性尺度を計算するための包括的な概要を提供することを目的としています。

ダメラウ・レーベンシュタインアルゴリズム:

Damerau-Levenshtein アルゴリズムは、2 つの文字列間の距離類似度を計算するために広く採用されている手法です。挿入、削除、置換、転置といった操作が考慮されます。このアルゴリズムは、ある文字列を別の文字列に変換するために必要なこれらの操作の最小数を計算します。たとえば、「病院」と「ハスピタ」の間のダメラウ・レーベンシュタイン距離は 2 (置換 1 つと転置 1 つ) です。

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

パフォーマンス重視のアプリケーションの場合、Damerau-Levenshtein アルゴリズムの実装を最適化することが重要です。以下に重要な考慮事項をいくつか示します:

• 文字列を整数の配列として表現します: 文字列をコード ポイントの配列 (各文字を表す整数) に変換すると、比較演算を高速化できます。
• 短絡メカニズム: 距離が事前定義されたしきい値を超えたときに停止するメカニズムを実装すると、パフォーマンスが大幅に向上します。
• 回転配列: 大きな行列の代わりに一連の回転配列を使用すると、メモリ消費を削減し、キャッシュ効率を向上させることができます。

コードの実装:

次のコードは、C# での Damerau-Levenshtein アルゴリズムの最適化された実装を提供します。

<code class="language-c#">public static int DamerauLevenshteinDistance(int[] source, int[] target, int threshold)
{
    if (Math.Abs(source.Length - target.Length) > threshold) return int.MaxValue;
    if (source.Length > target.Length) Swap(ref target, ref source);
    int maxi = source.Length;
    int maxj = target.Length;
    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;
    for (int j = 1; j <= maxj; j++)
    {
        dMinus2 = dMinus1;
        dMinus1 = dCurrent;
        dCurrent = new int[maxi + 1];
        dCurrent[0] = j;
        for (int i = 1; i <= maxi; i++)
        {
            int cost = (source[i - 1] == target[j - 1]) ? 0 : 1;
            int del = dMinus1[i] + 1;
            int ins = dCurrent[i - 1] + 1;
            int sub = dMinus1[i - 1] + cost;
            int min = (del < ins) ? (del < sub ? del : sub) : (ins < sub ? ins : sub);
            if (i > 1 && j > 1 && source[i - 2] == target[j - 1] && source[i - 1] == target[j - 2])
                min = Math.Min(min, dMinus2[i - 2] + cost);
            dCurrent[i] = min;
            if (min > threshold) return int.MaxValue;
        }
    }
    return (dCurrent[maxi] > threshold) ? int.MaxValue : dCurrent[maxi];
}

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

この実装は、以前に概説したパフォーマンス向上に関する考慮事項に従います。文字列を整数の配列として表し、回転された配列を使用することにより、計算プロセスが大幅に高速化されます。

以上が文字列の類似性比較のために、Damerau-Levenshtein アルゴリズムを最適化するにはどうすればよいでしょうか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。