Levenshtein-Algorithmus

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