Die Levenshtein-Distanz

Beim Suchen nach bestimmten String-Funktionen in PHP bin ich auf eine Funktion gestossen, welche die Levenshtein-Distanz zwischen zwei Strings berechnen will. Von der Neugierde gepackt habe ich mich kurz informiert: http://de.wikipedia.org/wiki/Levenshtein-Distanz

Es geht also um die Anzahl Schritte, die man machen muss, um vom einen Wort zum anderen zu kommen. Das Beispiel aus der Wikipedia:

Um beispielsweise von „Tier“ zu „Tor“ zu kommen ist eine Ersetzung und eine Löschung notwendig, die Levenshtein-Distanz beträgt also 2:
1. Tier
2. Toer (Ersetze i durch o)
3. Tor (Lösche e)

Das kann sehr nützlich sein, um die Ähnlichkeit von Wörtern zu berechnen. Wäre sicher einmal interessant, die Funktion über ein Wörterbuch laufen zu lassen.

Ich kann mir vorstellen, dass Google ähnliche Algorithmen verwendet, um beispielsweise die Verbesserungsvorschläge bei fehlerhaft eingegebenen Begriffen zu erhalten.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.