forskning og test
vi testede flere algoritmer til at sammenligne strenge og valgte den, der bedre passer til vores behov.
vi sammenlignede streng A og streng B for at have målinger på de forskellige algoritmer.
regler for strenglighed kan variere fra sag til sag. Hvis du vil overveje “niche” og “chien” lignende, vil du bruge en strenglighedsalgoritme, der registrerer anagrammer. Ikke i vores tilfælde. En app ved navn” niche “og en anden ved navn” chien ” er meget sandsynligt to helt forskellige apps.
efter nogle brainstorming og forskning kom vi op med nogle algoritme metoder, der ville hjælpe vores sag. Cosinusalgoritmen viste sig at være irrelevant for os, da den for eksempel ikke ser ud til at tage hensyn til bogstavrækkefølgen, hvilket fører til et indeks på 1 (lignende streng) på et anagram (“niche” og “chien”).
her er hvad vi bemærkede:
Levenshtein-algoritme
Levenshtein-afstanden er det mindste antal redigeringer med enkelt tegn, der kræves for at ændre det ene ord til det andet, så resultatet er et positivt heltal, følsomt over for strenglængde . Hvilket gør det sværere at tegne mønster.
for eksempel,
- Levenshtein-afstanden mellem” foo “og” bar “er 3
- Levenshtein-afstanden mellem” skønheder “og” smukke “er også 3
- for os mennesker er”skønheder”/” smukke “par meget mere ens end”foo”/” bar ” – parret. Men Levenshtein-afstanden er den samme.
den metriske, vi bruger her, er den inverse af Levenshtein-afstanden ( 1 / levenshtein_distance), så resultatet er en procentdel og læses lettere af os. Men ovennævnte problem forblev det samme.
hvor 1 er resultatet af at sammenligne identiske strenge, “Shasamiphone” og “Shasamandroid” har en lighed på 0,167. “chien” og “niche” har en lighed på 0,25.
så fra Levenshtein-algoritmens synspunkt er Chien/Niche mere ens end “Shasamiphone”/”Shasamandroid”, fordi færre redigeringer er nødvendige for at komme fra “chien” til “niche” end at komme fra “Shasamiphone” til “Shasamandroid”.
Trigram sammenligning
en trigram algoritme er et tilfælde af n-gram, en sammenhængende sekvens af n (tre, i dette tilfælde) elementer fra en given prøve. I vores tilfælde er et applikationsnavn en prøve, og et tegn er et element.
så sekvensen “martha” har 4 trigrammer { mar art RTH tha }.
vi kan bruge Trigram-metoden til at sammenligne to strenge.
tager for eksempel “martha” og det samme ord med en skrivefejl, “marhta”, og vi kan beregne deres trigrammer:
trigrammer “martha”: { mar art rth tha }
trigrammer “marhta”: { mar arh rht hta }
for at måle lighed deler vi antallet af matchende trigrammer i begge strenge: 1 { Mar } ved antallet af unikke trigrammer: 7 { mar art RTH tha arh RHT MTV }
The result is 1/7 = 14%
for at afbalancere ulempen ved de ydre tegn (noget for at forstærke ligheden mellem strenge, der starter og slutter med de samme trigrammer), padler vi strengen med emner på begge sider, hvilket resulterer i disse tilfælde i yderligere tre trigrammer “_ma”, “ha_” og “ta_”.
trigrammer “martha”: {_ma mar art RTH Tha ha_ }
trigrammer “marhta”: {_ma mar arh RHT hta ta_ }
efter at have gjort det, er antallet af matchende trigrammer op til: 2 { _ma mar }
antallet af alle unikke trigrammer: 9 { _ma mar art RTH tha arh rht hta ha_ }
The result is now 2/9 = 22%
ved hjælp af denne metode til at sammenligne “kvidre v1” og “kvidre v2” har vi:
antallet af matchende trigrammer: 7 {_VV med itt tte ter ER_ }
antallet af alle unikke trigrammer: 11 { tv VV med itt tte ter ER_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
grænsen for Trigram-metoden til at sammenligne strenge er, at korte strenge med en (eller to..) forskellige trigrammer har tendens til at producere en lavere lighed end lange.
Sådan får vi et 0.2 lighed mellem” Shasamandroid “og” Shasamiphone”, da de har flere forskellige trigrammer.
antallet af matchende trigrammer er: 5 { _sh sha haha haha haha}
antallet af alle unikke trigrammer: 20
da der er en stærk afhængighed med strenglængde, giver det ikke en god sammenligning for os.
Jørgensen-Jørgensen
“i datalogi og statistik, den Jaro-vinkler afstand er en streng metrisk til måling af redigeringsafstanden mellem to sekvenser.
uformelt er Jaro-afstanden mellem to ord det mindste antal transpositioner med et tegn, der kræves for at ændre det ene ord til det andet.
Jaro-Blinkler-afstanden bruger en præfiksskala, der giver mere gunstige ratings til strenge, der matcher fra starten for en indstillet præfikslængde”
kilde:
at give “mere betydning” til ord med identiske præfikser fik Jaro-vinkler-afstanden til at virke meget interessant for vores brugssag.
fra begyndelsen med Jaro-afstandsformlen, her hvordan det fungerer. Gå ikke i panik, vi går trin for trin:
Jaro-afstanden mellem to sekvenser s1 og s2 er defineret af:
dj er Jaro-afstanden
m er antallet af matchende tegn (tegn, der vises i s1 og i s2)
t er halvdelen af antallet af transpositioner (sammenlign det i-TH tegn af s1 og det i-TH tegn af s2 divideret med 2)
|s1| er længden af den første streng
|s2| er længden af den anden streng
med et eksempel. Lad os tage “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 at erstatte tal er formlen, får vi:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
nu ved vi, hvad der er Jaro-afstanden, lad os hoppe til Jaro-vinkler-afstanden.
Jaro-vinkler-ligheden bruger en præfiksskala p, der giver mere gunstige ratings til strenge, der matcher fra starten for en indstillet præfikslængde l.
p er en konstant skaleringsfaktor for, hvor meget scoren justeres opad for at have fælles præfikser. Standardværdien for denne konstant i Vinklers arbejde er p=0,1.
l er længden af fælles præfiks i starten af strengen (op til maksimalt 4 tegn).
så tilbage til eksemplet “martha”/ “marhta”, lad os tage en præfikslængde på l = 3 (som henviser 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 hjælp af Jaroinkler-formlen går vi fra Jaro-afstanden med 94% lighed med 96%.
i vores tilfælde starter de fleste af lignende apps med det samme præfiks (“kvidre v1” vs “kvidre v2” eller “Shasamiphone” vs “Shasamandroid” osv. Se tabellen over test af algoritmer ovenfor). Så det er et vigtigt kriterium at tage hensyn til.
