A (Google like) auto suggest for customer addresses

I have a database of 600,000 addresses with no names attached to it like this:

Address01, Address02, City, State Zip

I know these addresses are good so what I would like to do is create a function to do an auto suggest for addresses like Google does for search words after our staff enters a addresses into our Point of Sale system. So for instance if a staff member types in:

Address01: 600 Weeler St

I want to go through my address01 column and look for a match and if there is none I want to auto suggest similars like

Did you mean:

1) Wheeler St
2) Wealer St
3) Whaler St

I have a couple of ideas on how to accomplish this but I am not sure of the best way to find "similars" since a Like = % (wild card character) won't work for this scenerio. So I am asking for some suggestions of an efficient way to accomplish the suggestions.

Essentially, I am looking for patterns so I am thinking that I need to be working with Regular Expressions but I haven't done any work with them and I don't want to spend a lot of time trying to make them work with this application if there is another (better) way to do it.

Any ideas, thoughts or suggestions will be greatly appreciated.

It seems to me that what you want is a "sounds like" search, which you can do using SoundEx.

Several database systems have that functionality built-in, so you simply need to use a function in your SQL statement (for SQL Server I think it is actually called Soundex, but I'm not sure about others).

Excellent tip Si. I think that is going to do the trick. Thanks!!!