Ricerca e test
Abbiamo testato diversi algoritmi per confrontare le stringhe e selezionato quello che meglio si adattava alle nostre esigenze.
Abbiamo confrontato la stringa A e la stringa B per avere metriche sui diversi algoritmi.
Le regole per la somiglianza delle stringhe possono differire da caso a caso. Se vuoi considerare” niche “e” chien ” simili, useresti un algoritmo di somiglianza delle stringhe che rileva gli anagrammi. Non nel nostro caso. Un’app denominata ” niche “e un’altra denominata” chien ” sono molto probabilmente due app completamente diverse.
Dopo alcuni brainstorming e ricerche abbiamo trovato alcuni metodi di algoritmo che avrebbero aiutato il nostro caso. L’algoritmo del coseno si è dimostrato irrilevante per noi, come ad esempio non sembra prendere in considerazione l’ordine delle lettere, che porta ad un indice di 1 (stringa simile) su un anagramma (“nicchia” e “chien”).
Ecco cosa abbiamo notato:
Algoritmo di Levenshtein
La distanza di Levenshtein è il numero minimo di modifiche a carattere singolo necessarie per cambiare una parola nell’altra, quindi il risultato è un numero intero positivo, sensibile alla lunghezza della stringa . Che rendono più difficile disegnare il modello.
Per esempio,
- la distanza di Levenshtein tra “foo” e “bar” è 3
- la distanza di Levenshtein tra “beauties” e “beautiful” è anche 3
- Per noi umani, la coppia “beauties”/”beautiful” è molto più simile alla coppia “foo”/”bar”. Ma la distanza di Levenshtein è la stessa.
La metrica che stiamo usando qui è l’inverso della distanza di Levenshtein ( 1 / levenshtein_distance ) quindi il risultato è una percentuale ed è più facilmente letto da noi. Ma il problema sopra menzionato è rimasto lo stesso.
Dove 1 è il risultato del confronto di stringhe identiche, “ShazamIphone” e “ShazamAndroid” hanno una somiglianza di 0,167. “chien” e “niche” hanno una somiglianza di 0,25.
Quindi dal punto di vista dell’algoritmo di Levenshtein Chien/Niche sono più simili di “ShazamIphone”/”ShazamAndroid” perché sono necessarie meno modifiche per passare da “chien” a “niche”, piuttosto che andare da “ShazamIphone” a “ShazamAndroid”.
Confronto trigramma
Un algoritmo trigramma è un caso di n-grammo, una sequenza contigua di n (tre, in questo caso) elementi da un dato campione. Nel nostro caso, il nome di un’applicazione è un esempio e un carattere è un elemento.
Quindi La sequenza “martha” ha 4 trigrammi { mar art rth tha}.
Possiamo usare il metodo Trigram per confrontare due stringhe.
Prendendo per esempio “marta” e la stessa parola con un errore di battitura, “marhta”, e siamo in grado di calcolare i trigrammi:
Trigrammi “martha”: { mar art rth tha }
Trigrammi “marhta”: { mar arh rht hta }
misurare la somiglianza dobbiamo dividere il numero di trigrammi in comune in entrambe le stringhe: 1 { mar } per il numero di trigrammi: 7 marzo }
The result is 1/7 = 14%
Per bilanciare lo svantaggio dei caratteri esterni (un po ‘ per rafforzare la somiglianza delle stringhe che iniziano e terminano con gli stessi trigrammi), riempiamo la stringa con spazi vuoti su entrambi i lati, risultando in questi casi in altri tre trigrammi “_ma”, “ha_” e “ta_”.
Trigrammi “martha”: {_ma mar art rth tha ha_ }
Trigrammi ” marhta “: { _ma mar arh rht hta ta_ }
Fatto questo, il numero di trigrammi corrispondenti è fino a: 2 { _ma mar }
Il numero di tutti i trigrammi unici: 9 { _ma mar art rth tha arh rht hta ha_ }
The result is now 2/9 = 22%
Utilizzando questo metodo per confrontare Twitter “v1” e “Twitter v2” abbiamo:
Il numero di matching trigrammi: 7 { _tw twi wit itt tte ter er_ }
Il numero di tutti unici trigrammi: 11 { tw twi wit itt tte ter er_ _v1 _v2 v1_ v2_ }
The result is 7/11 = 63%
Il limite del Trigramma metodo per confrontare le stringhe è che le corde con uno (o due..) diversi trigrammi tendono a produrre una somiglianza inferiore rispetto a quelli lunghi.
Ecco come otteniamo uno 0.2 somiglianza tra “ShazamAndroid” e “ShazamIphone”, in quanto hanno trigrammi più diversi.
Il numero di trigrammi corrispondenti è: 5 { _sh sha haz aza zam }
Il numero di tutti i trigrammi unici: 20
Poiché c’è una forte dipendenza con la lunghezza della stringa, non produce un buon confronto per noi.
Algoritmo di Jaro-Winkler
“In informatica e statistica, la distanza Jaro-Winkler è una metrica stringa per misurare la distanza di modifica tra due sequenze.
Informalmente, la distanza Jaro tra due parole è il numero minimo di trasposizioni a carattere singolo necessarie per cambiare una parola nell’altra.
La distanza Jaro-Winkler utilizza una scala di prefisso che fornisce valutazioni più favorevoli alle stringhe che corrispondono dall’inizio per una lunghezza di prefisso impostata”
Fonte: Wikipedia.
Dare “più importanza” alle parole con prefissi identici ha reso la distanza Jaro-Winkler molto interessante per il nostro caso d’uso.
Partendo dall’inizio con la formula della distanza di Jaro, ecco come funziona. Non fatevi prendere dal panico, andiamo passo per passo:
Il Jaro Distanza tra le due sequenze s1 e s2 è definito da:
dj è la Jaro distanza
m è il numero di caratteri corrispondenti (personaggi che compaiono in s1 e s2)
t è la metà del numero di trasposizioni (confrontare l’i-esimo carattere di s1 e l’i-esimo carattere di s2 diviso 2)
|s1| è la lunghezza della prima stringa
|s2| è la lunghezza della seconda stringa
Con un esempio. Prendiamo “martha” e “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
Solo sostituendo i numeri è la formula, otteniamo:
dj = (⅓) ( 6/6 + 6/6 + (6–1)/6) = ⅓ 17/6 = 0,944Jaro distance = 94,4%
Ora sappiamo qual è la distanza Jaro, saltiamo alla distanza Jaro-Winkler.
La somiglianza Jaro-Winkler utilizza una scala di prefisso p che fornisce valutazioni più favorevoli alle stringhe che corrispondono fin dall’inizio per una lunghezza di prefisso impostata l.
p è un fattore di scala costante per quanto il punteggio viene regolato verso l’alto per avere prefissi comuni. Il valore standard per questa costante nel lavoro di Winkler è p = 0.1.
l è la lunghezza del prefisso comune all’inizio della stringa (fino a un massimo di 4 caratteri).
Quindi torniamo all’esempio “martha”/ “marhta”, prendiamo una lunghezza prefisso di l = 3 (che si riferisce a “mar”). Arriviamo a:
dw = 0,944 + ( (0,1*3)(1–0,944)) = 0,944 + 0,3*0,056 = 0,961Jaro-Winkler distance = 96,1%
Usando la formula di JaroWinkler andiamo dalla distanza di Jaro al 94% di somiglianza al 96%.
Nel nostro caso, la maggior parte delle app simili inizia con lo stesso prefisso (“twitter v1” vs “twitter v2” o “ShazamIphone” vs “ShazamAndroid” ecc. Vedere la tabella di test degli algoritmi sopra). Quindi è un criterio importante da prendere in considerazione.
