Differenza tra distanza Jaro-Winkler e Levenshtein?

Question

Ho un caso d'uso in cui ho bisogno di fare la corrispondenza fuzzy di milioni di record da più file. Ho identificato due algoritmi per questo: Jaro-Winkler e Levenshtein modifica distanza.

Quando ho iniziato ad esplorare entrambi, non ero in grado di capire quale sia la differenza esatta tra i due. Sembra che Levenshtein dia il numero di modifiche tra due stringhe, e Jaro-Winkler dà un punteggio corrispondente tra 0.0 e 1.0. Non ho capito l'algoritmo. Poiché ho bisogno di usare entrambi gli algoritmi, ho bisogno di conoscere le differenze esatte rispetto alle prestazioni dell'algoritmo.

Answer 1

Levenshtein conta il numero di modifiche (inserzioni, eliminazioni o sostituzioni) necessarie per convertire una stringa in un'altra. Damerau-Levenshtein è una versione modificata che considera anche le trasposizioni come singole modifiche. Anche se l'uscita è il numero intero di modifiche, questo può essere normalizzata per dare un valore di similarità dalla formula

1 - (edit distance/length of the larger of the two strings) 

L'algoritmo Jaro è una misura di caratteri in comune, essendo non più di metà della lunghezza della più lunga stringa in distanza, con considerazione per le trasposizioni. Winkler ha modificato questo algoritmo per supportare l'idea che le differenze vicino all'inizio della stringa siano più significative delle differenze vicino alla fine della stringa. Jaro e Jaro-Winkler sono adatti per confrontare stringhe più piccole come parole e nomi.

Decidere quale usare non è solo una questione di prestazioni. È importante scegliere un metodo adatto alla natura delle stringhe che si stanno confrontando. In generale, comunque, entrambi gli algoritmi che hai citato possono essere costosi, perché ogni stringa deve essere confrontata con ogni altra stringa e con milioni di stringhe nel tuo set di dati, questo è un numero enorme di confronti. Questo è molto più costoso di qualcosa come calcolare una codifica fonetica per ogni stringa e quindi semplicemente raggruppare stringhe che condividono codifiche identiche.

C'è un'infinità di informazioni dettagliate su questi algoritmi e altri algoritmi di corrispondenza a stringa fuzzy su Internet. Questo vi darà un inizio:

A Comparison of Personal Name Matching: Techniques and Practical Issues

Secondo tale documento, la velocità dei quattro algoritmi di Jaro e Levenshtein che ho citato sono dal più veloce al più lento:

• Jaro
• Jaro-Winkler
• Levenshtein
• Damerau-Levenshtein

con il tempo più lento, da 2 a 3 volte il più veloce. Naturalmente questi tempi dipendono dalla lunghezza delle stringhe e dalle implementazioni e ci sono modi per ottimizzare questi algoritmi che potrebbero non essere stati utilizzati.