두 현 사이의 Damerau-Levenshtein 거리를 어떻게 효율적으로 계산할 수 있습니까?

문자열 거리 유사도를 효율적으로 계산

맞춤법 검사 및 텍스트 분석과 같은 응용 프로그램에서는 두 문자열 간의 거리 유사성을 계산해야 하는 경우가 많습니다. Damerau-Levenshtein 알고리즘은 한 문자열을 다른 문자열로 변환하는 데 필요한 수정 횟수를 측정하는 데 일반적으로 사용되는 방법입니다.

고성능 코드 구현

성능 최적화를 위해 향상된 Damerau-Levenshtein 알고리즘 구현을 채택했습니다. 여기에는 다음과 같은 성능 향상 기술이 포함되어 있습니다.

1. 비교 속도를 높이려면 문자열을 코드 포인트 배열로 변환하세요.
2. 단락 메커니즘을 사용하여 거리가 지정된 임계값을 초과하면 계산이 종료됩니다.
3. 행렬 대신 3개의 회전된 배열을 사용하여 짧은 문자열에 대한 배열 슬라이싱 작업을 최적화합니다.

샘플 코드

다음 코드는 기존 구현보다 훨씬 빠르게 수행되는 향상된 Damerau-Levenshtein 알고리즘을 보여줍니다.

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

성능 고려 사항

위 코드에 구현된 성능 향상으로 인해 속도가 크게 향상되었습니다.

• Wikipedia의 C# 예제보다 약 10배 빠릅니다(최대 거리 제한이 없더라도).
• 최대 거리를 제공할 경우 성능 이점은 30배에서 100배까지 증가할 수 있습니다.

위 내용은 두 현 사이의 Damerau-Levenshtein 거리를 어떻게 효율적으로 계산할 수 있습니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!