Levenshtein-Algorithmus

Levenshtein Algorithmus

Copyright © Shutterstock/whiteMocca

Was ist der Levenshtein-Algorithmus?

In der Informationstheorie, Linguistik und Informatik ist der Levenshtein-Algorithmus oder die Levenshtein-Distanz eine String-Metrik zur Messung der Differenz zwischen zwei Sequenzen. Informell ist der Levenshtein-Algorithmus zwischen zwei W√∂rtern die minimale Anzahl von Ein-Zeichen-Bearbeitungen (Einf√ľgungen, L√∂schungen oder Ersetzungen), die erforderlich sind, um ein Wort in das andere zu √§ndern. Der Algorithmus ist nach dem sowjetischen Mathematiker Vladimir Levenshtein benannt, der diese Entfernung 1965 in Betracht zog.

Die Grenzen

Der Levenshtein-Algorithmus besitzt mehrere obere und untere Grenzen:

  • Es besteht mindestens der Gr√∂√üenunterschied zwischen den beiden Strings.
  • Die maximale L√§nge ist die des l√§ngeren Strings.
  • Das Ergebnis betr√§gt nur 0 wenn die beiden Strings gleich sind.
  • Wenn die Strings die gleiche Gr√∂√üe haben, ist die Hamming-Distanz eine obere Grenze f√ľr die Levenshtein-Distanz.
  • Die Levenshtein-Distanz zwischen zwei Strings ist nicht gr√∂√üer als die Summe ihrer Levenshtein-Abst√§nde von einer dritten Strings (Dreiecksungleichung).

Anwendungen

Bei der ann√§hernden Zeichenfolgen√ľbereinstimmung besteht das Ziel darin, √úbereinstimmungen f√ľr kurze Zeichenfolgen in vielen l√§ngeren Texten zu finden, in Situationen, in denen eine kleine Anzahl von Unterschieden zu erwarten ist. Hier ist eine der Strings typischerweise kurz, w√§hrend die andere beliebig lang ist. Dies hat eine breite Palette von Anwendungen, zum Beispiel Rechtschreibpr√ľfung, Korrektursysteme f√ľr die optische Zeichenerkennung und Software zur Unterst√ľtzung der √úbersetzung nat√ľrlicher Sprache basierend auf Translation Memory.

Man kann die Levenshtein-Distanz auch zwischen zwei l√§ngeren Strings berechnen, aber die Kosten, um sie zu berechnen, was grob proportional zu dem Produkt der zwei Stringl√§ngen ist, macht dies unpraktisch. Wenn sie verwendet werden, um bei der Suche nach unscharfen Zeichenfolgen in Anwendungen, wie zum Beispiel einer Datensatzverkn√ľpfung, zu helfen, sind die verglichenen Zeichenfolgen normalerweise kurz, um die Geschwindigkeit der Vergleiche zu verbessern.

Beispiel Levenshtein-Algorithmus

Beispiel zum Levenshtein-Algorithmus / Screenshot levenshtein.de/

 


Sie haben noch Fragen?

Kontaktieren Sie uns

Kostenloser SEO-Check der OSG


Weitere Inhalte