Levenshtein Algorithmus
Was ist der Levenshtein-Algorithmus?
Der Levenshtein-Algorithmus berechnet die minimale Anzahl einzelner Zeichenoperationen, die nötig ist, um eine Zeichenfolge in eine andere umzuwandeln. Er zählt Einfügungen, Löschungen und Ersetzungen. Eine Distanz von 0 bedeutet identische Texte, während höhere Werte eine größere Abweichung anzeigen.
Grundidee des Levenshtein-Algorithmus
Der Levenshtein-Algorithmus misst die Ähnlichkeit zweier Zeichenfolgen anhand ihrer Levenshtein-Distanz, auf Deutsch auch Editierdistanz genannt. Entscheidend ist der kürzeste Bearbeitungsweg zwischen den Zeichenfolgen. Der Algorithmus bewertet dabei jedes eingefügte, gelöschte oder ersetzte Zeichen üblicherweise mit den Kosten 1.
Ein Beispiel: Zwischen SEO und SEA beträgt die Distanz 1, weil nur das letzte Zeichen ersetzt werden muss. Zwischen SEO und SEO beträgt sie 0. Die Distanz ist eine absolute Zahl und hängt deshalb von der Länge der verglichenen Begriffe ab.
So funktioniert die Berechnung
Der Levenshtein-Algorithmus verwendet eine Matrix mit einer Zeile pro Zeichen der ersten Zeichenfolge und einer Spalte pro Zeichen der zweiten Zeichenfolge. Die erste Zeile und die erste Spalte enthalten fortlaufende Werte. Sie bilden den Aufwand ab, eine leere Zeichenfolge allein durch Einfügungen oder Löschungen aufzubauen.
Für jedes weitere Matrixfeld werden drei mögliche Wege verglichen:
Der kleinste dieser drei Werte wird in das aktuelle Feld übernommen. Der Wert rechts unten enthält am Ende die Levenshtein-Distanz. Für Zeichenfolgen mit den Längen m und n benötigt die klassische Berechnung m × n Vergleiche. Die Zeitkomplexität beträgt daher O(m × n).
Haus und Maus lautet das Ergebnis 1. Die minimale Bearbeitung besteht aus einer einzigen Ersetzung: Das Zeichen H wird durch M ersetzt. Zusätzliche Operationen wären möglich, würden aber nicht dem kürzesten Bearbeitungsweg entsprechen. Distanz richtig einordnen
Eine Levenshtein-Distanz von 3 hat ohne Bezug zur Wortlänge nur begrenzte Aussagekraft. Drei Änderungen sind bei zwei Zeichenfolgen mit jeweils vier Zeichen erheblich, bei Texten mit jeweils 100 Zeichen dagegen gering. Für Vergleiche unterschiedlich langer Begriffe wird die Distanz deshalb häufig normalisiert.
Eine mögliche Ähnlichkeitsformel lautet: 1 minus Distanz geteilt durch die Länge der längeren Zeichenfolge. Multipliziert mit 100 ergibt sich ein Prozentwert. Bei SEO und SEA beträgt die Distanz 1 und die maximale Länge 3. Die normalisierte Ähnlichkeit liegt damit bei rund 66,7 Prozent.
Messbar ist die Zeichenähnlichkeit also über Distanz und Normalisierung. Ein allgemeingültiger Grenzwert existiert jedoch nicht. Prüfe Schwellenwerte immer an echten Begriffspaaren aus deinem Datenbestand. Bei kurzen Markenbezeichnungen kann eine Änderung bereits relevant sein, während längere Produktnamen mehrere Abweichungen vertragen.
Levenshtein-Algorithmus im SEO
Im SEO kann der Levenshtein-Algorithmus Schreibvarianten, Tippfehler und nahezu identische Keywords erkennen. Das erleichtert die Bereinigung großer Keywordlisten und ergänzt eine strukturierte SEO-Keyword-Recherche. Der Algorithmus kann beispielsweise Onlineshop und Onlineshp als ähnliche Zeichenfolgen markieren.
Für das Keyword-Clustering reicht die Levenshtein-Distanz allein nicht aus. Zwei Begriffe können fast gleich geschrieben sein und trotzdem verschiedene Bedeutungen haben. Umgekehrt können Auto und Fahrzeug dasselbe Thema bezeichnen, obwohl ihre Zeichenfolgen kaum übereinstimmen. Kombiniere Zeichenähnlichkeit deshalb mit Suchintention, SERP-Überschneidungen und semantischer Analyse.
Für eine erste Recherche nach Suchvolumen, Konkurrenz und Klickpreisen kannst du den kostenlosen Keyword-Planer verwenden. Die fachliche Entscheidung, ob zwei Keywords dieselbe Seite benötigen, bleibt von der Suchintention abhängig.
Nutzen für SEA und GEO
Im SEA kann der Levenshtein-Algorithmus ähnliche Suchbegriffe aus Suchanfrageberichten gruppieren. Dadurch lassen sich Tippfehler, Singular- und Pluralvarianten oder leicht abweichende Produktbezeichnungen schneller prüfen. Vor einer Zusammenführung muss jedoch kontrolliert werden, ob Conversion-Rate, Kosten und Nutzerabsicht vergleichbar sind.
Bei GEO (Generative Engine Optimization) kann die Zeichenähnlichkeit helfen, unterschiedliche Schreibweisen einer Marke oder eines Produkts in analysierten Quellen zu vereinheitlichen. Der Levenshtein-Algorithmus erkennt jedoch weder Empfehlungen noch den Kontext einer KI-Antwort. Für die Bewertung von ChatGPT, Perplexity, Gemini und Grok werden deshalb zusätzliche semantische und entitätsbasierte Verfahren benötigt.
Abgrenzung zu ähnlichen Verfahren
| Verfahren | Was wird verglichen? | Wesentlicher Unterschied |
|---|---|---|
| Levenshtein-Distanz | Zeichenfolgen beliebiger Länge | Zählt Einfügungen, Löschungen und Ersetzungen. |
| Damerau-Levenshtein-Distanz | Zeichenfolgen beliebiger Länge | Berücksichtigt zusätzlich das Vertauschen benachbarter Zeichen. |
| Hamming-Distanz | Zeichenfolgen gleicher Länge | Zählt ausschließlich abweichende Zeichenpositionen. |
| Semantische Ähnlichkeit | Bedeutung von Wörtern oder Texten | Erfasst inhaltliche Nähe auch bei unterschiedlicher Schreibweise. |
Der Unterschied zwischen dem Levenshtein-Algorithmus und der Damerau-Levenshtein-Variante wird bei typischen Vertippern sichtbar. Die Umwandlung von SEO in SOE benötigt nach dem klassischen Verfahren zwei Ersetzungen. Die Damerau-Variante kann den Tausch der benachbarten Zeichen E und O als eine Operation werten.
Typische Fehler bei der Anwendung
Der häufigste Fehler ist die Gleichsetzung von ähnlicher Schreibweise und gleicher Bedeutung. Der Levenshtein-Algorithmus bewertet ausschließlich Zeichenpositionen. Er weiß nicht, ob zwei Begriffe synonym sind, dieselbe Suchintention bedienen oder für dieselbe Landingpage geeignet sind.
Eine saubere Vorverarbeitung entscheidet darüber, ob die Ergebnisse verwendbar sind. Bei Produktdaten kann das Entfernen von Artikelnummern sinnvoll sein. Bei Markenmonitoring können genau diese Zeichen relevant sein. Prüfe deshalb zuerst, welche Bestandteile eine Identität kennzeichnen, bevor du Texte normalisierst oder kürzt.
Häufige Fragen zum Levenshtein-Algorithmus
Kann der Levenshtein-Algorithmus ganze Texte vergleichen?
Ja, technisch lassen sich auch ganze Texte vergleichen. Mit zunehmender Textlänge steigen jedoch Rechenaufwand und Risiko irreführender Ergebnisse. Für längere Dokumente sind abschnittsweise oder semantische Vergleiche meist aussagekräftiger.
Beachtet der Algorithmus Groß- und Kleinschreibung?
Der Levenshtein-Algorithmus behandelt Groß- und Kleinbuchstaben als unterschiedliche Zeichen, sofern die Eingaben nicht vorher vereinheitlicht werden. Die gewünschte Behandlung muss deshalb vor der Berechnung festgelegt werden.
Welcher Schwellenwert gilt für ähnliche Wörter?
Es gibt keinen allgemeingültigen Schwellenwert. Der passende Grenzwert hängt von Wortlänge, Sprache und Anwendungsfall ab. Kurze Begriffe benötigen meist strengere Grenzen als lange Produktnamen.
Erkennt der Levenshtein-Algorithmus Synonyme?
Nein. Der Algorithmus vergleicht Zeichen und erkennt keine Wortbedeutungen. Synonyme wie 'Auto' und 'Fahrzeug' erfordern semantische Verfahren oder ein Wörterbuch.
Wie werden Leerzeichen und Sonderzeichen behandelt?
Leerzeichen und Sonderzeichen zählen grundsätzlich als normale Zeichen. Werden sie entfernt oder vereinheitlicht, verändert sich die berechnete Distanz. Die Vorverarbeitung muss daher für alle Datensätze gleich sein.
Eignet sich die Levenshtein-Distanz für Duplicate Content?
Die Levenshtein-Distanz kann nahezu identische kurze Texte erkennen. Für längere Seiten reicht sie allein nicht aus, weil Struktur, Wortreihenfolge und Bedeutung fehlen. Duplicate-Content-Prüfungen benötigen zusätzliche Verfahren.
Wenn du Keyworddaten, Schreibvarianten und technische Auffälligkeiten deiner Domain strukturiert auswerten möchtest, kannst du mit einem kostenlosen Account starten.
Sie haben noch Fragen?
