Confronto stringa intelligente

Question

Sto cercando una libreria/classe che consenta il confronto intelligente di due stringhe. Al massimo darebbe come risultato la percentuale di come due stringhe sono simili. Sto confrontando i nomi delle società, gli indirizzi che sono registrati in diversi repository, avendo così molti errori di ortografia o incongruenze nei nomi.

stringhe di esempio per confrontare:

"Good Company Ltd." vs. "GoodCompany" 
"Baker Street 2" vs. "Baker Str. 2" 

Se ho un risultato in percentuale del alikeness, che questo può essere un input per fusione intelligente di tali dati.

Conosci qualche buona libreria che consenta il confronto tra stringhe così intelligenti?

Answer 1

Levenshtein non è appropriato in questo caso. "Good Company Ltd" e "GoodCompany" se tagliati hanno una distanza = 3 mentre "Good Company Ltd" e "Food Company Ltd" hanno una distanza di 1, ma totalmente un significato diverso. Suggerisco l'algoritmo Metaphone or Double Metaphone.

Utilizzando online metaphone comparer i risultati sono:

Good Company Ltd = KTKMPNLTT 
GoodCompany = KTKMPN 
Food Company Ltd = FTKMPNLTT 
GoodCompanyLLC = KTKMPNLK 

In questo modo si sa che GoodCompany, Good Company Ltd e GoodCompanyLLC sono simili, mentre Food Company è errato o totalmente non correlate (KTKMPN è contenuto sia nel KTKMPNLTT e KTKMPNLK ma non in FTKMPNLTT).

Look here per altri confronti di algoritmi.

Answer 2

Si potrebbe voler cercare l'implementazione Levenshtein Distance. Mostra quanti caratteri sono necessari inserimenti/cancellazioni e sostituzioni per rendere uguali due stringhe.

Ecco un post sulle librerie in C# che implementano Levenshtein Distance e altri algoritmi di confronto del testo: .NET library for text algorithms?.

Tuttavia penso che dovrai usare una combinazione di metodi, perché usare Levenshtein ti dirà che "Good Company Ltd." è più simile a "Bad Company Ltd." che a "GoodCompany".

Forse dovrai eseguire un po 'di pre-elaborazione espandendo "str". a "street" e rimuovendo "Ltd." come parola "senza senso" in termini di confronto tra stringhe.

UPDATE 1

Francesco De Lisi suggests da usare algoritmi fonetici. Sembra che siano più adatti per confrontare i nomi errati. Dovrai comunque suddividere gli indirizzi in parti fonetiche/non fonetiche (come i numeri di costruzione) e confrontarli separatamente.

UPDATE 2

quanto per il confronto indirizzi, questo post suggests to use Google Maps API per questo scopo e un altro post discute address parsing. Immagino che Google possa produrre risultati affidabili perché hanno un database di indirizzi stradali dove possono trovare l'ortografia del nome della strada più corretta. Senza un elenco di nomi di strada/società corretti, potresti incontrare un nome strano che non è corretto, tuttavia molti nomi corretti potrebbero essere simili.

Answer 3

Quello che stai cercando è un Levenshtein distance (Wikipedia):

... la distanza Levenshtein è una stringa metrica per misurare la differenza tra due sequenze. Informale, la distanza tra due parole Levenshtein è il numero minimo di modifiche singoli caratteri (inserimento, cancellazione, sostituzione) necessari per cambiare una parola nell'altra