Smart string comparison

Question

I am looking for a library/class that allows smart compare of two strings. At best it would give as a result percent of how two strings are alike. I am comparing company names, addresses that are recordered in different repositories, thus having many misspellings or inconsistencies in names.

Sample strings to compare:

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

If I get a result in percentage of alikeness, than this can be an input for smart merge of such data.

Do you know any good libraries that would allow such smart string compare?

Try taking a look at this: http://stackoverflow.com/questions/2344320/comparing-strings-with-tolerance — Justin, May 23 '13 at 11:59
Could you tell us what percentage you'd expect to be returned for each of those two string comparisons? — jszigeti, May 23 '13 at 12:00
Would `"GreatOrgansiation"` have any "alikeness" to `"GoodCompany"`? Are you trying to compare meaning? How alike are `"accept"` and `"except"` which sound similar but have different meanings? What about `"country fair"` and `"equal and fair"` or, `"four candles"` and `"fork handles"`? Is there an element of NLP or is this a simpler algorithm? Do you want "Means alike", "Sounds alike" or "Looks alike"? — Jodrell, May 23 '13 at 12:57
@Jodrell: I want to perform a comparison in "looks alike" terms. Company name or address is a generic name, so different meaning will not be the case. Differences can happen due to: misspellings, shortcuts, omitted endings (like Ltd), omitted spaces, etc. — Radoslaw, May 23 '13 at 13:36

Francesco De Lisi · Accepted Answer · 2013-05-23T12:29:02.977

Levenshtein is not appropriate in this case. "Good Company Ltd" and "GoodCompany" if trimmed have a distance = 3 while "Good Company Ltd" and "Food Company Ltd" have a distance of 1, but totally a different meaning. I suggest Metaphone or Double Metaphone algorithm.

Using online metaphone comparer the results are:

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

In this way you know that GoodCompany, Good Company Ltd and GoodCompanyLLC are similar, while Food Company is misspelled or totally not related (KTKMPN is contained both in KTKMPNLTT and KTKMPNLK but not in FTKMPNLTT).

Look here for other algorithms comparisons.

Nice links! Last time I heard of the phonetic comparison it worked only for languages with latin letters. — Artemix, May 23 '13 at 12:37

score 14 · Answer 2 · edited May 23 '17 at 12:22

You might want to look for Levenshtein Distance implementation. It shows how many characters insertions/deletions and substitutions are required to make two strings equal.

Here is a post about libraries in C# that implement Levenshtein Distance and other text-comparison algorithms: .NET library for text algorithms?.

However I think you'll have to use some combination of methods, because using Levenshtein will tell you that 'Good Company Ltd.' is more similar to 'Bad Company Ltd.' than to 'GoodCompany'.

Maybe you'll have to do some preprocessing by expanding 'str.' to 'street' and removing 'Ltd.' as 'meaningless' word in terms of string comparison.

UPDATE 1

Francesco De Lisi suggests to use Phonetic algoritms. Looks like they are better suited for comparing misspelled names. Still you'll need to split addresses to phonetic / non-phonetic parts (like building numbers) and compare them separately.

UPDATE 2

As for addresses comparison, this post suggests to use Google Maps API for this purpose and another post discusses address parsing. I guess that Google can produce reliable results because they have a database of street addresses where they can find the most correct street name spelling. Without list of correct street/company names you may encounter some strange name that is incorrect, however many different correct names would be similar to it.

Levenshtein is not really appropriate. Metaphone or Double Metaphone are able to check for similarities in a better way. — Francesco De Lisi, May 23 '13 at 12:23
Thanks for suggesting Google Maps API, they're be suitable for address proofing. — Radoslaw, May 23 '13 at 15:09

score 8 · Answer 3 · answered May 23 '13 at 11:59

What you're looking for is a Levenshtein distance (Wikipedia):

...the Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion, substitution) required to change one word into the other

Smart string comparison

3 Answers3