Levenshtein-Distanz

aus GlossarWiki, der Glossar-Datenbank der Fachhochschule Augsburg
Wechseln zu:Navigation, Suche

1 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.

2 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.

3 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.