cercetare și teste
am testat mai mulți algoritmi pentru a compara siruri de caractere, și selectat pe cel care s-ar potrivi mai bine nevoia noastră.
am comparat șirul A și șirul B pentru a avea valori asupra diferiților algoritmi.
regulile pentru similitudinea șirurilor pot diferi de la caz la caz. Dacă doriți să luați în considerare „nișă” și „chien” similare, ați folosi un algoritm de similitudine a șirului care detectează anagramele. Nu și în cazul nostru. O aplicație numită” nișă „și alta numită” chien ” sunt foarte probabil să fie două aplicații complet diferite.
după unele brainstorming și de cercetare am venit cu unele metode algoritm care ar ajuta cazul nostru. Algoritmul cosinusului s-a dovedit a fi irelevant pentru noi, deoarece, de exemplu, nu pare să țină cont de ordinea literelor, ceea ce duce la un index de 1 (șir similar) pe o anagramă („nișă” și „chien”).
Iată ce am observat:
algoritmul Levenshtein
distanța Levenshtein este numărul minim de modificări cu un singur caracter necesare pentru a schimba un cuvânt în celălalt, deci rezultatul este un număr întreg pozitiv, sensibil la lungimea șirului . Ceea ce face mai dificilă desenarea modelului.
de exemplu,
- distanța Levenshtein dintre „foo” și „bar” este de 3
- distanța Levenshtein dintre „frumuseți” și „frumoase”este, de asemenea, de 3
- pentru noi, oamenii, perechea”frumuseți”/”frumoase”este mult mai asemănătoare decât perechea”foo”/ „bar”. Dar distanța Levenshtein este aceeași.
metrica pe care o folosim aici este inversul distanței Levenshtein ( 1 / levenshtein_distance), astfel încât rezultatul este un procent și este mai ușor de citit de noi. Dar problema menționată mai sus a rămas aceeași.
unde 1 este rezultatul comparării șirurilor identice, „ShazamIphone” și „ShazamAndroid” au o asemănare de 0,167. „chien” și „nișă” au o asemănare de 0,25.
deci, din punct de vedere algoritmul Levenshtein Chien/nișă sunt mai asemănătoare decât „ShazamIphone”/”ShazamAndroid”, deoarece sunt necesare mai puține modificări pentru a obține de la „chien” la „nișă”, decât pentru a obține de la „ShazamIphone” la „ShazamAndroid”.
comparație Trigramă
un algoritm trigram este un caz de n-gram, o secvență contiguă de n (trei, în acest caz) articole dintr-un eșantion dat. În cazul nostru, un nume de aplicație este un eșantion și un caracter este un element.
deci secvența „martha”are 4 trigrame { mar art RTH tha}.
putem folosi metoda Trigram pentru a compara două șiruri de caractere.
luând de exemplu „martha” și același cuvânt cu o greșeală de scriere, „marhta”, și putem calcula trigramele lor:
trigrame „martha”: { mar art RTH tha }
trigrame „marhta”: { mar arh rht hta }
pentru a măsura similitudinea împărțim numărul de trigrame potrivite în ambele șiruri: 1 { mar } după numărul de trigrame unice: 7 { mar art rth tha arh rht hta }
The result is 1/7 = 14%
pentru a echilibra dezavantajul caracterelor exterioare (oarecum pentru a consolida similitudinea șirurilor care încep și se termină cu aceleași trigrame), tamponăm șirul cu spații libere pe ambele părți, rezultând în aceste cazuri încă trei trigrame „_ma”, „ha_” și „ta_”.
trigrame „martha”: {_ma mar art rth Tha ha_ }
trigrame „marhta”: {_ma mar arh rht hta ta_ }
după ce ați făcut acest lucru, numărul de trigrame potrivite este de până la: 2 { _ma mar }
Numărul tuturor trigramelor unice: 9 { _ma mar art rth tha arh rht hta ha_ }
The result is now 2/9 = 22%
folosind această metodă pentru a compara „Twitter v1” și „Twitter v2” avem:
numărul de trigrame potrivite: 7 { _tw twi wit itt tte ter er_ }
Numărul tuturor trigramelor unice: 11 { TW twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
limita metodei Trigram pentru a compara șirurile este că șirurile scurte cu unul (sau două..) trigramele diferite tind să producă o asemănare mai mică decât cele lungi.
așa obținem un 0.2 similitudine între „ShazamAndroid” și „ShazamIphone”, deoarece au mai multe trigrame diferite.
numărul de trigrame potrivite este: 5 { _sh sha haz aza zam }
Numărul tuturor trigramelor unice: 20
deoarece există o dependență puternică cu lungimea șirului, nu produce o comparație bună pentru noi.
algoritmul Jaro-Winkler
„în informatică și Statistică, distanța Jaro-Winkler este o metrică de șir pentru măsurarea distanței de editare dintre două secvențe.
informal, distanța Jaro dintre două cuvinte este numărul minim de transpuneri cu un singur caracter necesare pentru a schimba un cuvânt în celălalt.
distanța Jaro-Winkler folosește o scară de prefix care oferă ratinguri mai favorabile șirurilor care se potrivesc de la început pentru o lungime de prefix setată”
Sursa: Wikipedia.
acordarea „mai multă importanță” cuvintelor cu prefixe identice a făcut ca distanța Jaro-Winkler să pară foarte interesantă pentru cazul nostru de utilizare.
pornind de la început cu formula jaro distance, aici cum funcționează. Nu intrați în panică, mergem pas cu pas:
distanța Jaro dintre două secvențe s1 și s2 este definită de:
dj este distanța Jaro
m este numărul de caractere potrivite (caractere care apar în S1 și în S2)
t este jumătate din numărul de transpuneri (comparați caracterul i al lui s1 și caracterul i al lui s2 împărțit la 2)
|S1| este lungimea primului șir
|S2| este lungimea celui de-al doilea șir
cu un exemplu. Să luăm „martha” și „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
doar prin înlocuirea numerelor este formula, obținem:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
acum știm care este distanța Jaro, să sărim la distanța Jaro-Winkler.
similitudinea Jaro-Winkler folosește o scară de prefix p care oferă evaluări mai favorabile șirurilor care se potrivesc de la început pentru o lungime de prefix setată l.
p este un factor de scalare constant pentru cât de mult scorul este ajustat în sus pentru a avea prefixe comune. Valoarea standard pentru această constantă în lucrarea lui Winkler este p = 0,1.
l este lungimea prefixului comun la începutul șirului (până la maximum 4 caractere).
deci, înapoi la „martha”/ „marhta” exemplu, să luăm o lungime prefix De L = 3 (care se referă la „mar”). Ajungem la:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
folosind formula JaroWinkler mergem de la distanța Jaro la 94% similitudine la 96%.
în cazul nostru, majoritatea aplicațiilor similare încep cu același prefix („twitter v1” vs „twitter V2” sau „ShazamIphone” vs „ShazamAndroid” etc. Consultați tabelul de testare a algoritmilor de mai sus). Deci, este un criteriu important de luat în considerare.
