Ich habe die folgenden 2 Zeichenfolgen:
%Vor%Beide Zeichenfolgen sind gleich, enthalten jedoch unterschiedliche Werte.
Wie kann ich diese Zeichenfolge vergleichen, um eine "übereinstimmende Punktzahl" zu erhalten, wie in dem Fall, das erste Wort ist ähnlich, "Manchester" und die zweiten Wörter enthalten ähnliche Buchstaben, aber nicht an der richtigen Stelle.
Gibt es einen einfachen Algorithmus, der die "übereinstimmende Punktzahl" zurückgibt, nachdem ich 2 Zeichenfolgen geliefert habe?
Sie können die Levenshtein-Distanz zwischen den beiden Strings berechnen und wenn sie kleiner ist als ein Wert (den Sie definieren müssen ) Sie können sie als ziemlich nah betrachten.
Ich musste etwas in der Art machen und Levenshtein Entfernung benutzen.
Ich habe es für eine SQL Server UDF verwendet, die in Abfragen mit mehr als einer Million Zeilen (und Texten von bis zu 6 oder 7 Wörtern) verwendet wird.
Ich fand, dass der Algorithmus schneller läuft und der "Ähnlichkeitsindex" genauer ist, wenn Sie jedes Wort einzeln vergleichen. I.e. Sie teilen jede Eingabezeichenfolge in Worte und vergleichen jedes Wort einer Eingabezeichenfolge mit jedem Wort der anderen Eingabezeichenfolge.
Denken Sie daran, dass Levenshtein den Unterschied macht, und Sie müssen es in einen "Ähnlichkeitsindex" umwandeln. Ich benutzte etwas wie die Entfernung, geteilt durch die Länge des längsten Wortes (aber mit einigen Variationen)
Sie müssen auch Folgendes beachten:
Abhängig davon ändert sich der Algorithmus. Zum Beispiel ist die Anwendung der ersten Regel sehr schnell, wenn die Anzahl der Wörter unterschiedlich ist. Und die zweite Regel reduziert die Anzahl der Vergleiche, besonders wenn es viele Wörter in den verglichenen Texten gibt. Das wird später mit Beispielen erklärt.
Ich habe auch die längeren Wörter höher gewichtet als die kürzeren Wörter, um den globalen Ähnlichkeitsindex zu erhalten. Mein Algorithmus nimmt das längste der beiden Wörter im Vergleichspaar und gibt dem Paar mit den längeren Wörtern ein höheres Gewicht als dem Paar mit den kürzeren Wörtern, obwohl es nicht genau proportional zur Paarlänge ist.
Bei diesem Beispiel, das eine andere Anzahl von Wörtern verwendet:
Wenn die gleiche Reihenfolge der Wörter in beiden Eingaben garantiert ist, sollten Sie diese Paare vergleichen:
%Vor%(Manchester, Manchester) (Utd, Vereinigtes) (FC: nicht verglichen)
%Vor%(Manchester, Manchester) (Utd: nicht verglichen) (United, FC)
%Vor%(Manchester: nicht verglichen) (Manchester, Utd) (United, FC)
Offensichtlich wäre die höchste Punktzahl für die erste Gruppe von Paaren.
Um Wörter in der gleichen Reihenfolge zu vergleichen.
Die Zeichenfolge mit der höheren Anzahl von Wörtern ist ein fester Vektor, der in diesem Beispiel als A, B, C, D, E dargestellt wird. Wo v [0] ist das Wort A, v [1] das Wort B und so weiter.
Für die Zeichenfolge mit der niedrigeren Anzahl von Wörtern müssen wir alle möglichen Kombinationen von Indizes erstellen, die mit dem ersten Satz verglichen werden können. In diesem Fall wird die Zeichenfolge mit der niedrigeren Anzahl von Wörtern durch a, b, c dargestellt.
Sie können eine einfache Schleife verwenden, um alle Vektoren zu erstellen, die die zu vergleichenden Paare darstellen, wie zB
%Vor%Die Zahlen in der Stichprobe sind Vektoren, die die Indizes der ersten Menge von Wörtern haben, die mit den Indizes in der ersten Menge verglichen werden müssen. dh v [0] = 0, bedeutet Vergleich Index 0 der kurzen Menge (a) mit Index 0 der langen Menge (A), v [1] = 2 bedeutet Vergleich von Index 1 der kurzen (b) Menge mit Index 2 der langen Reihe (C) und so weiter.
Um diese Vektoren zu berechnen, beginnen Sie einfach mit 0,1,2. Verschiebe den letzten Index, der verschoben werden kann, bis er nicht mehr verschoben werden kann, nach rechts:
Strat durch Verschieben des letzten:
%Vor%Wenn der letzte nicht weiter bewegt werden kann, bewege den vorletzten und setze den letzten auf den nächsten möglichen Platz zurück (1 zu 2 und 4 zu 3):
%Vor%Bewege den vorletzten wieder.
%Vor%Verschiebe die vorherige:
%Vor%Und so weiter. Siehe das Bild
Wenn Sie alle möglichen Kombinationen haben, können Sie die definierten Paare vergleichen.
Stoppen Sie den Vergleich, wenn die minimale Ähnlichkeit erreicht ist: Je nachdem, was Sie tun möchten, ist es möglich, dass Sie einen Threshold setzen, der den Vergleich der Paare stoppt, wenn er erreicht ist.
Wenn Sie keine Thresold setzen können, können Sie immer aufhören, wenn Sie für jedes Wortpaar eine 100% ige Ähnlichkeit haben. Das spart viel Zeit.
Manchmal können Sie einfach entscheiden, den Vergleich zu beenden, wenn die Ähnlichkeit mindestens bei 75% liegt. Dies kann verwendet werden, wenn Sie dem Benutzer alle Zeichenfolgen anzeigen möchten, die denen ähneln, die vom Benutzer bereitgestellt werden.
Wenn es Änderungen in der Reihenfolge geben kann, müssen Sie jedes Wort des ersten Satzes mit jedem Wort des zweiten Satzes vergleichen und die höchsten Bewertungen für die Kombinationen der Ergebnisse nehmen, die alle Wörter des kürzesten Paares enthalten geordnet auf allen möglichen Wegen, verglichen mit verschiedenen Wörtern des zweiten Paares. Dazu können Sie das obere oder untere Dreieck einer Matrix von (n X m) Elementen auffüllen und dann die benötigten Elemente aus der Matrix nehmen.
Sie müssen das Wort vor dem Vergleich auch normalisieren:
Um die Prozedur zu optimieren, habe ich zwischengespeichert, was auch immer ich konnte, dh die Vergleichsvektoren für verschiedene Größen, wie die Vektoren 0,1,2-0,1,3, -0,1,4-0,2,3, in den Vergleichsbeispielen A, B, C, D, E bis a, b, c: Alle Vergleiche für die Längen 3,5 würden bei der ersten Verwendung berechnet und für alle eingehenden Vergleiche mit 3 Wörtern bis 5 Wörtern wiederverwendet.
Ich habe Hamming Abstand versucht und die Ergebnisse waren weniger genau.
Sie können viel komplexere Dinge tun, wie semantische Vergleiche, phonetische Vergleiche, beachten Sie, dass einige Buchstaben genau gleich sind (wie b und v , für mehrere Sprachen, wie Spanisch, wo es keine Unterscheidung gibt). Einige dieser Dinge sind sehr einfach zu implementieren und andere sind wirklich schwierig.
HINWEIS: Ich habe die Implementierung der Levenhstein-Distanz nicht berücksichtigt, weil Sie sie leicht auf verschiedenen Ebenen implementieren können
Schauen Sie sich diesen Artikel an, der erklärt, wie es geht und gibt auch Beispielcode:)
Fuzzy Matching (Levenshtein Entfernung)
Aktualisierung:
Hier ist der Methodencode, der zwei Strings als Parameter akzeptiert und den "Levenshtein Distance" der beiden Strings berechnet
%Vor%Das Erkennen von Duplikaten ist manchmal etwas "komplizierter" als die Berechnung von Levenshtein dinstance. Betrachten Sie folgendes Beispiel:
%Vor%Diese Duplikate können mit komplizierten Cluster-Algorithmen verglichen werden.
Für weitere Informationen möchten Sie vielleicht einige Forschungsarbeiten wie "Effektives inkrementelles Clustering für doppelte Erkennung in großen Datenbanken".
(Beispiel stammt von der Zeitung)
Was Sie suchen, ist ein Zeichenfolgenähnlichkeitsmaß. Es gibt mehrere Möglichkeiten, dies zu tun:
Im Allgemeinen finde ich die Option # 2 am einfachsten zu implementieren und wenn Ihre Strings Phrasen sind, dann können Sie sie einfach an Wortgrenzen in Token zerlegen. In allen oben genannten Fällen möchten Sie möglicherweise zuerst die Stoppwörter (allgemeine Wörter wie und, a, etc) vor dem Token löschen. Aktualisieren: Links
Naive Similarity-Engine in C # implementieren * Warnung: schamlose Selbstwerbung
Hier ist eine Alternative zur Verwendung des Levenshtein-Distanzalgorithmus. Dies vergleicht Zeichenfolgen basierend auf dem Koeffizienten der Würfel, der die Anzahl der gemeinsamen Buchstabenpaare in jeder Zeichenfolge vergleicht, um einen Wert zwischen 0 und 1 zu erzeugen, wobei 0 keine Ähnlichkeit und 1 vollständige Ähnlichkeit ist.
%Vor%Rufen Sie die Methode wie folgt auf:
%Vor% Ausgabe ist: 0.75862068965517238