1. Was versteht man unter
'Levenshtein'?
Levenshtein ist der russische Wissenschaftler, von dem der Algorithmus
zur Berechnung der sogenannten "Edit-Distanz" entwickelt wurde.
Mathematisch gesehen handelt es sich hierbei um eine Metrik im Raum der
Zeichenketten, die den Abstand zweier Zeichenketten zueinander
bestimmt. Dabei wird die minimale Anzahl Editier-Operationen ermittelt,
die nötig ist, um eine Zeichenkette in
eine andere schrittweise zu transformieren. Solche Editier-Operationen
können z.B. "Einfügen",
"Löschen" oder "Ersetzen" von
Buchstaben sein. Diese Operationen sind offensichtlich symmetrisch und
erfllen die Dreiecks-Ungleichung. |
|
|
