Levenshtein-Distanz

Definition

Die Levenshtein-Distanz dient der Berechnung von Wortähnlichkeiten, welche beispielsweise bei der unschaften Fuzzy-Suche verwendet wird. Die Berechnung erfolgt durch Zählen der Schritte, die nötig sind, um eine Zeichenkette durch Einfügen, Löschen und Ersetzen von Zeichen in eine andere Zeichenkette zu überführen.

Beispiel

Um von dem Begriff „Auto“ zu dem Begriff „aus“ zu kommen sind zwei Schritte nötig:
0. Auto
1. Auso (Ersetzen von „t“ durch „s“)
2. Aus (Löschen von „o“ )
Die Levenshtein-Distanz betägt zwei, da zwei Umwandlungsschritte benötigt werden.

Literatur

Michael, Jörg - Doppelgänger gesucht Ein Programm für die kontextsensitive phonetische Textumwandlung, erschienen in C’T vom 25/99 S. 252

Dieser Artikel ist GlossarWiki-konform.

In diesem Artikel sollten die Quellenangaben überarbeitet werden.
Bitte die Regeln der GlossarWiki-Quellenformatierung beachten.