forskning och tester
vi testade flera algoritmer för att jämföra strängar och valde den som bättre skulle passa vårt behov.
vi jämförde sträng A och sträng B för att ha mått på de olika algoritmerna.
regler för stränglikhet kan skilja sig från fall till fall. Om du vill överväga ”nisch” och ”chien” liknande, skulle du använda en stränglikhetsalgoritm som upptäcker anagram. Inte i vårt fall. En app som heter” nisch ”och en annan som heter” chien ” är mycket sannolikt två helt olika appar.
efter lite brainstorming och forskning kom vi fram till några algoritmmetoder som skulle hjälpa vårt fall. Cosinusalgoritmen visade sig vara irrelevant för oss, eftersom det till exempel inte verkar ta hänsyn till bokstavsordern, vilket leder till ett index på 1 (liknande sträng) på ett anagram (”nisch” och ”chien”).
här är vad vi märkte:
Levenshtein-algoritmen
Levenshtein-avståndet är det minsta antalet redigeringar med enstaka tecken som krävs för att ändra ett ord till det andra, så resultatet är ett positivt heltal, känsligt för stränglängd . Vilket gör det svårare att rita mönster.
till exempel,
- Levenshtein-avståndet mellan ”foo” och ”bar” är 3
- Levenshtein-avståndet mellan ”beauties” och ”beautiful”är också 3
- för oss människor är”beauties”/”beautiful” – paret mycket mer lik”foo”/ ” bar ” – paret. Men Levenshtein-avståndet är detsamma.
den metriska vi använder här är inversen av Levenshtein-avståndet (1 / levenshtein_distance ) så resultatet är en procentandel och läses lättare av oss. Men problemet som nämns ovan förblev detsamma.
där 1 är resultatet av att jämföra identiska strängar, ”ShazamIphone” och ”ShazamAndroid” har en likhet på 0,167. ”chien” och ”nisch” har en likhet på 0,25.
så från Levenshtein-algoritmens synvinkel är Chien/nisch mer lika än ”ShazamIphone”/”ShazamAndroid” eftersom färre ändringar behövs för att komma från ”chien” till ”nisch” än att komma från ”ShazamIphone” till ”ShazamAndroid”.
trigram jämförelse
en trigram algoritm är ett fall av n-gram, en sammanhängande sekvens av n (tre, i detta fall) objekt från ett givet prov. I vårt fall är ett Applikationsnamn ett prov och ett tecken är ett objekt.
så sekvensen ”martha” har 4 trigram { mar art rth tha }.
vi kan använda Trigrammetoden för att jämföra två strängar.
ta till exempel ”martha” och samma ord med ett typsnitt, ”marhta”, och vi kan beräkna deras trigram:
trigram ”martha”: { mar art RTH tha }
trigram ”marhta”: { mar arh rht HTA }
för att mäta likhet delar vi antalet matchande trigram i båda strängarna: 1 { mar } med antalet unika trigram: 7 { Mar art RTH tha arh rht hta }
The result is 1/7 = 14%
för att balansera nackdelen med de yttre tecknen (något för att förstärka likheten mellan strängar som börjar och slutar med samma trigram), lägger vi strängen med ämnen på vardera sidan, vilket resulterar i dessa fall i ytterligare tre trigram ”_ma”, ”ha_” och ”ta_”.
trigram ”martha”: {_ma mar art RTH tha ha_ }
trigram ”marhta”: {_ma mar arh rht HTA ta_ }
efter att ha gjort det är antalet matchande trigram upp till: 2 { _ma mar }
antalet alla unika trigram: 9 { _ma mar art RTH tha arh rht hta ha_ }
The result is now 2/9 = 22%
med denna metod för att jämföra ”Twitter v1” och ”Twitter v2” har vi:
antalet matchande trigram: 7 { _tw twi wit ITT tte ter er_ }
antalet alla unika trigram: 11 { TW twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
gränsen för Trigrammetoden för att jämföra strängar är att korta strängar med en (eller två..) olika trigram tenderar att ge en lägre likhet än långa.
det är så vi får en 0.2 likhet mellan” ShazamAndroid ”och” ShazamIphone”, eftersom de har mer olika trigram.
antalet matchande trigram är: 5 { _sh sha haz aza zam }
antalet alla unika trigram: 20
eftersom det finns ett starkt beroende av stränglängd ger det inte en bra jämförelse för oss.
Jaro-Winkler-algoritmen
”i datavetenskap och statistik är Jaro-Winkler-Avståndet ett strängmått för att mäta redigeringsavståndet mellan två sekvenser.
informellt är Jaro-avståndet mellan två ord det minsta antalet transpositioner med ett tecken som krävs för att ändra ett ord till det andra.
Jaro-Winkler-avståndet använder en prefixskala som ger mer gynnsamma betyg till strängar som matchar från början för en uppsättning prefixlängd”
källa: Wikipedia.
att ge ”större betydelse” för ord med identiska prefix gjorde Jaro-Winkler-avståndet mycket intressant för vårt användningsfall.
börja från början med Jaro distance-formeln, här hur det fungerar. Var inte panik, vi går steg för steg:
Jaro-avståndet mellan två sekvenser s1 och s2 definieras av:
dj är Jaro-avståndet
M är antalet matchande tecken (tecken som visas i s1 och i s2)
t är hälften av antalet transpositioner (jämför i-th-tecknet i s1 och i-th-tecknet i s2 dividerat med 2)
|s1| är längden på den första strängen
|s2| är längden på den andra strängen
med ett exempel. Låt oss ta ”martha” och ”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
bara genom att ersätta siffror är formeln får vi:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
nu vet vi vad som är Jaro-avståndet, låt oss hoppa till Jaro-Winkler-avståndet.
Jaro-Winkler-likheten använder en prefixskala p som ger mer gynnsamma betyg till strängar som matchar från början för en uppsättning prefixlängd l.
p är en konstant skalningsfaktor för hur mycket poängen justeras uppåt för att ha vanliga prefix. Standardvärdet för denna konstant i Winklers arbete är p=0,1.
l är längden på vanligt prefix i början av strängen (upp till maximalt 4 tecken).
så tillbaka till” martha ”/” marhta ”- exemplet, låt oss ta ett prefixlängd på l = 3 (som hänvisar till”mar”). Vi kommer till:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
med hjälp av JaroWinkler-formeln går vi från Jaro-avståndet med 94% likhet med 96%.
i vårt fall börjar de flesta liknande appar med samma prefix (”twitter v1” vs ”twitter v2” eller ”ShazamIphone” vs ”ShazamAndroid” etc. Se tabellen för Algoritmtestning ovan). Så det är ett viktigt kriterium att ta hänsyn till.
