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.

Levenshtein

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.

5 Replies to “C) Levenshtein Distanz”

  1. dennis

    Zeile 24 enthält einen Syntaxfehler: ein überflüssiges Semikolon hinter dem Vergleichsoperator <

  2. Stefan Kiesel

    Hallo,

    vielen Dank für den Hinweis. Da muss sich bei der letzten Verbesserung ein kleiner Fehler eingeschlichen haben. Ich habe den Code ausgebessert.

    Grüße
    Stefan

Schreibe einen Kommentar

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.