Levenshtein 알고리즘을 사용하여 편집 거리를 계산하고 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);

출력:

Similarity Index: 0.70

이 예는 "The Quick fox Jumped"와 "The fox" 사이의 유사성 지수 0.7을 보여줍니다.

전체적으로, 이 문서는 문자열 유사성을 정량화하는 강력한 방법을 제공하므로 여러 문자열을 효율적이고 효과적으로 비교할 수 있습니다.

위 내용은 Levenshtein 알고리즘을 사용하여 편집 거리를 계산하고 Java에서 두 문자열 간의 유사성을 결정하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!