Description: Alles rund um den Levenshtein-Algorithmus zur fehlertoleranten Suche. Webseite zeigt effiziente Implemtierungen.
internet (23755) datenbank (930) suche (648) algorithmus (39) fuzzy (39) online demo (13) soundex (7) levenshtein (3) fehlertolerant (2) approximativ (2)
Der Levenshtein-Algorithmus (auch Edit-Distanz genannt) errechnet die Mindestanzahl von Editierungsoperationen, die notwendig sind, um eine bestimmte Zeichenkette soweit abzuändern, um eine andere bestimmte Zeichenkette zu erhalten. Die wohl bekannteste Weise die Edit-Distanz zu berechnen erfolgt durch den sogenannten Dynamic-Programming-Ansatz. Dabei wird eine Matrix initialisiert, die für jede (m, N)-Zelle die Levenshtein-Distanz (levenshtein distance) zwischen dem m-Buchstabenpräfix des einen Wortes und
"=" Übereinstimmung; "o" Ersetzen; "+" Einfügen; "-" Löschen
Obwohl ausgeklügelte Verbesserungen bezglich der Berechnung grosser Matrizen gemacht wurden, gibt es keine Alternative zu dem meist recht großen Berechnungsaufwand. Nachdem Kenntnisstand der Autoren gelanges bisher nur der Firma Exorbyte den Levensthein Algorithmus in höchster Geschwindigkeit zu implementieren .