Wie berechnet man die Levenshtein-Entfernung in Java?

1. Einleitung

In diesem Artikel beschreiben wir den Levenshtein-Abstand, der auch als Bearbeitungsabstand bezeichnet wird. Der hier erläuterte Algorithmus wurde 1965 von einem russischen Wissenschaftler, Vladimir Levenshtein, entwickelt.

Wir werden eine iterative und eine rekursive Java-Implementierung dieses Algorithmus bereitstellen.

2. Wie groß ist der Levenshtein-Abstand?

Der Levenshtein-Abstand ist ein Maß für die Unähnlichkeit zwischen zwei Saiten. Bei zwei Strings x und y misst der Abstand mathematisch die minimale Anzahl von Zeichenänderungen, die erforderlich sind, um x in y umzuwandeln .

In der Regel sind drei Arten von Änderungen zulässig:

  1. Einfügen eines Zeichens c
  2. Löschen eines Zeichens c
  3. Ersetzen eines Zeichens c durch c '

Beispiel: Wenn x = 'Schuss' und y = 'Punkt' , beträgt der Bearbeitungsabstand zwischen den beiden 1, da 'Schuss ' durch Ersetzen von ' h ' durch ' p ' in 'Punkt' konvertiert werden kann .

In bestimmten Unterklassen des Problems können die mit jeder Art der Bearbeitung verbundenen Kosten unterschiedlich sein.

Zum Beispiel weniger Kosten für die Ersetzung durch ein Zeichen in der Nähe der Tastatur und ansonsten mehr Kosten. Der Einfachheit halber werden in diesem Artikel alle Kosten als gleich angesehen.

Einige der Anwendungen der Bearbeitungsentfernung sind:

  1. Rechtschreibprüfung - Erkennen von Rechtschreibfehlern im Text und Finden der nächstgelegenen korrekten Rechtschreibung im Wörterbuch
  2. Plagiaterkennung (siehe IEEE-Papier)
  3. DNA-Analyse - Feststellung der Ähnlichkeit zwischen zwei Sequenzen
  4. Spracherkennung (siehe - Microsoft Research)

3. Algorithmusformulierung

Nehmen wir zwei Strings x und y mit den Längen m bzw. n . Wir können jeden String als x [1: m] und y [1: n] bezeichnen.

Wir wissen, dass am Ende der Transformation beide Strings gleich lang sind und an jeder Position übereinstimmende Zeichen haben. Wenn wir also das erste Zeichen jedes Strings betrachten, haben wir drei Möglichkeiten:

  1. Auswechslung:
    1. Bestimmen Sie die Kosten ( D1 ) für das Ersetzen von x [1] durch y [1] . Die Kosten für diesen Schritt wären Null, wenn beide Zeichen gleich sind. Wenn nicht, dann wären die Kosten eins
    2. Nach Schritt 1.1 wissen wir, dass beide Strings mit demselben Zeichen beginnen. Daher wären die Gesamtkosten nun die Summe der Kosten von Schritt 1.1 und der Kosten für die Umwandlung des restlichen Strings x [2: m] in y [2: n].
  2. Einfügen:
    1. Fügen Sie ein Zeichen in x ein , das mit dem ersten Zeichen in y übereinstimmt. Die Kosten für diesen Schritt wären eins
    2. Nach 2.1 haben wir ein Zeichen aus y verarbeitet . Daher wären die Gesamtkosten nun die Summe der Kosten von Schritt 2.1 (dh 1) und der Kosten für die Umwandlung des vollen x [1: m] in das verbleibende y (y [2: n]).
  3. Streichung:
    1. Löschen Sie das erste Zeichen aus x , die Kosten für diesen Schritt wären eins
    2. Nach 3.1 haben wir ein Zeichen von x verarbeitet , aber das volle y muss noch verarbeitet werden. Die Gesamtkosten wären die Summe der Kosten von 3,1 (dh 1) und der Kosten für die Umwandlung des verbleibenden x in das volle y

Der nächste Teil der Lösung besteht darin, herauszufinden, welche Option aus diesen drei ausgewählt werden kann. Da wir nicht wissen, welche Option am Ende zu minimalen Kosten führen würde, müssen wir alle Optionen ausprobieren und die beste auswählen.

4. Naive rekursive Implementierung

Wir können sehen, dass der zweite Schritt jeder Option in Abschnitt 3 größtenteils das gleiche Problem mit der Bearbeitungsentfernung ist, jedoch in Teilzeichenfolgen der ursprünglichen Zeichenfolgen. Dies bedeutet, dass wir nach jeder Iteration das gleiche Problem haben, jedoch kleinere Strings.

Diese Beobachtung ist der Schlüssel zur Formulierung eines rekursiven Algorithmus. Die Wiederholungsbeziehung kann definiert werden als:

D (x [1: m], y [1: n]) = min {

D (x [2: m], y [2: n]) + Kosten für das Ersetzen von x [1] durch y [1],

D (x [1: m], y [2: n]) + 1,

D (x [2: m], y [1: n]) + 1

}}

Wir müssen auch Basisfälle für unseren rekursiven Algorithmus definieren, in unserem Fall, wenn eine oder beide Zeichenfolgen leer werden:

  1. Wenn beide Strings leer sind, ist der Abstand zwischen ihnen Null
  2. Wenn eine der Zeichenfolgen leer ist, entspricht der Bearbeitungsabstand zwischen ihnen der Länge der anderen Zeichenfolge, da wir so viele Einfügungen / Löschungen benötigen, um eine in die andere umzuwandeln:
    • Beispiel: Wenn ein String ist „Hund“ und anderer String ist „“ (leer), müssen wir entweder drei Einfügungen in leeren String zu machen , „Hund“ oder wir brauchen drei Deletionen in „Hund“ entleeren zu machen. Daher beträgt der Bearbeitungsabstand zwischen ihnen 3

Eine naive rekursive Implementierung dieses Algorithmus:

public class EditDistanceRecursive { static int calculate(String x, String y) { if (x.isEmpty()) { return y.length(); } if (y.isEmpty()) { return x.length(); } int substitution = calculate(x.substring(1), y.substring(1)) + costOfSubstitution(x.charAt(0), y.charAt(0)); int insertion = calculate(x, y.substring(1)) + 1; int deletion = calculate(x.substring(1), y) + 1; return min(substitution, insertion, deletion); } public static int costOfSubstitution(char a, char b) { return a == b ? 0 : 1; } public static int min(int... numbers) { return Arrays.stream(numbers) .min().orElse(Integer.MAX_VALUE); } }

Dieser Algorithmus hat die exponentielle Komplexität. Bei jedem Schritt verzweigen wir uns in drei rekursive Aufrufe, um eine O (3 ^ n) -Komplexität aufzubauen.

Im nächsten Abschnitt werden wir sehen, wie wir dies verbessern können.

5. Dynamischer Programmieransatz

Bei der Analyse der rekursiven Aufrufe stellen wir fest, dass die Argumente für Unterprobleme Suffixe der ursprünglichen Zeichenfolgen sind. Dies bedeutet, dass es nur m * n eindeutige rekursive Aufrufe geben kann (wobei m und n eine Anzahl von Suffixen von x und y sind ). Daher sollte die Komplexität der optimalen Lösung quadratisch sein, O (m * n) .

Schauen wir uns einige der Unterprobleme an (gemäß der in Abschnitt 4 definierten Wiederholungsrelation):

  1. Unterprobleme von D (x [1: m], y [1: n]) sind D (x [2: m], y [2: n]), D (x [1: m], y [2 : n]) und D (x [2: m], y [1: n])
  2. Sub-problems of D(x[1:m], y[2:n]) are D(x[2:m], y[3:n]), D(x[1:m], y[3:n]) and D(x[2:m], y[2:n])
  3. Sub-problems of D(x[2:m], y[1:n]) are D(x[3:m], y[2:n]), D(x[2:m], y[2:n]) and D(x[3:m], y[1:n])

In all three cases, one of the sub-problems is D(x[2:m], y[2:n]). Instead of calculating this three times like we do in the naive implementation, we can calculate this once and reuse the result whenever needed again.

This problem has a lot of overlapping sub-problems, but if we know the solution to the sub-problems, we can easily find the answer to the original problem. Therefore, we have both of the properties needed for formulating a dynamic programming solution, i.e., Overlapping Sub-Problems and Optimal Substructure.

We can optimize the naive implementation by introducing memoization, i.e., store the result of the sub-problems in an array and reuse the cached results.

Alternatively, we can also implement this iteratively by using a table based approach:

static int calculate(String x, String y) { int[][] dp = new int[x.length() + 1][y.length() + 1]; for (int i = 0; i <= x.length(); i++) { for (int j = 0; j <= y.length(); j++) { if (i == 0) { dp[i][j] = j; } else if (j == 0) { dp[i][j] = i; } else { dp[i][j] = min(dp[i - 1][j - 1] + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1, dp[i][j - 1] + 1); } } } return dp[x.length()][y.length()]; } 

This algorithm performs significantly better than the recursive implementation. However, it involves significant memory consumption.

This can further be optimized by observing that we only need the value of three adjacent cells in the table to find the value of the current cell.

6. Conclusion

In diesem Artikel haben wir beschrieben, was Levenshtein-Abstand ist und wie er mit einem rekursiven und einem auf dynamischer Programmierung basierenden Ansatz berechnet werden kann.

Der Levenshtein-Abstand ist nur eines der Maßstäbe für die Ähnlichkeit von Strings. Einige der anderen Metriken sind Cosinus-Ähnlichkeit (die einen tokenbasierten Ansatz verwendet und die Strings als Vektoren betrachtet), Würfelkoeffizient usw.

Wie immer finden Sie die vollständige Implementierung der Beispiele auf GitHub.