10.2.3 Levenshtein-Matrizen

Wenn man in einem Smartphone Sprache mit Hilfe der Tastatur eingibt, dann ist es heute üblich, dass die Tastatur Wortvorschläge macht, welche Wörter als nächstes im Satz vorkommen. Die Tastatur-App versucht vorherzusagen, was der Mensch schreiben wird.

Damit solche Vorhersagen möglich sind, muss ein Computer in der Lage sein, Beziehungen zwischen Wörtern zu berechnen.

Ein historisch früher Ansatz solche Wortähnlichkeiten mit einer Zahl auszudrücken ist die "Levenshtein-Distanz". Wladimir Levenshtein hat die Idee der "Levenshtein-Distanz" 1965 in einem Artikel ertmals formuliert.

Mit Hilfe eines geeigneten Algorithmus wird zu zwei gegebenen Wörtern die Levenshtein-Distanz ermittelt:

Übung

• Öffne folgende App in einem neuen Fenster: Levenshtein-Matrizen.

• Tippe unterschiedliche Wörter ein, ermittle die Levenshtein-Distanz und überlege was die Levenshtein-Distanz anschaulich bedeutet.

Übung

• Öffne folgende App in einem neuen Fenster: Anwendung der Levenshtein-Matrizen.

• Tippe eigenen Text ein und überlege, wie sinnvoll die Levenshtein-Distanz in einer Tastatur-App Wortvorschläge machen könnte.