tutkimus ja testit
testasimme useita algoritmeja merkkijonojen vertailuun ja valitsimme sen, joka sopisi paremmin tarpeeseemme.
vertailimme merkkijonoa A ja merkkijonoa B, jotta eri algoritmeilla olisi mittareita.
merkkijonojen samankaltaisuutta koskevat säännöt voivat vaihdella tapauskohtaisesti. Jos haluat harkita ”niche” ja ”chien” samankaltaisia, voit käyttää merkkijonon samankaltaisuus algoritmi, joka tunnistaa anagrammeja. Ei meidän tapauksessamme. Sovellus nimeltä ” niche ”ja toinen nimeltään” chien ” ovat hyvin todennäköisesti kaksi täysin eri sovelluksia.
muutaman aivoriihen ja tutkimuksen jälkeen keksimme algoritmimenetelmiä, jotka auttaisivat juttuamme. Kosinialgoritmi osoittautui meille epäolennaiseksi, sillä se ei esimerkiksi näytä ottavan huomioon kirjainjärjestystä, joka johtaa indeksiin 1 (samanlainen merkkijono) anagrammissa (”niche” ja ”chien”).
tässä on mitä huomasimme:
Levenshteinin algoritmi
Levenshteinin etäisyys on vähimmäismäärä yhden merkin muokkauksia, joita tarvitaan yhden sanan vaihtamiseksi toiseen, joten tuloksena on positiivinen kokonaisluku, joka on herkkä merkkijonon pituudelle . Jotka vaikeuttavat kuvion piirtämistä.
esimerkiksi,
- levenshteinin etäisyys ”foo”: n ja ”bar”: n välillä on 3
- Levenshteinin etäisyys ”beautiesin” ja ”Beautifulin” välillä on myös 3
- meille ihmisille ”beauties”/”beautiful” – pari on paljon samankaltaisempi kuin ”foo”/”bar” – pari. Mutta Levenshteinin etäisyys on sama.
tässä käyttämämme metriikka on Levenshtein-etäisyyden käänteisluku (1 / levenshtein_detäisyys), joten tulos on prosenttiluku ja me voimme helpommin lukea sen. Mutta edellä mainittu ongelma pysyi samana.
missä 1 on identtisten merkkijonojen vertailun tulos, ”Shazamifonin” ja ”Shazamandroidin” samankaltaisuus on 0,167. ”chien” ja ”niche” ovat samankaltaiset 0,25.
joten Levenshteinin algoritmin näkökulmasta Chien/Niche ovat enemmän samanlaisia kuin ”ShazamIphone”/”ShazamAndroid”, koska vähemmän muokkauksia tarvitaan ”chienistä” ”kapeaan”, kuin ”Shazamiphonesta” ”shazamandroidiin”.
Trigrammivertailu
trigrammialgoritmi on n-gramman tapaus, joka on yhtäjaksoinen sarja n (tässä tapauksessa kolme) alkiota annetusta näytteestä. Meidän tapauksessamme sovelluksen nimi on näyte ja merkki on kohde.
joten järjestyksessä ”martha”on 4 trigrammia { mar art rth tha }.
Trigram-menetelmällä voidaan verrata kahta merkkijonoa.
ottaen esimerkiksi ”martha” ja saman sanan kirjoitusvirheellä ”marhta”, ja voimme laskea niiden trigrammit:
trigrammit ”martha”: { mar art rth tha }
trigrammit ”marhta”: { mar arh rht hta }
samankaltaisuuden mittaamiseksi jaamme vastaavien trigrammien määrän molempiin kieliin: 1 { Mar } määrä ainutlaatuinen trigrammit: 7 { mar art rth tha arh rht hta }
The result is 1/7 = 14%
tasapainottamiseksi haitta ulompi merkkiä (jonkin verran vahvistaa samankaltaisuutta merkkijonojen alkaa ja päättyy samalla trigrammit), me pad merkkijono aihioita molemmin puolin, jolloin näissä tapauksissa kolme enemmän trigrammit ”_ma”, ”ha_” ja ”ta_”.
trigrammit ”martha”: {_ma mar art rth tha ha_ }
trigrammit ”marhta”: {_ma mar arh rht HTA ta_ }
sen jälkeen vastaavien trigrammien lukumäärä on enintään: 2 { _ma mar }
kaikkien yksilöllisten trigrammien lukumäärä: 9 { _mar art RTH Tha arh rht hta ha_ }
The result is now 2/9 = 22%
käyttämällä tätä menetelmää vertaamalla ”Twitter v1 ”ja” Twitter v2 ” meillä on:
vastaavien trigrammien määrä: 7 { _tw twi wit itt tte tte er_ }
kaikkien yksilöllisten trigrammien määrä: 11 { TW twi wit itt tte tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
trigram-menetelmän raja merkkijonojen vertailuun on, että lyhyitä merkkijonoja on yksi (tai kaksi..) eri trigrammeilla on taipumus tuottaa matalampaa samankaltaisuutta kuin pitkillä.
näin saadaan 0.2 samankaltaisuus ”Shazamandroidin” ja ”Shazamiphonen” välillä, koska niillä on enemmän erilaisia trigrammeja.
vastaavien trigrammien määrä on: 5 { _sh sha haz aza Zam }
kaikkien yksilöllisten trigrammien määrä: 20
koska on olemassa vahva riippuvuus merkkijonon pituudesta, se ei anna meille hyvää vertailukohtaa.
Jaro-Winklerin algoritmi
”tietojenkäsittelytieteessä ja tilastotieteessä Jaro-Winkler-etäisyys on merkkijonometri, jolla mitataan kahden sekvenssin välistä edit-etäisyyttä.
epävirallisesti Jaro-välimatka kahden sanan välillä on vähimmäismäärä yhden merkin transpositioita, jotka vaaditaan yhden sanan vaihtamiseksi toiseen.
Jaro-Winkler-etäisyydessä käytetään etuliitteasteikkoa, joka antaa suotuisammat arvosanat merkkijonoille, jotka täsmäävät alusta alkaen tietyn etuliitteen pituuteen”
lähde: Wikipedia.
”suuremman merkityksen” antaminen sanoille, joilla on identtiset etuliitteet, sai Jaro-Winkler-välimatkan tuntumaan käyttötapauksemme kannalta erittäin mielenkiintoiselta.
alusta alkaen Jaron etäisyyskaavalla, näin se toimii. Don ’ t panic, we go step by step:
Jaron etäisyys kahden sarjan s1 ja s2 on määritelty:
dj on Jaron etäisyys
m on vastaavien merkkien määrä (merkit, jotka esiintyvät S1: ssä ja S2: ssa)
t on puolet transpositioiden määrästä (vertaa s1: n i: s merkki ja S2: n i: s merkki jaettuna 2: lla)
|s1| on ensimmäisen merkkijonon pituus
|s2| on toisen merkkijonon pituus
exemplellä. Otetaan ”Martta”ja ” 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
vain korvaamalla numerot on kaava, saamme:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
nyt tiedämme, mikä on Jaro etäisyys, hypätään Jaro-Winkler etäisyys.
Jaro-Winkler-samankaltaisuudessa käytetään etuliitteasteikkoa P, joka antaa suotuisammat arvosanat merkkijonoille, jotka täsmäävät alusta alkaen asetetun etuliitteen pituudelle l.
P on vakio skaalauskerroin sille, kuinka paljon pistemäärää säädetään ylöspäin, jotta niillä on yhteiset etuliitteet. Tämän vakion vakioarvo Winklerin työssä on p=0,1.
l on merkkijonon alussa olevan yhteisen etuliitteen pituus (enintään 4 merkkiä).
joten takaisin ”martha”/ ”marhta” esimerkki, otetaan etuliite pituus L = 3 (joka viittaa ”mar”). Saamme:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
käyttämällä JaroWinkler kaava menemme Jaro etäisyys 94% samankaltaisuus 96%.
meidän tapauksessamme suurin osa vastaavista sovelluksista alkaa samalla etuliitteellä (”twitter v1” vs ”twitter v2” tai ”ShazamIphone” vs ”ShazamAndroid” jne. Katso algoritmien testaustaulukko yllä). Se on siis tärkeä huomioon otettava kriteeri.
