Heim >Java >javaLernprogramm >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!