kutatás és tesztek
több algoritmust teszteltünk a karakterláncok összehasonlítására, és kiválasztottuk azt, amelyik jobban megfelel az igényeinknek.
összehasonlítottuk az A és a B karakterláncot, hogy a különböző algoritmusokon metrikák legyenek.
a húrok hasonlóságára vonatkozó szabályok esetenként eltérhetnek. Ha a “niche” – t és a “chien” – t hasonlónak szeretné tekinteni, akkor egy string hasonlósági algoritmust használ, amely felismeri az anagrammákat. A mi esetünkben nem. A “niche” és egy másik “chien” nevű alkalmazás valószínűleg két teljesen különböző alkalmazás.
némi brainstorming és kutatás után előálltunk néhány algoritmus módszerrel, ami segíthet az ügyünkben. A koszinusz algoritmus irrelevánsnak bizonyult számunkra, mivel például úgy tűnik, hogy nem veszi figyelembe a betűrendet, ami 1-es indexhez vezet (hasonló karakterlánc) egy anagrammán (“niche” és “chien”).
itt van, amit észrevettünk:
Levenshtein algoritmus
a Levenshtein-távolság az egykarakteres szerkesztések minimális száma, amely az egyik szó megváltoztatásához szükséges, így az eredmény pozitív egész szám, érzékeny a karakterlánc hosszára . Ami megnehezíti a minta rajzolását.
például,
- a “foo” és a “bar” közötti Levenshtein-távolság 3
- a “szépségek” és a “gyönyörű” közötti Levenshtein-távolság szintén 3
- számunkra, emberek számára a “szépségek”/”gyönyörű” pár sokkal hasonlóbb, mint a “foo”/”bár” pár. De a Levenshtein távolság ugyanaz.
az itt használt metrika a Levenshtein-távolság inverze ( 1 / levenshtein_distance), így az eredmény egy százalék, és könnyebben olvasható. De a fent említett probléma ugyanaz maradt.
ahol az 1 az azonos húrok összehasonlításának eredménye, a “ShazamIphone” és a “ShazamAndroid” hasonlósága 0,167. a “Chien” és a “niche” hasonlósága 0,25.
tehát a Levenshtein algoritmus szempontjából a Chien / Niche jobban hasonlít, mint a”ShazamIphone”/” ShazamAndroid”, mert kevesebb szerkesztésre van szükség a” chien “- től a” niche “- ig, mint a” ShazamIphone “- tól a”ShazamAndroid” – ig.
Trigram összehasonlítás
a trigram algoritmus az n-gram esete, egy adott minta n (három, ebben az esetben) elemének összefüggő szekvenciája. Esetünkben az alkalmazás neve minta, a karakter pedig elem.
tehát a “martha” szekvenciának 4 trigrama van { Mar art rth tha }.
használhatjuk a Trigram módszert két karakterlánc összehasonlítására.
Vegyük például a “martha” szót és ugyanazt a szót egy elírással, a “marhta” szót, és kiszámíthatjuk a trigramjaikat:
trigramok “martha”: { Mar art rth tha }
trigramok “marhta”: { mar arh rht hta }
a hasonlóság mérésére elosztjuk az egyező trigramok számát mindkét húrban: 1 { mar } az egyedi trigramok számával: 7 { mar art rth tha arh rht hta }
The result is 1/7 = 14%
a külső karakterek hátrányának kiegyenlítése érdekében (némileg megerősítve az azonos trigramokkal kezdődő és végződő karakterláncok hasonlóságát) a karakterláncot mindkét oldalon üres lapokkal töltjük be, ami ebben az esetben három további trigramot eredményez: “_ma”, “ha_” és “ta_”.
trigrams “martha”: { _ma Mar art rth Tha ha_ }
Trigrams “marhta”: { _ma mar arh rht hta ta_ }
miután ezt megtette, az egyező trigramok száma legfeljebb: 2 { _ma mar }
az összes egyedi trigram száma: 9 { _ma Mar art rth tha arh rht hta ha_ }
The result is now 2/9 = 22%
ezzel a módszerrel a “Twitter v1” és a “Twitter v2” összehasonlításához:
a megfelelő trigramok száma: 7 { _tw twi wit itt tte ter er_ }
az összes egyedi trigram száma: 11 { tw twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
a trigram módszer határa a húrok összehasonlítására az, hogy rövid húrok egy (vagy kettővel..) a különböző trigramok általában alacsonyabb hasonlóságot mutatnak, mint a hosszúak.
így kapunk 0-t.2 hasonlóság a “ShazamAndroid” és a “ShazamIphone” között, mivel több különböző trigramm van.
az egyező trigramok száma: 5 { _sh sha haz aza zam }
az összes egyedi trigram száma: 20
mivel erős függőség van a húr hosszától, ez nem eredményez jó összehasonlítást számunkra.
Jaro-Winkler algoritmus
“a számítástechnikában és a statisztikában a Jaro-Winkler-távolság egy karakterlánc-mutató, amely két szekvencia közötti szerkesztési távolságot méri.
informálisan a Jaro két szó közötti távolság az egykarakteres átültetések minimális száma, amely szükséges az egyik szó másikra váltásához.
a Jaro-Winkler távolság előtagskálát használ, amely kedvezőbb besorolást ad azoknak a karakterláncoknak, amelyek a kezdetektől egyeznek egy meghatározott előtaghosszig”
forrás: Wikipedia.
az azonos előtagú szavaknak “nagyobb jelentőséget” adva a Jaro-Winkler távolság nagyon érdekesnek tűnt a használati esetünkben.
az elejétől kezdve a Jaro távolság képlettel, itt hogyan működik. Ne ess pánikba, lépésről lépésre haladunk:
a Jaro távolságot két S1 és s2 szekvencia határozza meg:
dj a Jaro távolság
m az egyező karakterek száma (az s1-ben és az s2-ben megjelenő karakterek)
t az átültetések számának fele (hasonlítsa össze az s1 i-edik karakterét és az s2 i-edik karakterét osztva 2-vel)
|s1| Az első karakterlánc hossza
|s2| a második karakterlánc hossza
példával. Vegyük a “martha” – t és a”marhta” – t.
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
csak a számok cseréjével kapjuk a képletet:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
most már tudjuk, mi a Jaro távolság, ugorjunk a Jaro-Winkler távolságra.
a Jaro-Winkler hasonlóság előtagskálát használ p amely kedvezőbb besorolást ad azoknak a karakterláncoknak, amelyek a kezdetektől egyeznek egy meghatározott előtaghosszra l.
p állandó méretezési tényező arra vonatkozóan, hogy a pontszámot mennyivel felfelé állítják be a közös előtagokhoz. Ennek az állandónak a standard értéke Winkler munkájában p=0,1.
l a közös előtag hossza a karakterlánc elején (legfeljebb 4 karakter).
tehát vissza a” martha “/” marhta “példa, Vegyünk egy előtag hossza l = 3 (ami arra utal, hogy”mar”). Eljutunk:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
a JaroWinkler képlet segítségével a Jaro távolságból 94% – os hasonlósággal 96% – ra megyünk.
esetünkben a legtöbb hasonló alkalmazás ugyanazzal az előtaggal kezdődik (“twitter v1” vs “twitter v2” vagy “ShazamIphone” vs “ShazamAndroid” stb. Lásd a fenti algoritmusok tesztelési táblázatát). Ezért fontos szempont, amelyet figyelembe kell venni.
