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

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

Jan 15, 2025 am 09:39 AM

How Can I Efficiently Calculate the Damerau-Levenshtein Distance Between Two Strings?

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.

뜨거운 기사 태그

메모장++7.3.1

메모장++7.3.1

사용하기 쉬운 무료 코드 편집기

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

드림위버 CS6

드림위버 CS6

시각적 웹 개발 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

C 언어 함수에 의해 반환 된 값 유형은 무엇입니까? 반환 값을 결정하는 것은 무엇입니까? C 언어 함수에 의해 반환 된 값 유형은 무엇입니까? 반환 값을 결정하는 것은 무엇입니까? Mar 03, 2025 pm 05:52 PM

C 언어 함수에 의해 반환 된 값 유형은 무엇입니까? 반환 값을 결정하는 것은 무엇입니까?

C 언어 함수 형식 문자 케이스 변환 단계 C 언어 함수 형식 문자 케이스 변환 단계 Mar 03, 2025 pm 05:53 PM

C 언어 함수 형식 문자 케이스 변환 단계

Gulc : C 도서관은 처음부터 구축되었습니다 Gulc : C 도서관은 처음부터 구축되었습니다 Mar 03, 2025 pm 05:46 PM

Gulc : C 도서관은 처음부터 구축되었습니다

C 언어 기능의 정의 및 호출 규칙은 무엇이며 C 언어 기능의 정의 및 호출 규칙은 무엇이며 Mar 03, 2025 pm 05:53 PM

C 언어 기능의 정의 및 호출 규칙은 무엇이며

뚜렷한 사용 및 문구 공유 뚜렷한 사용 및 문구 공유 Mar 03, 2025 pm 05:51 PM

뚜렷한 사용 및 문구 공유

C 표준 템플릿 라이브러리 (STL)는 어떻게 작동합니까? C 표준 템플릿 라이브러리 (STL)는 어떻게 작동합니까? Mar 12, 2025 pm 04:50 PM

C 표준 템플릿 라이브러리 (STL)는 어떻게 작동합니까?

메모리에 저장된 C 언어 함수의 반환 값은 어디에 있습니까? 메모리에 저장된 C 언어 함수의 반환 값은 어디에 있습니까? Mar 03, 2025 pm 05:51 PM

메모리에 저장된 C 언어 함수의 반환 값은 어디에 있습니까?

STL (정렬, 찾기, 변환 등)의 알고리즘을 효율적으로 사용하려면 어떻게합니까? STL (정렬, 찾기, 변환 등)의 알고리즘을 효율적으로 사용하려면 어떻게합니까? Mar 12, 2025 pm 04:52 PM

STL (정렬, 찾기, 변환 등)의 알고리즘을 효율적으로 사용하려면 어떻게합니까?

See all articles