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

高效計算字串距離相似度

在拼字檢查和文字分析等應用程式中，經常需要計算兩個字串之間的距離相似度。 Damerau-Levenshtein演算法是一種常用的方法，它衡量將一個字串轉換為另一個字串所需的修改次數。

高效能程式碼實作

為了最佳化效能，我們採用了一種改良的Damerau-Levenshtein演算法實作。它包含以下幾種效能增強技術：

1. 將字串轉換為代碼點數組以加快比較速度。
2. 利用短路機制，如果距離超過指定閾值則終止計算。
3. 使用三個旋轉數組代替矩陣，優化短字串的陣列切片運算。

範例程式碼

以下程式碼展示了改進後的Damerau-Levenshtein演算法，其執行速度比現有實作快得多：

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

性能考量

上述程式碼中實現的效能增強帶來了顯著的速度提升：

• 比維基百科上的C#範例快約10倍（即使沒有最大距離限制）。
• 當提供最大距離時，效能優勢可提升到30倍到100倍。

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