Finden, wie ähnlich zwei Zeichenketten sind

Question

Ich suche nach einem Algorithmus, der 2 Zeichenketten nimmt und mir einen "Ähnlichkeitsfaktor" zurückgibt.

Grundsätzlich werde ich eine Eingabe haben, die falsch geschrieben sein kann, Buchstaben transponiert haben, usw., und ich muss die nächste Übereinstimmung in einer Liste der möglichen Werte finden, die ich habe.

Dies ist nicht für die Suche in einer Datenbank. Ich werde eine In-Memory-Liste von etwa 500 Strings haben, um alle zu vergleichen, alle unter 30 Zeichen, also kann es relativ langsam sein.

Ich weiß, dass es existiert, ich habe es vorher gesehen, aber ich kann mich nicht an seinen Namen erinnern.

---

Edit: Danke für das Aufzeigen von Levenshtein und Hamming. Nun, welche sollte ich implementieren? Sie messen grundsätzlich verschiedene Dinge, die beide für das verwendet werden können, was ich will, aber ich bin mir nicht sicher, welches besser geeignet ist.

Ich habe die Algorithmen gelesen, Hamming scheint offensichtlich schneller. Da keiner von beiden erkennen wird, dass zwei Charaktere transponiert werden (z. B. Jordan und Jodran), was meiner Meinung nach ein häufiger Fehler sein wird, der genauer sein wird für das, was ich will? Kann mir jemand etwas über die Kompromisse erzählen?

Answer 1

Ok, so dass die Standard-Algorithmen sind:

1) Hamming distance Nur gut für die Saiten von gleicher Länge, aber sehr effizient. Im Grunde zählt es einfach die Anzahl der verschiedenen Zeichen. Nicht nützlich für die unscharfe Suche von Text in natürlicher Sprache.

2) . Die Levenstein-Distanz misst die Entfernung in Bezug auf die Anzahl der "Operationen", die erforderlich sind, um eine Zeichenfolge in eine andere umzuwandeln. Diese Operationen umfassen Einfügen, Löschen und Ersetzen. Der Standardansatz zur Berechnung der Levenstein-Distanz ist die dynamische Programmierung.

3) Generalized Levenstein/(Damerau–Levenshtein distance) Dieser Abstand berücksichtigt auch Transpositionen von Zeichen in einem Wort und ist wahrscheinlich die Bearbeitungsentfernung, die am besten für die Fuzzy-Anpassung von manuell eingegebenem Text geeignet ist. Der Algorithmus zur Berechnung der Entfernung ist ein wenig komplizierter als die Levenstein-Distanz (das Erkennen von Transpositionen ist nicht einfach). Die häufigsten Implementierungen sind eine Modifikation des bitap Algorithmus (wie grep).

Im Allgemeinen würden Sie wahrscheinlich wollen eine Implementierung der dritten Option in einer Art Nearest-Neighbor-Suche basiert auf einem kd Baum Eigentlich

Answer 2

Sie suchen nach dem Levenshtein distance

Answer 3

• Levenstein Entfernung
• Hamming-Distanz
• soundex
• Metaphone

Answer 4

die Damerau-Levenshtein distance ist ähnlich der Levenshtein-Distanz, sondern umfasst auch Zwei-Zeichen-Transposition. Die Wikipedia-Seite (verlinkt) enthält einen Pseudocode, der relativ einfach zu implementieren sein sollte.