Bagaimanakah algoritma Levenshtein boleh digunakan untuk mengira jarak edit dan menentukan persamaan antara dua rentetan di Jawa?

Perbandingan Rentetan Kesamaan dalam Java

Apabila membandingkan berbilang rentetan untuk mengenal pasti rentetan yang paling serupa, adalah penting untuk memanfaatkan teknik dan algoritma yang sesuai. Artikel ini menyelidiki pendekatan yang digunakan secara meluas dikenali sebagai "jarak edit" untuk mengira persamaan antara dua rentetan.

Mengira Jarak Edit menggunakan Algoritma Levenshtein

Mengira suntingan jarak melibatkan penentuan bilangan minimum sisipan aksara, pemadaman dan penggantian yang diperlukan untuk mengubah satu rentetan kepada rentetan yang lain. Algoritma Levenshtein ialah pendekatan klasik untuk mengira jarak suntingan, selalunya dimasukkan ke dalam perpustakaan pengaturcaraan. Untuk mengira menggunakan algoritma 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()];
}

Indeks Persamaan Normal

Setelah jarak edit dikira, indeks persamaan boleh dikira dengan menormalkannya kepada panjang daripada rentetan yang lebih panjang:

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

Penggunaan Contoh:

Untuk menggunakan kaedah ini, anda boleh menggunakannya seperti berikut:

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

Output:

Similarity Index: 0.70

Ini contoh menunjukkan indeks persamaan 0.7 antara "Musang cepat melompat" dan "The musang".

Secara keseluruhannya, teknik yang diterangkan dalam artikel ini menyediakan cara yang kukuh untuk mengukur persamaan rentetan, membolehkan perbandingan berbilang rentetan yang cekap dan berkesan.

Atas ialah kandungan terperinci Bagaimanakah algoritma Levenshtein boleh digunakan untuk mengira jarak edit dan menentukan persamaan antara dua rentetan di Jawa?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!