如何有效計算兩個字串之間的 Damerau-Levenshtein 距離？

利用Damerau-Levenshtein演算法計算給定字串的距離相似度

在拼字檢查和文字比較等多種應用中，確定字串之間的相似度至關重要。 Damerau-Levenshtein距離是一種有效的度量方法，它計算將字串轉換為另一個字串所需的最小編輯次數（插入、刪除、替換或轉置）。

Damerau-Levenshtein演算法的效能最佳化

為了在計算Damerau-Levenshtein距離時獲得最佳效能，請考慮以下關鍵點：

• 將字串轉換為整數陣列： 與字元相比，比較整數陣列的速度要快得多。
• 短路機制： 如果目前距離超過指定閾值，則停止計算。
• 旋轉陣列集合： 使用三個陣列而不是大型矩陣來減少記憶體開銷。
• 最佳化陣列切片： 確保陣列與較短的字串對齊。

程式碼實作

以下優化的C#程式碼片段實作了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>

以上是如何有效計算兩個字串之間的 Damerau-Levenshtein 距離？的詳細內容。更多資訊請關注PHP中文網其他相關文章！