Zunächst einmal ist der Levenshtein-Abstand definiert als die Mindestanzahl von Bearbeitungen, die erforderlich sind, um Zeichenfolge A in Zeichenfolge B umzuwandeln, wobei eine Bearbeitung das Einfügen oder Löschen eines einzelnen Zeichens oder das Ersetzen eines Zeichens durch ein anderes Zeichen ist. Es ist also sehr viel der "Unterschied zwischen zwei Saiten", für eine bestimmte Definition von Entfernung. =)
Es hört sich so an, als ob Sie nach einer Abstandsfunktion F (A, B) suchen, die einen Abstand zwischen den Saiten A und B und einen Schwellenwert N angibt, wobei Saiten mit einem Abstand von weniger als N Kandidaten für Tippfehler sind. Zusätzlich zur Levenshtein-Distanz können Sie auch Needleman–Wunsch berücksichtigen . Es ist im Grunde dasselbe, aber Sie können eine Funktion dafür bereitstellen, wie nahe ein bestimmtes Zeichen an einem anderen Zeichen ist. Sie könnten diesen Algorithmus mit einer Reihe von Gewichten verwenden, die die Positionen der Tasten auf einer QWERTZ-Tastatur widerspiegeln, um Tippfehler ziemlich gut zu finden. Dies hätte jedoch Probleme mit internationalen Tastaturen.
Wenn Sie k Zeichenfolgen haben und potenzielle Tippfehler finden möchten, müssen Sie O(k^2) vergleichen. Außerdem ist jeder Vergleich O(len(A)*len(B)). Wenn Sie also eine Million Saiten haben, werden Sie sich in Schwierigkeiten wiederfinden, wenn Sie die Dinge naiv angehen. Hier sind ein paar Vorschläge zur Beschleunigung:
- Entschuldigung, falls dies offensichtlich ist, aber die Levenshtein-Distanz ist symmetrisch, stellen Sie also sicher, dass Sie nicht F(A, B) und F(B, A) berechnen.
- abs(len(A) - len(B)) ist eine Untergrenze für den Abstand zwischen den Saiten A und B. Sie können also die Überprüfung von Saiten überspringen, deren Längen zu unterschiedlich sind.
Ein Problem, auf das Sie stoßen könnten, ist, dass "1st St." hat einen ziemlich großen Abstand von "First Street", obwohl Sie diese wahrscheinlich als identisch betrachten möchten. Der einfachste Weg, dies zu handhaben, besteht wahrscheinlich darin, Zeichenfolgen in eine kanonische Form umzuwandeln, bevor Sie die Vergleiche durchführen. Sie könnten also alle Zeichenfolgen klein schreiben, ein Wörterbuch verwenden, das "1st" auf "first" abbildet usw. Dieses Wörterbuch könnte ziemlich groß werden, aber ich kenne keinen besseren Weg, um mit diesem Problem umzugehen.
Da Sie diese Frage mit PHP getaggt haben, gehe ich davon aus, dass Sie dafür PHP verwenden möchten. PHP hat eine eingebaute levenshtein() Funktion, aber beide Strings müssen 255 Zeichen oder weniger lang sein. Wenn das nicht lang genug ist, müssen Sie Ihre eigenen machen. Alternativ untersuchen Sie dies mit Pythons difflib.
