badania i testy
przetestowaliśmy kilka algorytmów do porównania ciągów i wybraliśmy ten, który lepiej pasuje do naszych potrzeb.
porównaliśmy ciąg a i ciąg B, aby uzyskać metryki dotyczące różnych algorytmów.
reguły podobieństwa łańcuchów mogą się różnić w zależności od przypadku. Jeśli chcesz rozważyć „niszowe” i „chien” podobne, użyjesz algorytmu podobieństwa łańcuchów, który wykrywa anagramy. Nie w naszym przypadku. Aplikacja o nazwie „niche” i inna o nazwie „chien” są bardzo prawdopodobne, że dwie zupełnie różne aplikacje.
po burzy mózgów i badaniach wymyśliliśmy kilka metod algorytmów, które pomogłyby w naszej sprawie. Algorytm cosinusa okazał się dla nas nieistotny, gdyż np. nie bierze pod uwagę kolejności liter, co prowadzi do indeksu 1 (podobnego ciągu) NA anagramie („nisza” i „chien”).
oto, co zauważyliśmy:
algorytm Levenshteina
odległość Levenshteina to minimalna liczba jednoznakowych edycji wymaganych do zmiany jednego słowa na drugie, więc wynikiem jest dodatnia liczba całkowita, wrażliwa na długość łańcucha . Co utrudnia rysowanie wzoru.
na przykład,
- Levenshtein odległość między ” foo „i” bar „wynosi 3
- Levenshtein odległość między” beauties „i” beautiful „wynosi również 3
- dla nas, ludzi, para”beauties”/” beautiful „jest znacznie bardziej podobna niż para”foo”/” bar”. Ale odległość Levenshteina jest taka sama.
metryka, której tutaj używamy, jest odwrotnością odległości Levenshteina (1 / levenshtein_distance), więc wynik jest procentowy i jest przez nas łatwiejszy do odczytania. Ale problem, o którym mowa powyżej, pozostał ten sam.
gdzie 1 jest wynikiem porównania identycznych ciągów,” ShazamIphone „i” ShazamAndroid ” mają podobieństwo 0,167. „chien „i” niche ” mają podobieństwo 0,25.
tak więc z punktu widzenia algorytmu Levenshteina Chien / Niche są bardziej podobne niż”ShazamIphone”/” ShazamAndroid”, ponieważ potrzeba mniej zmian, aby dostać się z” chien „do” niche”, niż dostać się z” ShazamIphone „do”ShazamAndroid”.
porównanie Trygramu
algorytm trygramu to przypadek n-grama, ciąg N (w tym przypadku trzech) elementów z danej próbki. W naszym przypadku nazwa aplikacji jest próbką, a znak jest elementem.
tak więc Sekwencja „martha” ma 4 trygramy { mar art rth tha}.
możemy użyć metody trygram do porównania dwóch łańcuchów.
biorąc na przykład „martha” i to samo słowo z literówką, „marhta”, i możemy obliczyć ich trygramów:
Trygramów „martha”: { mar art RTH tha }
Trygramów „marhta”: { mar arh RHT hta }
aby zmierzyć podobieństwo dzielimy liczbę pasujących trygramów w obu ciągach: 1 { mar } według liczby unikalnych trygramów: 7 { mar art rth tha arh RHT hta }
The result is 1/7 = 14%
aby zrównoważyć wadę zewnętrznych znaków (nieco wzmocnić podobieństwo ciągów rozpoczynających się i kończących się tymi samymi trygramami), podkładamy ciąg z spacjami po obu stronach, co w tym przypadku w trzech kolejnych trygramów „_ma”, „ha_” i „ta_”.
Trygramów „martha”: {_ma Mar art RTH tha ha_ }
Trygramów ” marhta „: { _ma mar arh RHT HTA ta_ }
po wykonaniu tego, liczba pasujących trygramów wynosi do: 2 { _ma mar }
liczba wszystkich unikalnych trygramów: 9 { _ma mar art RTH tha arh RHT HTA ha_ }
The result is now 2/9 = 22%
korzystając z tej metody, aby porównać „Twitter v1” i „Twitter V2” mamy:
liczba pasujących trygramów: 7 { _tw twi wit itt tte ter er_ }
liczba wszystkich unikalnych trygramów: 11 { tw twi wit itt TTE ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
limit metody trygram do porównywania łańcuchów jest to, że krótkie łańcuchy z jednym (lub dwoma..) różne trygramy wydają się produkować mniejsze podobieństwo niż długie.
tak otrzymujemy 0.2 podobieństwo między „ShazamAndroid” i „ShazamIphone”, ponieważ mają więcej różnych trygramów.
liczba pasujących trygramów wynosi: 5 { _sh sha haz aza zam }
liczba wszystkich unikalnych trygramów: 20
ponieważ istnieje silna zależność z długością ciągu, nie daje to dobrego porównania dla nas.
algorytm Jaro-Winklera
„w informatyce i statystyce odległość Jaro-Winklera jest ciągową metryką służącą do pomiaru odległości między dwoma ciągami.
nieformalnie, odległość Jaro między dwoma wyrazami jest minimalną liczbą jednoznakowych transpozycji wymaganych do zmiany jednego słowa na drugie.
odległość Jaro-Winklera wykorzystuje skalę prefiksu, która daje korzystniejsze oceny ciągom, które pasują Od początku do zadanej długości prefiksu”
źródło: Wikipedia.
nadanie” większej wagi ” słowom z identycznymi przedrostkami sprawiło, że odległość Jaro-Winklera wydawała się bardzo interesująca dla naszego przypadku użycia.
zaczynając od początku od formuły odległości Jaro, oto jak to działa. Nie panikuj, idziemy krok po kroku:
odległość Jaro między dwoma sekwencjami s1 i s2 jest określona przez:
dj jest odległością Jaro
m jest liczbą pasujących znaków (znaków, które pojawiają się w s1 i w s2)
t jest połową liczby transpozycji (porównaj i-ten znak s1 i i-ten znak s2 podzielony przez 2)
|S1| jest długością pierwszego ciągu
|s2| jest długością drugiego ciągu
z exemple. Weźmy „Martę” i „marhtę”.
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
po prostu zastępując liczby otrzymujemy wzór:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
teraz wiemy, jaka jest odległość Jaro, przejdźmy do odległości Jaro-Winklera.
podobieństwo Jaro-Winklera wykorzystuje skalę prefiksu p, która daje bardziej korzystne oceny ciągom, które pasują Od początku do ustawionej długości prefiksu l.
p jest stałym współczynnikiem skalowania dla tego, o ile wynik jest skorygowany w górę za posiadanie wspólnych prefiksów. Standardową wartością tej stałej w pracy Winklera jest p = 0,1.
l jest długością wspólnego przedrostka na początku łańcucha (maksymalnie do 4 znaków).
wracając do przykładu” martha ” / „marhta”, weźmy przedrostek długości L = 3 (który odnosi się do”mar”). Dostajemy się do:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
korzystając ze wzoru Jarowinklera idziemy z odległości Jaro w 94% do 96%.
w naszym przypadku większość podobnych aplikacji zaczyna się od tego samego prefiksu („twitter v1” vs „twitter v2” lub „ShazamIphone” vs „ShazamAndroid” itp. Patrz tabela testowania algorytmów powyżej). Jest to więc ważne kryterium, które należy wziąć pod uwagę.
