Confronta algoritmi di similarità

Question

Voglio usare le funzioni di similarità delle stringhe per trovare dati corrotti nel mio database.

mi sono imbattuto in alcuni di loro:

• Jaro,
• Jaro-Winkler,
• Levenshtein,
• euclidea e
• Q-gram,

I volevo sapere qual è la differenza tra loro e in quali situazioni funzionano meglio?

Answer 1

Espandere sul mio commento wiki-walk nell'errata e noting some of the ground-floor literature on the comparability of algorithms that apply to similar problem spaces, esploriamo l'applicabilità di questi algoritmi prima di determinare se sono numericamente comparabili.

Da Wikipedia, Jaro-Winkler:

In informatica e statistica, la distanza di Jaro-Winkler (Winkler, 1990) è una misura di somiglianza tra due stringhe.È una variante della metrica distanza di Jaro (Jaro, 1989, 1995) e principalmente [citazione necessaria] utilizzata nell'area del collegamento del record (rilevamento duplicato ). Maggiore è la distanza di Jaro-Winkler per due stringhe, più simili sono le stringhe. La metrica della distanza di Jaro-Winkler è progettata e più adatta per stringhe brevi come i nomi di persone. Il punteggio è normalizzato in modo tale che 0 equivale a nessuna somiglianza e 1 è una corrispondenza esatta .

Levenshtein distance:

In teoria dell'informazione e informatica, la distanza Levenshtein è una stringa metrica per misurare la quantità di differenza tra due sequenze . Il termine modifica distanza è spesso usato per riferirsi specificamente a a distanza Levenshtein.

La distanza Levenshtein tra due stringhe è definito come il minimo numero di modifiche necessarie per trasformare una stringa nell'altra, con le operazioni di modifica ammissibile essendo inserzione, delezione o sostituzione di un singolo carattere. Prende il nome da Vladimir Levenshtein, che ha considerato questa distanza nel 1965.

Euclidean distance:

In matematica, la distanza euclidea o la metrica euclidea è la distanza "ordinario" tra due punti che ci si misurare con un righello e viene fornito dalla formula di Pitagora. Usando questa formula come distanza, lo spazio euclideo (o anche qualsiasi spazio interno del prodotto) diventa uno spazio metrico. La norma associata è chiamata norma euclidea. La letteratura più vecchia si riferisce alla metrica come metrica pitagorica.

E Q- or n-gram encoding:

Nei campi della linguistica computazionale e probabilità, un n-gram è una sequenza contigua di n elementi da una data sequenza di testo o discorso. Gli articoli in questione possono essere fonemi, sillabe, lettere, parole o coppie di basi in base all'applicazione. n-grammi sono raccolti da un testo o un corpus vocale.

Il nucleo due vantaggi dei modelli n-grammi (e algoritmi che utilizzano loro) sono relativa semplicità e la possibilità di scalare fino - semplicemente aumentando na modello può essere utilizzato per memorizzare più rapida con un ben Compreso il compromesso spazio-tempo, consentendo piccoli esperimenti a scalare in modo molto efficiente.

Il problema è questi algoritmi risolvono diversi problemi che hanno applicabilità diversa entro lo spazio di tutti gli algoritmi possibili per risolvere il problema longest common subsequence, nei dati o in un innesto utilizzabile metric stessa. In realtà, non tutte queste sono anche le misure , poiché alcune di esse non soddisfano lo triangle inequality.

Invece di andare dal tuo modo di definire uno schema di dubbia per rilevare la corruzione dei dati, farlo correttamente: utilizzando checksums e parity bits per i vostri dati. Non cercare di risolvere un problema molto più difficile quando una soluzione più semplice farà.

Answer 2

La somiglianza delle stringhe aiuta in molti modi diversi. Ad esempio

• Google intendeva dire che i risultati vengono calcolati utilizzando la somiglianza delle stringhe.
• la somiglianza della stringa viene utilizzata per correggere gli errori OCR.
• somiglianza stringa viene utilizzata per correggere errori di immissione della tastiera.
• somiglianza stringa viene utilizzata per trovare la sequenza più corrispondente di due DNA in bioinformatica.

Ma come una taglia non va bene per tutti. Ogni algoritmo di similarità delle stringhe è progettato per un utilizzo specifico sebbene la maggior parte di esse sia simile. Ad esempio Levenshtein_distance indica il numero di caratteri che si modificano per rendere uguali due stringhe.

kitten → sitten 

Qui la distanza è di 1 carattere. È possibile assegnare pesi diversi a cancellazione, aggiunta e sostituzione. Ad esempio, errori OCR ed errori di tastiera danno meno peso per alcune modifiche. OCR (alcuni caratteri sono molto simili agli altri), alcuni caratteri sono molto vicini l'uno all'altro. La somiglianza delle corde bioinformatiche consente un sacco di inserimenti.

tuo secondo esempio di "distanza Jaro–Winkler metrica è stato progettato e più adatto per le stringhe brevi come nomi di persona"

quindi si dovrebbe tenere in mente circa il tuo problema.

Desidero utilizzare le funzioni di similarità delle stringhe per trovare dati danneggiati nel mio database.

Come sono danneggiati i dati? Si tratta di un errore dell'utente, simile all'errore di input della tastiera? O è simile agli errori OCR? O qualcos'altro interamente?