Java で編集距離を計算し、2 つの文字列間の類似性を判断するために、レーベンシュタイン アルゴリズムをどのように使用できますか?

Java での類似文字列比較

複数の文字列を比較して最も類似した文字列を特定する場合、適切な技術とアルゴリズムを活用することが不可欠です。この記事では、2 つの文字列間の類似性を計算するために「編集距離」として知られる広く使用されているアプローチについて詳しく説明します。

レーベンシュタイン アルゴリズムを使用した編集距離の計算

編集の計算距離には、ある文字列を別の文字列に変換するために必要な文字の挿入、削除、置換の最小数を決定することが含まれます。レーベンシュタイン アルゴリズムは、編集距離を計算するための古典的なアプローチであり、プログラミング ライブラリに組み込まれることがよくあります。レーベンシュタイン アルゴリズムを使用して計算するには:

// 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

This例では、「The Quick fox Jumped」と「The Quick fox Jumped」の間の類似性指数 0.7 を示しています。 fox".

全体として、この記事で説明する手法は、文字列の類似性を定量化するための堅牢な方法を提供し、複数の文字列の効率的かつ効果的な比較を可能にします。

以上がJava で編集距離を計算し、2 つの文字列間の類似性を判断するために、レーベンシュタイン アルゴリズムをどのように使用できますか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。