6/05: 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.

IT allgemein

Keine Kommentare »

Noch keine Kommentare

Hinterlasse einen Kommentar

Line and paragraph breaks automatic, e-mail address never displayed, HTML allowed: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

(req)

(req, never shown)

Note: Spam control is in use - if this is your first comment, it will be automatically sent for moderation. Other moderation is carried out on a per-post basis.