Levenshtein 알고리즘을 사용하여 편집 거리를 계산하고 Java에서 두 문자열 간의 유사성을 결정하는 방법은 무엇입니까?-java지도 시간-php.cn

Levenshtein 알고리즘을 사용하여 편집 거리를 계산하고 Java에서 두 문자열 간의 유사성을 결정하는 방법은 무엇입니까?

DDD

풀어 주다： 2024-11-18 06:28:02

원래의

503명이 탐색했습니다.

How can the Levenshtein algorithm be used to calculate edit distance and determine the similarity between two strings in Java?

Java의 유사성 문자열 비교

여러 문자열을 비교하여 가장 유사한 문자열을 식별할 때는 적절한 기술과 알고리즘을 활용하는 것이 중요합니다. 이 기사에서는 두 문자열 간의 유사성을 계산하기 위해 "편집 거리"라고 알려진 널리 사용되는 접근 방식을 자세히 설명합니다.

Levenshtein 알고리즘을 사용하여 편집 거리 계산

편집 계산 거리는 한 문자열을 다른 문자열로 변환하는 데 필요한 최소 문자 삽입, 삭제 및 대체 수를 결정하는 것과 관련됩니다. Levenshtein 알고리즘은 편집 거리를 계산하기 위한 고전적인 접근 방식으로, 종종 프로그래밍 라이브러리에 통합됩니다. Levenshtein 알고리즘을 사용하여 계산하려면:

// Levenshtein's Edit Distance Function
public static int editDistance(String s1, String s2) {
    // Convert to lower case for case-insensitive comparison
    s1 = s1.toLowerCase();
    s2 = s2.toLowerCase();

    int[][] matrix = new int[s2.length() + 1][s1.length() + 1];

    // Initialize first column to cost of insertion
    for (int i = 0; i <= s1.length(); i++) {
        matrix[0][i] = i;
    }

    // Initialize first row to cost of deletion
    for (int j = 0; j <= s2.length(); j++) {
        matrix[j][0] = j;
    }

    // Populate the matrix
    for (int j = 1; j <= s2.length(); j++) {
        for (int i = 1; i <= s1.length(); i++) {
            int cost = s1.charAt(i - 1) == s2.charAt(j - 1) ? 0 : 1;
            int min = Math.min(matrix[j - 1][i] + 1, // Deletion
                    Math.min(matrix[j][i - 1] + 1, // Insertion
                            matrix[j - 1][i - 1] + cost)); // Substitution
            matrix[j][i] = min;
        }
    }

    return matrix[s2.length()][s1.length()];
}

로그인 후 복사

정규화된 유사성 지수

편집 거리가 계산되면 유사성 지수는 이를 길이로 정규화하여 계산할 수 있습니다. 긴 문자열:

// Similarity Index Function
public static double similarityIndex(String s1, String s2) {
    int distance = editDistance(s1, s2);
    String longer = s1.length() > s2.length() ? s1 : s2;
    double similarity = 1.0 - (distance / (double) longer.length());
    return similarity;
}

로그인 후 복사

사용 예:

이러한 방법을 활용하려면 다음과 같이 적용할 수 있습니다.

String str1 = "The quick fox jumped";
String str2 = "The fox";
double similarity = similarityIndex(str1, str2);
System.out.println("Similarity Index: " + similarity);

로그인 후 복사

출력: