string matching approssimativa

Question

So che questa domanda è stato chiesto un sacco di tempo. Voglio un suggerimento su quale algoritmo è adatto per la corrispondenza approssimativa stringa.

L'applicativo è specifico per nome della società solo di corrispondenza e niente altro.

La sfida più grande è probabilmente il nome fine parte dell'azienda e breve nominato parte Esempio: 1. CompanyA Pty Ltd vs CompanyA PTY. ltd. vs CompanyA 2. Ingegneria WES vs W.E.S. Engineering (estremamente rara occorrenza)

Pensi Levenshtein Edit distanza e 'adeguata?

sto usando C #

Saluti, Max

Answer 1

Ci sono varie metriche distanza stringa è possibile utilizzare.

Jaro-Winkler . A differenza di edit-distanza in cui il risultato di un confronto è in unità discrete di modifiche, JW ti dà un punteggio di 0-1. E 'particolarmente adatto per i nomi propri. Anche guardare questo bel tutorial e questa domanda SO.

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

Impl 1 (Hanno una versione Dot Net troppo se si guarda l'elenco di file)

Impl 2

---

Se si vuole fare un po 'di corrispondenza più sofisticati, si può provare a fare un po' la normalizzazione personalizzata di forme di parole che si verificano comunemente nei nomi di società come ltd/limited, inc/incorporated, corp/corporation sul conto per 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 calcolata Levenshtein edit-distanza).

Answer 2

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

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

Answer 3

In questi semplici esempi, solo la rimozione di tutti i caratteri non alfanumerici ti dà una partita, ed è il più facile da fare come è possibile pre-calcolare i dati su ogni lato, poi fare un dritto uguale partita che sarà un molto più veloce di moltiplicazione croce e il calcolo della distanza di modifica.

Answer 4

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

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

Ho lavorato sul sistema veramente larga scala con simili requisiti nome di corrispondenza che si è parlato. Nome corrispondenza non è molto semplice e l'ordine dei nomi e cognomi potrebbe essere diverso. Semplici algoritmi nome fuzzy matching falliscono miseramente in tali scenari.

Se vogliamo solo parlare di algoritmi stringa corrispondente approssimativi, poi ci sono molti. Pochi di loro sono: Jaro-Winkler, Edit distanza (Levenshtein), Jaccard somiglianza, Soundex / Fonetica basata algoritmi ecc Un semplice googling ci darebbe tutti i dettagli. È possibile implementare tutti loro in C #

L'ironia è, funzionano mentre si tenta di abbinare due date stringhe di input. Va bene teoricamente e per dimostrare il modo in cui le opere di corrispondenza stringa sfocati o approssimative.

Tuttavia, il punto grossolanamente sottovalutato è, come possiamo utilizzare lo stesso in ambienti di produzione. Non tutti che io sappia che sono stati scouting per uno string matching approssimato algoritmo sapeva come avrebbero potuto risolvere lo stesso nell'ambiente di produzione.

I potrebbe avere appena parlato di Lucene, che è specifico per Java, ma non v'è Lucene per .Net anche.

https://lucenenet.apache.org/