Wie berechnet man die String-Ähnlichkeit in Java mithilfe der Levenshtein-Distanz?

Ähnlichkeitszeichenfolgenvergleich in Java

Verstehen der Notwendigkeit von Ähnlichkeitsmaßen

Beim Arbeiten mit Bei Textdaten ist es von entscheidender Bedeutung, die Ähnlichkeit zwischen Zeichenfolgen zu beurteilen. Dies kann sich bei Aufgaben wie der Identifizierung doppelter Inhalte, der Suche nach den ähnlichsten Suchergebnissen oder sogar der Extraktion aussagekräftiger Informationen aus Texten als nützlich erweisen. Glücklicherweise gibt es in Java effiziente und gut etablierte Methoden zur Berechnung der String-Ähnlichkeit.

Einführung in die Ähnlichkeitsfunktion

Der gebräuchlichste Ansatz zum String-Vergleich ist die Berechnung eines Ähnlichkeitsindex, der den Grad der Ähnlichkeit zwischen zwei Zeichenfolgen quantifiziert. Ein weit verbreitetes Ähnlichkeitsmaß ist der Levenshtein-Abstand, der die Mindestanzahl an Bearbeitungen (Einfügungen, Löschungen oder Ersetzungen) berechnet, die erforderlich sind, um eine Zeichenfolge in die andere umzuwandeln. Diese Distanzmetrik wird normalerweise auf einen Bereich zwischen 0 und 1 normalisiert, wobei ein höherer Wert eine größere Ähnlichkeit anzeigt.

Implementierung der Levenshtein-Distanz

Eine Möglichkeit, die Levenshtein-Distanz zu berechnen Die Entfernung erfolgt mithilfe der Methode **String.getLevenshteinDistance()**, die von der **Apache Commons Text**-Bibliothek bereitgestellt wird, die den Standard implementiert Levenshtein-Algorithmus. Alternativ können Sie den Algorithmus auch manuell implementieren, wie im folgenden Code gezeigt:

public static int editDistance(String s1, String s2) {
  int n = s1.length() + 1;
  int m = s2.length() + 1;
  int[][] matrix = new int[n][m];

  for (int i = 0; i < n; i++) {
    matrix[i][0] = i;
  }

  for (int j = 0; j < m; j++) {
    matrix[0][j] = j;
  }

  for (int i = 1; i < n; i++) {
    for (int j = 1; j < m; j++) {
      int cost = (s1.charAt(i - 1) == s2.charAt(j - 1)) ? 0 : 1;
      matrix[i][j] = Math.min(
        matrix[i - 1][j] + 1, // deletion
        Math.min(
          matrix[i][j - 1] + 1, // insertion
          matrix[i - 1][j - 1] + cost // substitution
        )
      );
    }
  }

  return matrix[n - 1][m - 1];
}

Berechnung des Ähnlichkeitsindex

Sobald die Levenshtein-Distanz berechnet ist, wird die Ähnlichkeit berechnet Der Index kann durch Normalisierung auf die Länge des längeren erhalten werden string:

public static double similarity(String s1, String s2) {
  double longerLength = Math.max(s1.length(), s2.length());
  return 1.0 - (editDistance(s1, s2) / longerLength);
}

Fazit

Durch die Implementierung der Levenshtein-Distanz und der Ähnlichkeitsfunktion in Java erhalten Sie ein leistungsstarkes Werkzeug zur Bewertung der Ähnlichkeit zwischen Strings. Diese Technik findet zahlreiche Anwendungen in der Verarbeitung natürlicher Sprache, der Datenanalyse und anderen Bereichen, in denen der Vergleich von Textinhalten unerlässlich ist.

Das obige ist der detaillierte Inhalt vonWie berechnet man die String-Ähnlichkeit in Java mithilfe der Levenshtein-Distanz?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!