我們如何優化用於字串相似度比較的 Damerau-Levenshtein 演算法？

基於距離相似度量的字串比較

引言:

在計算語言學和自然語言處理中，確定兩個字串之間的相似性對於各種應用至關重要。一種廣泛使用的度量方法是距離相似度度量，它量化將一個字串轉換為另一個字串所需的修改次數。本文旨在全面介紹如何計算兩個給定字串之間的距離相似度度量，重點在於效能最佳化。

Damerau-Levenshtein演算法:

Damerau-Levenshtein演算法是一種廣泛採用的技術，用於計算兩個字串之間的距離相似度量。它考慮以下操作：插入、刪除、替換和轉置。該演算法計算將一個字串轉換為另一個字串所需的這些操作的最小數量。例如，「hospital」和「haspita」之間的Damerau-Levenshtein距離為2（一次替換和一次轉置）。

性能考量:

對於對效能敏感的應用程序，最佳化Damerau-Levenshtein演算法的實作至關重要。以下是一些關鍵考慮因素：

• 將字串表示為整數數組： 將字串轉換為代碼點數組（表示每個字元的整數）允許進行更快的比較操作。
• 短路機制： 實現一種當距離超過預定義閾值時就停止的機制可以顯著提高性能。
• 旋轉數組： 使用一組旋轉數組而不是大型矩陣可以減少記憶體消耗並提高快取效率。

程式碼實作:

以下程式碼提供了Damerau-Levenshtein演算法在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;
}

此實作遵循前面概述的效能增強考慮因素。透過將字串表示為整數數組並使用旋轉數組，它大大加快了計算過程。

以上是我們如何優化用於字串相似度比較的 Damerau-Levenshtein 演算法？的詳細內容。更多資訊請關注PHP中文網其他相關文章！