Math
Editierdistanz
Berechne die Levenshtein-Tabelle und eine optimale Zeichenkettenausrichtung.
Zum Ausprobieren
Zwei Zeichenketten mit bis zu zehn Zeichen bearbeiten. Die Levenshtein-Tabelle wird Zeile für Zeile gefüllt und verfolgt dann eine optimale Ausrichtung zurück. Einfügungen und Löschungen kosten 1; eine Ersetzung kostet 1 oder 2. Distanz −1 bedeutet, dass die Tabelle unfertig ist.
Gleichungen des Moduls
Gleichungen D(i,0)=i; D(0,j)=j D(i,j)=min(D(i−1,j)+1, D(i,j−1)+1, D(i−1,j−1)+c) c=0 für gleiche Symbole; sonst die Ersetzungskosten Das Zurückverfolgen liefert eine optimale Ausrichtung aus Einfügen/Löschen/Ersetzen
