Nell'informatica e nella statistica, la similarità di Jaro-Winkler è una metrica per stringhe che misura la distanza di modifica (edit distance) tra due sequenze. Si tratta di una variante della metrica di distanza di Jaro proposta nel 1990 da William E. Winkler.

La distanza di Jaro-Winkler utilizza un coefficiente di prefisso che assegna valutazioni più favorevoli alle stringhe che trovano corrispondenza dall'inizio per una lunghezza di prefisso predeterminata. Testo in corsivo Maggiore è la distanza di Jaro-Winkler per due stringhe, minore è la loro similarità. Il valore della similarità viene normalizzato in modo tale che 0 indichi una corrispondenza esatta e 1 indichi l'assenza di similarità. L'articolo originale definiva infatti la metrica in termini di similarità, quindi la distanza è definita come l'inverso di tale valore (distanza = 1 − similarità).

Sebbene venga spesso definita come tale, la distanza di Jaro-Winkler non è una metrica nel senso matematico del termine, poiché non soddisfa la disuguaglianza triangolare.

Definizione

Similarità di Jaro La similarità di Jaro di due stringhe e è data da:

dove:

è la lunghezza di ; è il numero di simboli corrispondenti (vedi più avanti); è il numero di trasposizioni (vedi più avanti).

Il valore della similarità di Jaro è pari a 0 se le stringhe non hanno corrispondenza e pari a 1 se coincidono esattamente. Nella prima fase, ogni simbolo di viene confrontato con tutti i suoi simboli corrispondenti in . Due simboli di e rispettivamente, sono considerati corrispondenti solo se sono uguali e non distanti più di simboli.

Esempio Le seguenti due stringhe di lunghezza 9, FAREMVIEL e FARMVILLE, hanno 8 simboli corrispondenti. F, A e R si trovano nella stessa posizione in entrambe le stringhe. Inoltre, M, V, I, E e L sono distanti al massimo 3 simboli (risultato di ). Se non vengono trovati simboli corrispondenti, le stringhe non sono simili e l'algoritmo termina restituendo un valore di similarità pari a 0.

Se si trovano simboli corrispondenti diversi da zero, il passo successivo consiste nel calcolare il numero di trasposizioni. La trasposizione è il numero di simboli corrispondenti che non si trovano nell'ordine corretto diviso per due. Nell'esempio sopra riportato tra FAREMVIEL e FARMVILLE, E e L sono i simboli corrispondenti che non si trovano nell'ordine corretto. Quindi il numero di trasposizioni è uno.

Infine, dato il numero di simboli corrispondenti e il numero di trasposizioni , è possibile calcolare la similarità di Jaro tra FAREMVIEL e FARMVILLE:

Similarità di Jaro-Winkler La similarità di Jaro-Winkler utilizza un coefficiente di prefisso che assegna valutazioni più favorevoli alle stringhe che corrispondono dall'inizio per una lunghezza di prefisso prestabilita . Date due stringhe e , la loro similarità di Jaro-Winkler è:

dove:

è la similarità di Jaro per e è la lunghezza del prefisso comune all'inizio della stringa, fino a un massimo di 4 simboli è una costante fattore di scala che indica di quanto il valore vada aumentato in presenza di prefissi comuni. non dovrebbe superare 0,25 (ovvero 1/4, dove 4 è la lunghezza massima del prefisso considerato), altrimenti la similarità potrebbe diventare maggiore di 1. Il valore standard per questa costante nel lavoro di Winkler è

La distanza di Jaro-Winkler è definita come .

Sebbene spesso definita come metrica di distanza, la distanza di Jaro-Winkler non è una metrica nel senso matematico del termine, poiché non soddisfa la disuguaglianza triangolare. Inoltre, essa non soddisfa l'assioma di identità .

Relazione con altre metriche del tipo edit distance Esistono altre misure popolari del tipo edit distance, calcolate utilizzando un diverso insieme di operazioni di modifica ammesse. Ad esempio,

la distanza di Levenshtein consente la cancellazione, l'inserimento e la sostituzione; la distanza di Damerau-Levenshtein ammette l'inserimento, la cancellazione, la sostituzione e la trasposizione di due simboli adiacenti; la distanza della massima sottosequenza comune (LCS, longest common subsequence) consente solo l'inserimento e la cancellazione, non la sostituzione; la distanza di Hamming ammette solo la sostituzione, quindi si applica solo a stringhe della stessa lunghezza.

La edit distance è solitamente definita come una metrica parametrizzabile calcolata con un insieme specifico di operazioni di modifica consentite e un costo (possibilmente infinito) a assegnato ciascuna operazione. Tale strategia viene ulteriormente generalizzata negli algoritmi di allineamento di sequenze del DNA come l'algoritmo di Smith-Waterman, che fanno dipendere il costo di un'operazione dal punto in cui viene applicata.

Note

Bibliografia

Collegamenti esterni

- Implementazione in Python nel Natural Language Toolkit

Categoria:Metrica Categoria:Stringhe