Forskning Og Tester
vi testet flere algoritmer for å sammenligne strenger, og valgte den som bedre passer vårt behov.
vi sammenlignet Streng A Og Streng B for å ha beregninger på de forskjellige algoritmer.
Regler for strenglikhet kan variere fra sak til sak. Hvis du vil vurdere» nisje «og» chien » lignende, vil du bruke en strenglikhetsalgoritme som oppdager anagrammer. Ikke i vårt tilfelle. En app som heter «nisje» og en annen som heter «chien» er svært sannsynlig å være to helt forskjellige apps.
etter litt brainstorming og forskning kom vi opp med noen algoritmemetoder som ville hjelpe vår sak. Cosinusalgoritmen viste seg å være irrelevant for oss, for eksempel ser det ikke ut til å ta hensyn til brevordren, noe som fører til en indeks på 1 (lignende streng) på et anagram («nisje «og»chien»).
Her er hva vi la merke til:
Levenshtein-Algoritmen
Levenshtein-avstanden er det minste antall redigeringer med enkelt tegn som kreves for å endre ett ord til det andre, så resultatet er et positivt heltall, følsomt for strenglengde . Som gjør det vanskeligere å tegne mønster.
for eksempel,
- Levenshtein-avstanden mellom» foo «og» bar «er 3
- Levenshtein-avstanden mellom» beauties «og» beautiful «er også 3
- for oss mennesker er»beauties»/» beautiful «- paret mye mer lik»foo»/» bar » – paret. Men Levenshtein-avstanden er den samme.
metriske vi bruker her er den inverse Av Levenshtein avstanden (1 / levenshtein_distance ) så resultatet er en prosentandel og blir lettere lest av oss. Men problemet nevnt ovenfor forblir det samme.
hvor 1 er resultatet av å sammenligne identiske strenger, har «ShazamIphone» og «ShazamAndroid» en likhet på 0,167. «chien » og» nisje » har en likhet på 0,25.
Så Fra levenshtein algoritmen synspunkt Chien / Nisje er mer lik «ShazamIphone» / «ShazamAndroid» fordi færre endringer er nødvendig for å få fra «chien» til «nisje», enn å få fra» ShazamIphone «til»ShazamAndroid».
Trigram Sammenligning
en trigram algoritme er et tilfelle av n-gram, en sammenhengende sekvens av n (tre, i dette tilfellet) elementer fra en gitt prøve. I vårt tilfelle er et søknadsnavn et eksempel og et tegn er et element.
så sekvensen «martha» har 4 trigrams { mar art rth tha }.
Vi kan bruke Trigram-metoden til å sammenligne to strenger.
Tar for eksempel «martha» Og det samme ordet med en skrivefeil, «marhta», og vi kan beregne deres trigrams:
Trigrams «martha»: { mar art rth tha }
for å måle likheten deler vi antall matchende trigrams i begge strengene: 1 { mar} ved antall unike trigrams: 7 { mar art rth tha arh rht hta }
The result is 1/7 = 14%
for å balansere ulempen med de ytre tegnene (noe for å styrke likheten til strenger som starter og slutter med de samme trigrams), puter vi strengen med emner på hver side, noe som resulterer i disse tilfellene i tre trigrams «_ma», «ha_» og «ta_».
Trigrams » martha «: { _ma mar art rth tha ha_ }
Trigrams «marhta»: {_ma mar arh rht hta ta_}
etter å ha gjort det, er antall matchende trigrams opp til: 2 { _ma mar }
antallet av alle unike trigrams: 9 { _ma mar art rth tha arh rht hta ha_ }
The result is now 2/9 = 22%
Ved hjelp av denne metoden for å sammenligne» Twitter v1 «og» Twitter v2 » vi har:
antall matchende trigrams: 7 { _tw twi wit itt tte ter er_ }
antall alle unike trigrams: 11 { tw twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
grensen For trigrammetoden for å sammenligne strenger er at korte strenger med en (eller to..) ulike trigrams har en tendens til å produsere en lavere likhet enn lange.
det er slik vi får en 0.2 likhet mellom «ShazamAndroid» Og «ShazamIphone», som de har flere forskjellige trigrams.
antall matchende trigrams er: 5 { _sh sha haz aza zam}
antallet av alle unike trigrams: 20
da det er en sterk avhengighet med strenglengde, gir det ikke en god sammenligning for oss.
Jaro-Winkler Algoritme
«i informatikk og statistikk Er jaro-Winkler-avstanden en strengmetrisk for å måle redigeringsavstanden mellom to sekvenser.
Uformelt Er jaro-avstanden mellom to ord det minste antall transposisjoner med enkelt tegn som kreves for å endre ett ord til det andre.
jaro-Winkler-avstanden bruker en prefiksskala som gir gunstigere karakterer til strenger som samsvarer fra begynnelsen for en angitt prefikslengde»
Kilde: Wikipedia.
Å Gi «mer betydning» til ord med identiske prefikser gjorde jaro-Winkler-avstanden til å virke veldig interessant for vår brukstilfelle.
Starter fra begynnelsen Med jaro avstandsformelen, her hvordan det fungerer. Ikke panikk, vi går trinnvis:
Jaro-Avstanden mellom to sekvenser s1 og s2 er definert av:
dj er jaro-avstanden
m er antall matchende tegn (tegn som vises i s1 og i s2)
t er halvparten av antall transposisjoner (sammenlign i-th-tegnet til s1 og i-th-tegnet til s2 dividert med 2)
|s1| er lengden på den første strengen
|s2| er lengden på den andre strengen
med et eksempel. La oss ta «martha» og «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
Bare ved å erstatte tall er formelen, får vi:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
Nå vet vi Hva som er jaro-avstanden, la oss hoppe Til jaro-Winkler-avstanden.
jaro-Winkler-likheten bruker en prefiksskala p som gir gunstigere rangeringer til strenger som samsvarer fra begynnelsen for en angitt prefikslengde l.
p er en konstant skaleringsfaktor for hvor mye poengsummen justeres oppover for å ha felles prefikser. Standardverdien for denne konstanten i Winklers arbeid er p=0,1.
l er lengden på vanlig prefiks ved starten av strengen(opptil maksimalt 4 tegn).
så tilbake til» martha «/» marhta » – eksemplet, la oss ta et prefiks lengde på l = 3 (som refererer til «mar»). Vi kommer til:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
Ved Hjelp Av JaroWinkler-formelen går Vi fra jaro-avstanden ved 94% likhet med 96%.
i vårt tilfelle starter de fleste lignende apper med samme prefiks («twitter v1» vs «twitter v2″eller» ShazamIphone » vs «ShazamAndroid» etc. Se Algoritmene testing tabellen ovenfor). Så det er et viktig kriterium å ta hensyn til.
