how to recognize similar words with difference in spelling

Question

I want to filter out duplicate customer names from a database. A single customer may have more than one entry to the system with the same name but with little difference in spelling. So here is an example: A customer named Brook may have three entries to the system with this variations:

1. Brook Berta
2. Bruck Berta
3. Biruk Berta

Let's assume we are putting this name in one database column. I would like to know the different mechanisms to identify such duplications form say a 100,000 records. We may use regular expressions in C# to iterate through all records or some other pattern matching technique or we may export these records to what ever best fits for such queries (SQL with Regular Expression capabilities)).

This is what I thought as a solution

• Write a C# code to iterate through each record
• Get only the Consonant letters in order (in the above case: BrKBrt)
• Search for the same Consonant pattern from the other records considering similar sounding letters like (C,K) (C,S), (F, PH)

So please forward any ideas.

Answer 1

The Double Metaphone algorithm, published in 2000, is a new and improved version of the Soundex algorithm that was patented in 1918.

The article has links to Double Metaphone implementations in many languages.

Answer 2

The obvious, established (and well documented) algorithms for finding string similarity are:

• Levenstein distance
• Soundex

Answer 3

Have a look at Soundex

There is a Soundex function in Transact-SQL (see http://msdn.microsoft.com/en-us/library/ms187384.aspx):

SELECT 
SOUNDEX('brook berta'),
SOUNDEX('Bruck Berta'),
SOUNDEX('Biruk Berta')

returns the same value B620 for each of the example values

Answer 4

I would consider writing something such as the "famous" python spell checker.

http://norvig.com/spell-correct.html

This will take a word and find all possible alternatives based on missing letters, adding letters, swapping letters, etc.

Answer 5

You might want to google for phonetic similarity algorithm and you'll find plenty of information about this. Including this article on Codeproject about implementing a solution in C#.

Answer 6

Look into soundex. It's a pretty standard library in most languages that does what you require, i.e. algorithmically identify phonetic similarity. http://en.wikipedia.org/wiki/Soundex

Answer 7

There is a very nice R (just search for "R" in Google) package for Record Linkage. The standard examples target exactly your problem: R RecordLinkage

The C-Code for Soundex etc. is taken directly from PostgreSQL!

Answer 8

I would recommend Soundex and derived algorithms over Lev distance for this solution. Levenstein distance more appropriate for spell checking solutions imho.