Match similar names in C#

Question

I'm currently working on a project that requires me to match our database of Bands and venues with a number of external services.

Basically I'm looking for some direction on the best method for determining if two names are the same. For Example:

• Our database venue name - "The Pig and Whistle"
• service 1 - "Pig and Whistle"
• service 2 - "The Pig & Whistle"
• etc etc

I think the main differences are going to be things like missing "the" or using "&" instead of "and" but there could also be things like slightly different spelling and words in different orders.

What algorithms/techniques are commonly used in this situation, do I need to filter noise words or do some sort of spell check type match?

Have you seen any examples of something simlar in c#?

UPDATE: In case anyone is interested in a c# example there is a heap you can access by doing a google code search for Levenshtein distance

Answer 1

The canonical (and probably the easiest) way to do this is to measure the Levenshtein distance between the two strings. If the distance is small relative to the size of the string, it's probably the same string. Note that if you have to compare a lot of very small strings it'll be harder to tell whether they're the same or not. It works better with longer strings.

A smarter approach might be to compare the Levenshtein distance between the two strings but to assign a distance of zero to the more obvious transformations, like "and"/"&", "Snoop Doggy Dogg"/"Snoop", etc.

Answer 2

soundex may also be useful

Answer 3

In bioinformatics we use this to compare DNA- or protein sequences all the time. There are plenty of algorithms, you probably want to look at global alignments. In this respect the Needleman-Wunsch algorithm is probably what you seek. If you have particularly long recurring strings to compare you might want to consider heuristic searches like BLAST.