Algorithm for almost similar values search

Question

I have Persons table in SQL Server 2008.

My goal is to find Persons who have almost similar addresses.

The address is described with columns state, town, street, house, apartment, postcode and phone.

Due to some specific differences in some states (not US) and human factor (mistakes in addresses etc.), address is not filled in the same pattern.

Most common mistakes in addresses

1. Case sensitivity
2. Someone wrote "apt.", another one "apartment" or "ap." (although addresses aren't written in English)
3. Spaces, dots, commas
4. Differences in writing street names, like 'Dr. Jones str." or "Doctor Jones street" or "D. Jon. st." or "Dr Jones st" etc.

The main problem is that data isn't in the same pattern, so it's really difficult to find similar addresses.

Is there any algorithm for this kind of issue?

Thanks in advance.

UPDATE

1. As I mentioned address is separated into different columns. Should I generate a string concatenating columns or do your steps for each column? I assume I shouldn't concatenate columns, but if I'll compare columns separately how should I organize it? Should I find similarities for each column an union them or intersect or anything else?
2. Should I have some statistics collecting or some kind of educating algorithm?

Answer 1

Suggest approaching it thus:

1. Create word-level n-grams (a trigram/4-gram might do it) from the various entries

2. Do a many x many comparison for string comparison and cluster them by string distance. Someone suggested Levenshtein; there are better ones for this kind of task, Jaro-Winkler Distance and Smith-Waterman work better. A libraryt such as SimMetrics would make life a lot easier

3. Once you have clusters of n-grams, you can resolve the whole string using the constituent subgrams i.e. D.Jones St => Davy Jones St. => DJones St.

Should not be too hard, this is an all-too-common problem.

Update: Based on your update above, here are the suggested steps

1. Catenate your columns into a single string, perhaps create a db "view" . For example,

   create view vwAddress as select top 10000 state town, street, house, apartment, postcode, state+ town+ street+ house+ apartment+ postcode as Address from ...

2. Write a separate application (say in Java or C#/VB.NET) and Use an algorithm like JaroWinkler to estimate the string distance for the combined address, to create a many x many comparison. and write into a separate table address1 | address n | similarity

You can use Simmetrics to get the similarity thus:

 JaroWinnkler objJw = new JaroWinkler()
double sim =  objJw.GetSimilarity (address1, addres n);

3. You could also trigram it so that an address such as "1 Jones Street, Sometown, SomeCountry" becomes "1 Jones Street", "Jones Street Sometown", and so on.... and compare the trigrams. (or even 4-grams) for higher accuracy.

4. Finally you can order by similarity to get a cluster of most similar addresses and decide an approprite threshold. Not sure why you are stuck