두 현 사이의 Damerau-Levenshtein 거리를 효율적으로 계산하려면 어떻게 해야 합니까?

Damerau-Levenshtein 알고리즘을 사용하여 주어진 문자열의 거리 유사성 계산

문자열 간의 유사성을 확인하는 것은 맞춤법 검사 및 텍스트 비교와 같은 다양한 응용 분야에서 매우 중요합니다. Damerau-Levenshtein 거리는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 횟수(삽입, 삭제, 대체 또는 전치)를 계산하는 효율적인 척도입니다.

다메라우-레벤슈타인 알고리즘 성능 최적화

다메라우-레벤슈타인 거리를 계산할 때 최적의 성능을 얻으려면 다음 핵심 사항을 고려하세요.

• 문자열을 정수 배열로 변환: 정수 배열을 비교하는 것이 문자 배열보다 훨씬 빠릅니다.
• 단락 메커니즘: 현재 거리가 지정된 임계값을 초과하면 계산을 중지합니다.
• 배열 컬렉션 회전: 메모리 오버헤드를 줄이려면 큰 행렬 대신 3개의 배열을 사용하세요.
• 배열 슬라이싱 최적화: 배열이 더 짧은 문자열로 정렬되었는지 확인하세요.

코드 구현

다음 최적화된 C# 코드 조각은 Damerau-Levenshtein 알고리즘을 구현합니다.

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

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