Corrispondenza approssimativa delle stringhe

Question

So che questa domanda è stata posta molto tempo. Voglio un suggerimento su quale algoritmo è adatto per la corrispondenza approssimativa delle stringhe.

L'applicativo è specifico per nome dell'azienda corrispondenza solo e nient'altro.

La sfida più grande è probabilmente la parte nome dell'azienda end e brevi nominato parte Esempio: 1. CompanyA Pty Ltd vs CompanyA PTY. ltd. vs companyA 2. WES Engineering vs W.E.S. Engineering (occurance estremamente raro)

Pensi Levenshtein Edit La distanza è adeguata?

sto usando C#

saluti, Max

Answer 1

Esistono varie metriche sulla distanza delle stringhe che è possibile utilizzare.

mi sento di raccomandare Jaro-Winkler. A differenza di edit-distance, dove il risultato di un confronto è in unità discrete di modifiche, JW ti dà un punteggio di 0-1. È particolarmente adatto per nomi propri. Anche guardare this nice tutorial e this SO question.

Non ho lavorato con C#, ma qui ci sono alcune implementazioni di JW ho trovato online:

Impl 1 (hanno una versione DOT NET anche se si guarda l'elenco di file)

Impl 2

---

Se si vuole fare un po 'più sofisticato di corrispondenza, si può provare a fare un po' la normalizzazione personalizzata di forme di parole comunemente si verificano in nomi di società come ad esempio ltd/limited, inc/incorporated, corp/corporation per tenere conto di caso insensibilità, abbreviazioni ecc In questo modo, se si calcola

distance (normalize("foo corp."), normalize("FOO CORPORATION"))

si dovrebbe ottenere il risultato di essere 0 invece di 14 (che è quello che si otterrebbe se si calcolo levenshtein edit-distance).

Answer 2

Sì, Levenshtein distanza è adatto a questo. Funzionerà per tutti quelli che hai elencato almeno.

Si potrebbe anche eventualmente utilizzare Soundex, ma non credo che ne avrai bisogno.

Answer 3

In questi semplici esempi, la semplice rimozione di tutti i caratteri non alfanumerici offre una corrispondenza ed è la più semplice da eseguire in quanto è possibile eseguire il calcolo preliminare dei dati su ciascun lato, quindi eseguire una corrispondenza diretta uguale che sarà molto più veloce della moltiplicazione incrociata e del calcolo della distanza di modifica.

Answer 4

Ho già fornito la mia risposta in un'altra domanda.

https://stackoverflow.com/a/30120166/2282794

Ho lavorato sul sistema davvero vasta scala con nome corrispondente requisiti simili che hai parlato. La corrispondenza dei nomi non è molto semplice e l'ordine del nome e del cognome potrebbe essere diverso. Gli algoritmi di corrispondenza dei nomi fuzzy falliscono miseramente in tali scenari.

Se vogliamo solo parlare degli algoritmi di corrispondenza delle stringhe approssimative, ce ne sono molti. Pochi di loro sono: Jaro-Winkler, Modifica distanza (Levenshtein), somiglianza Jaccard, algoritmi basati su Soundex/Phonetics ecc. Un semplice googling ci darebbe tutti i dettagli. È possibile implementare tutti in C#

Ironia, funzionano mentre si tenta di far corrispondere due stringhe di input. Va bene in teoria e per dimostrare come funzionano le corrispondenze sfocate o approssimative.

Tuttavia, il punto grossolanamente sottovalutato è, come utilizziamo lo stesso nelle impostazioni di produzione. Non tutti quelli che conosco su chi stava cercando un algoritmo approssimativo per la corrispondenza delle stringhe sapevano come avrebbero potuto risolvere lo stesso nell'ambiente di produzione.

Potrei aver appena parlato di Lucene che è specifico di Java ma c'è anche Lucene per .Net.

https://lucenenet.apache.org/