výzkum a testy
Testovali jsme několik algoritmů pro porovnání řetězců a vybrali jsme ten, který by lépe vyhovoval naší potřebě.
porovnali jsme řetězec A a řetězec B, abychom měli metriky na různých algoritmech.
pravidla pro podobnost řetězců se mohou případ od případu lišit. Pokud chcete považovat „niche “ a“ chien “ za podobné, použijte algoritmus podobnosti řetězců, který detekuje přesmyčky. Ne v našem případě. Aplikace s názvem „niche“ a další s názvem „chien“ budou velmi pravděpodobně dvě zcela odlišné aplikace.
po nějakém brainstormingu a výzkumu jsme přišli s některými algoritmickými metodami, které by pomohly našemu případu. Kosinový algoritmus se pro nás ukázal jako irelevantní, protože se například nezdá, že by zohledňoval pořadí písmen, které vede k indexu 1 (podobný řetězec) na přesmyčce („niche“ a „chien“).
zde je to, co jsme si všimli:
Levenshteinův algoritmus
Levenshteinova vzdálenost je minimální počet jednoznakových úprav potřebných ke změně jednoho slova na druhé, takže výsledkem je kladné celé číslo citlivé na délku řetězce . Což ztěžuje kreslení vzoru.
například,
- vzdálenost Levenshtein mezi “ foo “ a „bar“ je 3
- vzdálenost Levenshtein mezi „krásami“ a “ krásnými „je také 3
- pro nás, lidi, je pár“krásek“/“ krásných „mnohem podobnější než pár“foo“/“ bar“. Ale vzdálenost Levenshtein je stejná.
metrika, kterou zde používáme, je inverzní k Levenshteinově vzdálenosti (1 / levenshtein_distance), takže výsledek je procento a je pro nás snadněji čitelný. Výše uvedený problém však zůstal stejný.
kde 1 je výsledkem porovnání identických řetězců,“ ShazamIphone „a“ ShazamAndroid “ mají podobnost 0,167. „chien“ a „niche“ mají podobnost 0,25.
takže z pohledu levenshteinova algoritmu jsou Chien / Niche více podobné než „ShazamIphone“ / „ShazamAndroid“, protože je zapotřebí méně úprav, než se dostat z „shazamiphone“ na „ShazamAndroid“.
Trigram porovnání
trigram algoritmus je případ n-gram, souvislá sekvence n (tři, v tomto případě) položky z daného vzorku. V našem případě je název aplikace ukázkou a znak je položka.
takže sekvence „martha“ má 4 trigramy { mar art rth tha }.
pomocí Trigramové metody můžeme porovnat dva řetězce.
Vezmeme-li například „martha“ a stejné slovo s překlepem, „marhta“, a můžeme vypočítat jejich trigramy:
trigramy „martha“: {mar art rth tha }
trigramy „marhta“: { mar arh rht HTA }
pro měření podobnosti vydělíme počet odpovídajících trigramů v obou řetězcích: 1 { mar } počtem jedinečných trigramů: 7 { mar art rth tha arh rht hta }
The result is 1/7 = 14%
abychom vyvážili nevýhodu vnějších znaků (poněkud pro posílení podobnosti řetězců začínajících a končících stejnými trigramy), vložíme řetězec mezerami na obě strany, což v tomto případě vede k dalším třem trigramům „_ma“, “ ha_ “ a „ta_“.
trigramy „martha“: {_ma mar art rth Tha ha_ }
trigramy „marhta“: {_ma mar arh rht hta ta_ }
poté, co jste to udělali, je počet odpovídajících trigramů až: 2 { _ma mar }
počet všech jedinečných trigramů: 9 { _ma mar art rth tha arh rht HTA ha_ }
The result is now 2/9 = 22%
pomocí této metody k porovnání „Twitter v1“ a „Twitter v2“ máme:
počet odpovídajících trigramů: 7 { _tw twi wit itt tte ter er_ }
počet všech jedinečných trigramů: 11 { tw twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
limit Trigram metody pro porovnání řetězců je, že krátké řetězce s jedním (nebo dvěma..) různé trigramy mají tendenci produkovat nižší podobnost než dlouhé.
takto získáme 0.2 podobnost mezi „ShazamAndroid“ a „ShazamIphone“, protože mají více různých trigramů.
počet odpovídajících trigramů je: 5 { _sh sha haz aza zam }
počet všech jedinečných trigramů: 20
protože existuje silná závislost s délkou řetězce, nepřináší to pro nás dobré srovnání.
Jaro-Winklerův algoritmus
„v informatice a statistice je Jaro-Winklerova vzdálenost strunová metrika pro měření editační vzdálenosti mezi dvěma sekvencemi.
neformálně je vzdálenost jara mezi dvěma slovy minimální počet jednoznakových transpozic potřebných ke změně jednoho slova na druhé.
vzdálenost Jaro-Winkler používá stupnici prefixů, která dává příznivější hodnocení řetězcům, které od začátku odpovídají nastavené délce předpony“
zdroj: Wikipedia.
vzhledem k „větší důležitosti“ slovům se stejnými předponami se vzdálenost Jaro-Winkler jeví jako velmi zajímavá pro náš případ použití.
počínaje od začátku vzorcem Jaro distance, zde jak to funguje. Nepanikařte, jdeme krok za krokem:
vzdálenost jara mezi dvěma sekvencemi s1 a s2 je definována:
dj je vzdálenost jara
m je počet odpovídajících znaků (znaky, které se objevují v s1 a v s2)
t je polovina počtu transpozic (porovnejte i-tý znak s1 a i-tý znak s2 děleno 2)
|s1| je délka prvního řetězce
|S2 / je délka druhého řetězce
s příkladem. Vezměme si „Marthu“ a „marhtu“.
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
pouhým nahrazením čísel je vzorec, dostaneme:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
nyní víme, jaká je vzdálenost jara, skočíme na vzdálenost Jaro-Winkler.
podobnost Jaro-Winkler používá prefixovou stupnici p, která dává příznivější hodnocení řetězcům, které se od začátku shodují pro nastavenou délku předpony l.
p je konstantní měřítko pro to, o kolik je skóre upraveno směrem nahoru pro společné předpony. Standardní hodnota pro tuto konstantu v Winklerově práci je p=0,1.
l je délka společné předpony na začátku řetězce (maximálně 4 znaky).
takže zpět k příkladu „martha“ / „marhta“, Vezměme si délku předpony l = 3 (která odkazuje na „mar“). Dostáváme se k:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
pomocí jarowinklerova vzorce jdeme z vzdálenosti jara na 94% podobnosti s 96%.
v našem případě většina podobných aplikací začíná se stejnou předponou („twitter v1 „vs“ twitter v2 „nebo“ ShazamIphone „vs“ ShazamAndroid “ atd. Viz tabulka testování algoritmů výše). Je tedy důležitým kritériem, které je třeba vzít v úvahu.
