C) Levenshtein Distanz

Die Levenshtein-Distanz gibt zurück, wie viele Änderungen einer Zeichenkette minimal notwendig sind, um eine andere Zeichenkette zu erhalten. So sind z. B. vier Änderungen notwendig, um aus dem Wort Stefan das Wort Stephanie zu erzeugen (f durch p ersetzen, h dazwischenschieben, i und e hinten dran hängen).

Beim Algorithmus wird eine Matrix in dieser oder einer ähnlichen Form erstellt:

   Stephanie
  0123456789
S 1012345678
t 2101234567
e 3210123456
f 4321123456
a 5432222345
n 6543333234

Dabei wird für jedes Element in jeder Zelle die minimalen Änderungen berechnet, die notwendig sind, um die darüber bzw. danebenstehende Zeichenkette zu erhalten. So lässt sich z. B. ablesen, dass zwei Änderungen nötig sind, um von „Stefan“ auf „Stephan“ zu kommen. Oder keine Änderung von „Ste“ auf „Ste“. Die Zahl unten Rechts (hier die vier) gibt die endgültige Anzahl der nötigen Änderungen an, um aus der einen Zeichenkette die Andere zu bilden. Anhand der Rekursionsgleichung, die den simplen Algorithmus beschreibt, lässt sich der Java-Code ausprogrammieren.

package de.jbb.lev;

public class Levenshtein {

  public int diff(String orig, String eing) {

    int matrix[][] = new int[orig.length() + 1][eing.length() + 1];
    for (int i = 0; i < orig.length() + 1; i++) {
      matrix[i][0] = i;
    }
    for (int i = 0; i < eing.length() + 1; i++) {
      matrix[0][i] = i;
    }
    for (int a = 1; a < orig.length() + 1; a++) {
      for (int b = 1; b < eing.length() + 1; b++) {
        int right = 0;
        if (orig.charAt(a - 1) != eing.charAt(b - 1)) {
          right = 1;
        }
        int mini = matrix[a - 1][b] + 1;
        if (matrix[a][b - 1] + 1 < mini) {
          mini = matrix[a][b - 1] + 1;
        }
        if (matrix[a - 1][b - 1] + right < mini) {
          mini = matrix[a - 1][b - 1] + right;
        }
        matrix[a][b] = mini;
      }
    }
    return matrix[orig.length()][eing.length()];
  }
}

Analyse des Quellcodes

Zeile 7: Initialisierung der Matrix.
Zeile 8 – 13: Füllen der ersten Spalte und der ersten Reihe mit der Anzahl der Buchstaben der jeweiligen Zeichenketten.
Zeile 14 – 31: Iteration über alle Felder der Matrix – ausgenommen den bereits gefüllten Feldern aus Zeile 8 – 13.
Zeile 16 – 19: Initialisierung der Variablen right, die gleich 0 ist, wenn das Zeichen in der aktuellen Spalte mit dem Zeichen in der aktuellen Zeile der Schleife übereinstimmt (also keine Änderung nötig ist). Ansonsten bekommt sie den Wert 1.
Zeile 20 – 26: Überprüft den besten Weg, um eine möglichst niedrige Anzahl an Änderungen zu erreichen. Dieser Wert wird in der Variablen mini gespeichert und anschließend dem aktuellen Element in der Matrix zugewiesen.