Domanda Differenza tra distanza Jaro-Winkler e Levenshtein? [chiuso]


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 la 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.


44
2017-08-28 04:10


origine


risposte:


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. Sebbene l'output sia il numero intero di modifiche, questo può essere normalizzato per fornire un valore di similarità in base alla formula

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

L'algoritmo Jaro è una misura di caratteri in comune, non più della metà della lunghezza della stringa più lunga 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'è una ricchezza di informazioni dettagliate su questi algoritmi e altri algoritmi di corrispondenza a stringa fuzzy su Internet. Questo ti darà un inizio:

Un confronto tra il nome personale Abbinamento: tecniche e pratiche Problemi

Secondo quel documento, la velocità dei quattro algoritmi Jaro e Levenshtein che ho citato sono da quelli più veloci a quelli più lenti:

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

con il 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.


98
2017-08-28 04:51