Forschung und Tests
Wir haben mehrere Algorithmen getestet, um Strings zu vergleichen, und den ausgewählt, der unseren Anforderungen besser entspricht.
Wir haben String A und String B verglichen, um Metriken für die verschiedenen Algorithmen zu erhalten.
Regeln für die Zeichenfolgenähnlichkeit können von Fall zu Fall unterschiedlich sein. Wenn Sie „Nische“ und „Chien“ als ähnlich betrachten möchten, verwenden Sie einen String-Ähnlichkeitsalgorithmus, der Anagramme erkennt. Nicht in unserem Fall. Eine App namens „niche“ und eine andere namens „Chien“ sind sehr wahrscheinlich zwei völlig unterschiedliche Apps.
Nach einigem Brainstorming und Recherchen haben wir einige Algorithmusmethoden entwickelt, die unserem Fall helfen würden. Der Kosinusalgorithmus erwies sich für uns als irrelevant, da er beispielsweise die Buchstabenreihenfolge nicht zu berücksichtigen scheint, was zu einem Index von 1 (ähnliche Zeichenfolge) auf einem Anagramm („Nische“ und „Chien“) führt.
Hier ist, was wir bemerkt haben:
Levenshtein-Algorithmus
Der Levenshtein-Abstand ist die minimale Anzahl von Ein-Zeichen-Bearbeitungen, die erforderlich sind, um ein Wort in das andere zu ändern. Die es schwieriger machen, Muster zu zeichnen.
Zum Beispiel,
- der Levenshtein-Abstand zwischen „foo“ und „bar“ beträgt 3
- Der Levenshtein-Abstand zwischen „beauties“ und „beautiful“ beträgt ebenfalls 3
- Für uns Menschen ist das Paar „beauties“ /“beautiful“ viel ähnlicher als das Paar „foo“ /“bar“. Aber die Levenshtein-Entfernung ist die gleiche.
Die Metrik, die wir hier verwenden, ist die Umkehrung der Levenshtein-Entfernung ( 1 / levenshtein_distance), sodass das Ergebnis ein Prozentsatz ist und von uns leichter gelesen werden kann. Das oben erwähnte Problem blieb jedoch dasselbe.
Wobei 1 das Ergebnis des Vergleichs identischer Zeichenfolgen ist, haben „ShazamIphone“ und „ShazamAndroid“ eine Ähnlichkeit von 0,167. „chien“ und „niche“ haben eine Ähnlichkeit von 0,25.
Aus der Sicht des Levenshtein-Algorithmus sind Chien / Niche ähnlicher als „ShazamIphone“ /“ShazamAndroid“, da weniger Änderungen erforderlich sind, um von „chien“ zu „niche“ zu gelangen, als von „ShazamIphone“ zu „ShazamAndroid“.
Trigrammvergleich
Ein Trigrammalgorithmus ist ein Fall von n-Gramm, einer zusammenhängenden Folge von n (in diesem Fall drei) Elementen aus einer bestimmten Stichprobe. In unserem Fall ist ein Anwendungsname ein Beispiel und ein Zeichen ein Element.
Die Sequenz „martha“ hat also 4 Trigramme { martha rth tha }.
Wir können die Trigramm-Methode verwenden, um zwei Strings zu vergleichen.
Nehmen wir zum Beispiel „martha“ und dasselbe Wort mit einem Tippfehler, „marhta“, und wir können ihre Trigramme berechnen:
Trigramme „martha“: { mar art rth tha }
Trigramme „marhta“: { mar arh rht hta }
Um die Ähnlichkeit zu messen, teilen wir die Anzahl der übereinstimmenden Trigramme in beide Zeichenfolgen: 1 { mar } durch die Anzahl der eindeutigen Trigramme: 7 { mär Kunst rth tha arh rht hta }
The result is 1/7 = 14%
Um den Nachteil der äußeren Zeichen auszugleichen (um die Ähnlichkeit von Zeichenfolgen, die mit denselben Trigrammen beginnen und enden, etwas zu verstärken), füllen wir die Zeichenfolge auf beiden Seiten mit Leerzeichen auf, was in diesem Fall zu drei weiteren Trigrammen „_ma“, „ha_“ und „ta_“ führt.
Trigramme “ martha „: { _ma mar art rth tha ha_ }
Trigramme “ marhta „: { _ma mar arh rht hta ta_ }
Danach beträgt die Anzahl der übereinstimmenden Trigramme: 2 { _ma mar }
Die Anzahl aller eindeutigen Trigramme: 9 { _ma mar Kunst rth tha arh rht hta ha_ }
The result is now 2/9 = 22%
Mit dieser Methode zum Vergleichen von „Twitter v1“ und „Twitter v2“ haben wir:
Die Anzahl der übereinstimmenden Trigramme: 7 { _tw twi wit itt tte ter er_ }
Die Anzahl aller eindeutigen Trigramme: 11 { tw twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
Die Grenze der Trigramm-Methode zum Vergleichen von Strings ist, dass kurze Strings mit einem (oder zwei)..) verschiedene Trigramme neigen dazu, eine geringere Ähnlichkeit als lange zu erzeugen.
So erhalten wir eine 0.2 Ähnlichkeit zwischen „ShazamAndroid“ und „ShazamIphone“, da sie mehr verschiedene Trigramme haben.
Die Anzahl der übereinstimmenden Trigramme ist: 5 { _sh sha haz aza zam }
Die Anzahl aller eindeutigen Trigramme: 20
Da es eine starke Abhängigkeit von der Zeichenfolgenlänge gibt, ergibt dies keinen guten Vergleich für uns.
Jaro-Winkler-Algorithmus
“ In der Informatik und Statistik ist die Jaro-Winkler-Distanz eine Zeichenfolgenmetrik zur Messung der Schnittentfernung zwischen zwei Sequenzen.
Informell ist der Jaro-Abstand zwischen zwei Wörtern die minimale Anzahl von Transpositionen aus einem Zeichen, die erforderlich sind, um ein Wort in das andere zu ändern.
Die Jaro-Winkler-Distanz verwendet eine Präfixskala, die Zeichenfolgen, die von Anfang an übereinstimmen, für eine festgelegte Präfixlänge günstigere Bewertungen gibt“
Quelle: Wikipedia.
Wörter mit identischen Präfixen „wichtiger“ zu machen, machte den Jaro-Winkler-Abstand für unseren Anwendungsfall sehr interessant.
Beginnen Sie von Anfang an mit der Jaro-Entfernungsformel, hier erfahren Sie, wie es funktioniert. Keine Panik, wir gehen Schritt für Schritt vor:
Der Jaro-Abstand zwischen zwei Sequenzen s1 und s2 ist definiert durch:
dj ist der Jaro-Abstand
m ist die Anzahl der übereinstimmenden Zeichen (Zeichen, die in s1 und in s2 vorkommen)
t ist die halbe Anzahl der Transpositionen (vergleiche das i-te Zeichen von s1 und das i-te Zeichen von s2 geteilt durch 2)
| s1 | ist die Länge der ersten Zeichenfolge
|s2 | ist die Länge der zweiten Zeichenfolge
Mit a Beispiel. Nehmen wir „Martha“ und „Marhta“.
m = 6
t = 2/2 =1 (2 couples of non matching characters, the 4-th and 5-th) { t/h ; h/t }
|s1| = 6
|s2| = 6
Nur durch Ersetzen von Zahlen ist die Formel, wir bekommen:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
Jetzt wissen wir, was die Jaro-Distanz ist, springen wir zur Jaro-Winkler-Distanz.
Die Jaro-Winkler-Ähnlichkeit verwendet eine Präfixskala p, die Zeichenfolgen, die von Anfang an für eine festgelegte Präfixlänge l übereinstimmen, günstigere Bewertungen gibt.
p ist ein konstanter Skalierungsfaktor dafür, wie stark die Punktzahl nach oben angepasst wird, um gemeinsame Präfixe zu haben. Der Standardwert für diese Konstante in Winklers Arbeit ist p = 0,1.
l ist die Länge des Präfixes am Anfang der Zeichenfolge (bis zu maximal 4 Zeichen).
Zurück zum Beispiel „martha“ / „marhta“ nehmen wir eine Präfixlänge von l = 3 (was sich auf „mar“ bezieht). Wir kommen zu:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
Mit der JaroWinkler-Formel gehen wir von der Jaro-Distanz bei 94% Ähnlichkeit zu 96%.
In unserem Fall beginnen die meisten ähnlichen Apps mit demselben Präfix („twitter v1“ vs „twitter v2“ oder „ShazamIphone“ vs „ShazamAndroid“ usw. Siehe die Algorithmen-Testtabelle oben). Es ist also ein wichtiges Kriterium zu berücksichtigen.
