views:

181

answers:

6

I'm working on some stuff for an in-house CRM. The company's current frontend allows for lots of duplicates. I'm trying to stop end-users from putting in the same person because they searched for 'Bill Johnson' and not 'William Johnson.' So the user will put in some information about their new customer and we'll find the similar names (including fuzzy names) and match them against what is already in our database and ask if they meant those things... Does such a database or technology exist?

+2  A: 

Implement the Levenshtein distance:

http://en.wikipedia.org/wiki/Levenshtein_distance

This can be written as a SQL Function and queried many different ways.

Fosco
A+ for cool computer science ideals. As I said in another comment about hoping to open up a mysql names database I should like to include something to this effect. My only worry is that this will in many cases check for distance of error, when in fact some nicknames hardly look like their origin, but again, quite helpful nontheless
jphenow
Mmh pairs like Jim and James are quite different, not sure it's an appropriate measure.
Mau
yes, I think it could catch a good number of the mishaps though and it would still have to check against our current database so if I required the difference be under a score of 4 AND its in our database could be some useful results
jphenow
John, Jack too.
detly
A: 

You can use SOUNDEX to get similar sounding names. However, it won't match with William and Bill for example.

Try this in SQL as an example.

SELECT SOUNDEX('John'), SOUNDEX('Jon')
Robin Day
Is this a standard SQL function? I know Oracle supports this, but do any others?
TMN
MS Sql Server supports SOUNDEX and DIFFERENCE
Ju9OR
It's in SQL Server, which the OP tagged the question as. I don't know about others.
Robin Day
+2  A: 
stimms
Yes I was considering doing an open/php/mysql alternative cause that's my thing :) but for this specific project I'd love to find a .net matcher with say nicknames and so forth
jphenow
That bit of perl could be useful for adding to a new open project for sure
jphenow
A: 

There is some built-in SOUNDS LIKE functionality in SQL Server, see SOUNDEX http://msdn.microsoft.com/en-us/library/aa259235%28SQL.80%29.aspx

As for full / nickname searching there isn't anything built it that I am aware of. Nicknames vary by region and it's a lot of information to keep track of. There might be a database linking full names to nicknames that you could leverage in your own application.

Mike M.
+1  A: 

Well SSIS has some fuzzy logic tasks we use to find duplicates after the fact.

I think though you need to have your logic look at more than just the name for best results. If they are putting in address, email or phone information, perhaps you could look for people with the same last name with one or more of those other matches and ask if one of them will do. You could also make a table of nicknames for various names and match on that. You won't get all of them, but you could get some of the most common in your country at least.

HLGEM
yes precisely. That's why I'd like to open some project on github soon so i can add as many as I can think of and people from elsewhere can tack on their localized nickname matching
jphenow
+5  A: 

I implemented such a functionality on one website. I use double_metaphone() + levenstein() in PHP. I precalculate a double_metaphone() for each entry in the dabatase, which I lookup using a SELECT of the first x chars of the 'metaphoned' searched term.

Then I sort the returned result according to their levenstein distance. double_metaphone() is not part of any PHP library (last time I checked), so I borrowed a PHP implementation I found somewhere a long while ago on the net (site no longer on line). I should post it somewhere I suppose.

EDIT: The website is still in archive.org: http://web.archive.org/web/20080728063208/http://swoodbridge.com/DoubleMetaPhone/

or Google cache: http://webcache.googleusercontent.com/search?q=cache:Tr9taWl9hMIJ:swoodbridge.com/DoubleMetaPhone/+Stephen+Woodbridge+double_metaphon

which leads to many other useful links with source code for double_metaphone(), including one in Javascript on github: http://github.com/maritz/js-double-metaphone

EDIT: Went through my old code, and here are roughly the steps of what I do, pseudo coded to keep it clear:

1) Precompute a double_metaphone() for every word in the database, i.e., $word='blahblah'; $soundslike=double_metaphone($word);

2) At lookup time, $word is fuzzy-searched against the database: $soundslike = double_metaphone($word)

4) SELECT * FROM table WHERE soundlike LIKE $soundlike (if you have levenstein stored as a procedure, much better: SELECT * FROM table WHERE levenstein(soundlike,$soundlike) < mythreshold ORDER BY levenstein(word,$word) ASC LIMIT ... etc.

It has worked well for me, although I can't use a stored procedure, since I have no control over the server and it's using MySQL 4.20 or something.

R. Hill
That's fantastic... public github perhaps? :)
jphenow
Added URLs to more information re. various double_metaphone() implementation. Now I remember better: I borrowed Stephen Woodbridge's PHP implementation, and modified it slightly for my need (removed the limit in order to double_metaphone the whole term, not just the first fourth characters, etc.)
R. Hill