Wie kann der Levenshtein-Algorithmus verwendet werden, um den Bearbeitungsabstand zu berechnen und die Ähnlichkeit zwischen zwei Zeichenfolgen in Java zu bestimmen?

Ähnlichkeits-String-Vergleich in Java

Beim Vergleich mehrerer Strings, um die ähnlichsten zu identifizieren, ist es wichtig, geeignete Techniken und Algorithmen zu nutzen. Dieser Artikel befasst sich mit einem weit verbreiteten Ansatz, der als „Bearbeitungsdistanz“ bekannt ist, um die Ähnlichkeit zwischen zwei Zeichenfolgen zu berechnen.

Berechnung der Bearbeitungsentfernung mit dem Levenshtein-Algorithmus

Berechnung der Bearbeitung Bei der Entfernung geht es darum, die Mindestanzahl von Zeicheneinfügungen, -löschungen und -ersetzungen zu bestimmen, die erforderlich sind, um eine Zeichenfolge in eine andere umzuwandeln. Der Levenshtein-Algorithmus ist ein klassischer Ansatz zur Berechnung der Bearbeitungsentfernung, der häufig in Programmierbibliotheken integriert ist. So berechnen Sie mit dem Levenshtein-Algorithmus:

// 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()];
}

Normalisierter Ähnlichkeitsindex

Sobald der Bearbeitungsabstand berechnet ist, kann der Ähnlichkeitsindex durch Normalisierung auf die Länge berechnet werden der längeren Zeichenfolge:

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

Verwendungsbeispiel:

Um diese Methoden zu nutzen, können Sie sie wie folgt anwenden:

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

Ausgabe:

Similarity Index: 0.70

Dieses Beispiel zeigt einen Ähnlichkeitsindex von 0,7 zwischen „Der schnelle Fuchs sprang“ und „Der Fuchs“.

Insgesamt sind die in beschrieben Dieser Artikel bietet eine robuste Möglichkeit zur Quantifizierung der String-Ähnlichkeit und ermöglicht einen effizienten und effektiven Vergleich mehrerer Strings.

Das obige ist der detaillierte Inhalt vonWie kann der Levenshtein-Algorithmus verwendet werden, um den Bearbeitungsabstand zu berechnen und die Ähnlichkeit zwischen zwei Zeichenfolgen in Java zu bestimmen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!