Levenshtein-Algorithmus – Definition, Funktionsweise und Einsatz im Onlinemarketing

Der Levenshtein-Algorithmus – benannt nach dem russischen Mathematiker Wladimir Levenshtein, der ihn 1965 entwickelte – ist ein Verfahren zur Berechnung der sogenannten Edit-Distanz (Bearbeitungsabstand) zwischen zwei Zeichenketten. Die Edit-Distanz gibt an, wie viele einzelne Zeichenoperationen mindestens notwendig sind, um eine Zeichenkette in eine andere umzuwandeln. Erlaubt sind dabei drei Operationen: ein Zeichen einfügen, ein Zeichen löschen oder ein Zeichen ersetzen – jeweils mit dem Kostenwert 1. Ein konkretes Beispiel: Die Edit-Distanz zwischen „Schuh" und „Schue" beträgt 1 (ein Zeichen ersetzen), zwischen „Hnad" und „Hand" ebenfalls 1 (Buchstaben vertauscht, eine Ersetzung). Je niedriger der berechnete Wert, desto ähnlicher sind die beiden Zeichenketten. Das Ergebnis ist eine präzise, mathematisch fundierte Ähnlichkeitsmessung – die Grundlage jeder fehlertoleranten Suche.

Der Levenshtein-Algorithmus ist in zahlreichen praxisrelevanten Bereichen des Onlinemarketings und E-Commerce im Einsatz – oft unsichtbar im Hintergrund, aber mit direktem Einfluss auf Nutzererfahrung und Umsatz:

• Fehlertolerante Suche im Online-Shop: Tippt ein Nutzer „Adibas" statt „Adidas" oder „Sneeker" statt „Sneaker", erkennt die Suchfunktion dank Levenshtein-Distanz die gemeinte Suchanfrage und liefert trotzdem relevante Ergebnisse – statt einer leeren Ergebnisseite. Dies reduziert Absprungraten messbar und schützt direkt den Umsatz.
• Rechtschreibkorrektur in Suchmaschinen: Google, Bing und andere Suchmaschinen nutzen Edit-Distanz-Berechnungen als eine Komponente, um Tippfehler in Suchanfragen zu erkennen und die Frage „Meinten Sie …?" zu generieren. Für SEO bedeutet das: Auch Seiten, die nicht exakt dem falsch geschriebenen Keyword entsprechen, können für fehlerhafte Suchanfragen sichtbar sein.
• Keyword-Analyse und Duplicate-Detection: In der SEO-Praxis hilft die Levenshtein-Distanz dabei, ähnliche Keywords in großen Keyword-Sets zu clustern, nahezu identische Seiteninhalte zu erkennen (Near-Duplicate-Content) oder Varianten eines Markenbegriffs in Suchanfragedaten zusammenzufassen.
• Datenbankbereinigung und CRM: Bei der Zusammenführung von Kundendatenbanken werden doppelte Einträge mit leicht abweichenden Schreibweisen (z. B. „Müller" vs. „Mueller") über Edit-Distanz-Vergleiche erkannt und zusammengeführt – ein wichtiger Schritt für saubere CRM- und Lead-Management-Daten.
• Chatbots und Sprachassistenten: KI-gestützte Chatbots nutzen Ähnlichkeitsmaße wie die Levenshtein-Distanz, um Nutzereingaben auch dann korrekt zu interpretieren, wenn diese Tippfehler enthalten oder von erwarteten Formulierungen abweichen.

Die Edit-Distanz (auch Levenshtein-Distanz genannt) ist der numerische Wert, den der Algorithmus als Ergebnis liefert. Er gibt an, wie viele Einzeloperationen (Einfügen, Löschen, Ersetzen) mindestens nötig sind, um Zeichenkette A in Zeichenkette B zu überführen. Die Berechnung erfolgt über eine dynamische Programmierung mit einer Matrix: Beide Zeichenketten werden entlang der Achsen einer Tabelle aufgetragen. Jede Zelle der Matrix wird mit dem Minimum aus drei möglichen Vorgängerwerten gefüllt – entsprechend den drei erlaubten Operationen. Der Wert in der letzten Zelle rechts unten ist die fertige Edit-Distanz.

• Distanz 0: Beide Zeichenketten sind identisch.
• Distanz 1: Ein einzelner Tippfehler (z. B. „Schhu" statt „Schuh" – ein Zeichen löschen).
• Distanz 2: Zwei Operationen notwendig (z. B. zwei falsch gesetzte Buchstaben).
• Hohe Distanz: Die Zeichenketten unterscheiden sich stark – eine fehlertolerante Zuordnung wäre nicht mehr sinnvoll.

In der Praxis definieren Systeme einen Toleranzschwellenwert – z. B. „zeige Treffer, wenn die Edit-Distanz ≤ 2 ist". Dieser Wert muss abhängig von der Zeichenkettenlänge und dem Anwendungsfall kalibriert werden: Bei kurzen Begriffen (3–4 Zeichen) ist eine Distanz von 2 bereits sehr tolerant; bei langen Produktbezeichnungen kann eine Distanz von 3–4 noch sinnvoll sein.

Der Levenshtein-Algorithmus ist das bekannteste, aber nicht das einzige Ähnlichkeitsmaß für Zeichenketten. Je nach Anwendungsfall können alternative Verfahren besser geeignet sein:

• Damerau-Levenshtein-Distanz: Erweitert den klassischen Algorithmus um eine vierte Operation: das Transponieren (Vertauschen) zweier benachbarter Zeichen. Da Buchstabendreher (z. B. „Hnad" statt „Hand") zu den häufigsten Tippfehlern gehören, ist diese Variante für Suchfunktionen in der Regel die praktischere Wahl.
• Jaro-Winkler-Distanz: Speziell für den Vergleich kurzer Zeichenketten wie Namen und Adressen optimiert. Liefert einen Ähnlichkeitswert zwischen 0 und 1 statt einer Anzahl von Operationen. Bevorzugt Zeichenketten, die am Anfang übereinstimmen, und eignet sich gut für die Deduplizierung von Personendaten in CRM-Systemen.
• Soundex / Metaphone: Phonetische Algorithmen, die Zeichenketten anhand ihres Klangs kodieren statt anhand ihrer exakten Schreibweise. Hilfreich, wenn Suchanfragen lautlich korrekt, aber orthografisch falsch sind (z. B. „Schmiede" vs. „Schmide"). Im deutschsprachigen Raum weniger präzise als im Englischen.
• N-Gram-Ähnlichkeit: Teilt Zeichenketten in überlappende Teilstrings fixer Länge (z. B. Bigramme oder Trigramme) auf und vergleicht deren Überschneidung. Skaliert bei sehr langen Texten effizienter als die Levenshtein-Matrix und wird häufig in Volltextsuchsystemen wie Elasticsearch eingesetzt.

In modernen Suchsystemen werden diese Verfahren oft kombiniert: Levenshtein oder Damerau-Levenshtein für die Tippfehlerkorrektur, phonetische Algorithmen für lautbasierte Ähnlichkeit und N-Gramme für die Volltextsuche über lange Dokumente.

Trotz seiner Stärken hat der Levenshtein-Algorithmus in bestimmten Anwendungsszenarien klare Schwächen, die beim Einsatz berücksichtigt werden sollten:

• Hoher Rechenaufwand bei großen Datenmengen: Die Berechnung der Edit-Distanz zwischen zwei Zeichenketten der Länge m und n hat eine Zeitkomplexität von O(m×n). Werden tausende von Suchbegriffen gegen eine große Produktdatenbank verglichen, steigt der Rechenaufwand erheblich. Für Echtzeit-Suchen in großen Katalogen werden daher optimierte Varianten oder Vorfilterungsschritte benötigt.
• Keine semantische Bedeutung: Der Algorithmus vergleicht ausschließlich Zeichenfolgen – er „versteht" keine Bedeutung. „Auto" und „PKW" haben eine hohe Edit-Distanz, sind aber bedeutungsgleich. Semantisch ähnliche Begriffe werden nicht erkannt; hierfür sind moderne NLP-Verfahren (z. B. Word Embeddings, semantische Suche) notwendig.
• Keine Berücksichtigung von Wortgrenzen: Der klassische Levenshtein-Algorithmus arbeitet auf Zeichenebene. Werden Begriffe vertauscht (z. B. „rote Schuhe" vs. „Schuhe rote"), liefert er eine hohe Distanz, obwohl die Suchabsicht identisch ist. Token-basierte Ähnlichkeitsmaße sind hier besser geeignet.
• Fehlende Sprachspezifik: Umlaute, diakritische Zeichen oder sprachspezifische Schreibvarianten (z. B. „ue" statt „ü") werden vom Algorithmus als normale Zeichenabweichungen behandelt. Ohne sprachspezifische Normalisierung (Unicode-Normalisierung, Umlaut-Mapping) können solche Varianten zu unerwünschten Ergebnissen führen.

Mit dem Aufstieg von KI-gestützten Sprachmodellen (LLMs) und semantischen Suchsystemen könnte man annehmen, dass zeichenbasierte Algorithmen wie Levenshtein an Bedeutung verloren haben – das Gegenteil ist jedoch der Fall: Levenshtein und semantische Suche ergänzen sich, statt einander zu ersetzen. Moderne Sucharchitekturen in E-Commerce-Systemen und Suchmaschinen nutzen typischerweise eine mehrschichtige Strategie:

• Schicht 1 – Tippfehlerkorrektur (Levenshtein / Damerau-Levenshtein): Korrigiert offensichtliche Eingabefehler, bevor die Suchanfrage an das semantische System weitergegeben wird. Ein Sprachmodell, das „Adibas Sneeker" als Eingabe erhält, liefert schlechtere Ergebnisse als eines, das zuerst auf „Adidas Sneaker" normalisiert.
• Schicht 2 – Semantische Suche (Vektor-Embeddings, LLMs): Versteht die inhaltliche Bedeutung der (nun korrekt geschriebenen) Suchanfrage und liefert semantisch passende Treffer – auch wenn die genauen Begriffe nicht im Dokument vorkommen.

Für Shop- und Website-Betreiber bedeutet das: Eine gute interne Suchfunktion 2026 kombiniert fehlertolerante Zeichenähnlichkeitssuche mit semantischem Matching. Systeme wie Elasticsearch, Algolia oder OpenSearch bieten beide Schichten als konfigurierbare Komponenten an. Der Levenshtein-Algorithmus bleibt dabei als erste Verteidigungslinie gegen Tippfehler unverzichtbar – auch in einer zunehmend KI-getriebenen Suchwelt.