Approximate string matching

Question

I know this question have been asked a lot of time. I want a suggestion on which algorithm is suitable for approximate string matching.

The application is specifically for company name matching only and nothing else.

The biggest challenge is probably the company end name part and short named part Example: 1. companyA pty ltd vs companyA pty. ltd. vs companyA 2. WES Engineering vs W.E.S. Engineering (extremely rare occurance)

Do you think Levenshtein Edit Distance is adequate?

I'm using C#

Regards, Max

Answer 1

In these simple examples, just removing all non-alpha-numeric characters gives you a match, and is the easiest to do as you can pre-compute the data on each side, then do a straight equals match which will be a lot faster than cross multiplying and calculating the edit distance.

Answer 2

There are various string distance metrics you could use.

I would recommend Jaro-Winkler. Unlike edit-distance where the result of a comparison is in discrete units of edits, JW gives you a 0-1 score. It is especially suited for proper names. Also look at this nice tutorial and this SO question.

I haven't worked with C# but here are some implementations of JW I found online:

Impl 1 (They have a DOT NET version too if you look at the file list)

Impl 2

---

If you want to do a bit more sophisticated matching, you can try to do some custom normalization of word forms commonly occurring in company names such as ltd/limited, inc/incorporated, corp/corporation to account for case insensitivity, abbreviations etc. This way if you compute

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

you should get the result to be 0 rather than 14 (which is what you would get if you computed levenshtein edit-distance).

Answer 3

I have provided my answer already in another question.

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

I have worked on really large scale system with similar name matching requirements that you have talked about. Name matching is not very straightforward and the order of first and last names might be different. Simple fuzzy name matching algorithms fail miserably in such scenarios.

If we just want to talk about the Approximate String matching algorithms, then there are many. Few of them are: Jaro-Winkler, Edit distance(Levenshtein), Jaccard similarity, Soundex/Phonetics based algorithms etc. A simple googling would give us all the details. You can implement all of them in C#

Irony is, they work while you try to match two given input strings. Alright theoretically and to demonstrate the way fuzzy or approximate string matching works.

However, grossly understated point is, how do we use the same in production settings. Not everybody that I know of who were scouting for an approximate string matching algorithm knew how they could solve the same in the production environment.

I might have just talked about Lucene which is specific to Java but there is Lucene for .Net also.

https://lucenenet.apache.org/

Answer 4

Yes, Levenshtein distance is suitable for this. It will work for all those you have listed at least.

You could also possibly use Soundex, but I don't think you'll need it.