How to perform Cleaning of a very large set of addresses
I guess you are in a situation that different fields of an address are mixed together. Try break the address text into Shingles and then try Locality-sensitive Hashing

Prof. Jeff Ullman's Text Book may help you put together all the techniques you need, starts with Section 3.2