Compare US addresses for trivial differences

[eluser]MadZad[/eluser]
We send US addresses to an external service to format them "the USPS way", which saves us postage. If the service suggests a change to the address, we let the user decide whether to accept the new one, or insist on the old.

What I'd like to do is detect "trivial" changes, that can just automatically be saved without risk and without bothering the user. i.e. "123 South Main Street" should be equivalent to the approved version "123 S Main St".

I'm sure this is a problem that's been solved many times over. Anyone have a favorite algorithm to recommend?

For reference, my initial approach is to trim/capitalize all strings, translate directions (" NORTH " becomes " N "), abbreviate suffixes a-la www.usps.com/ncsc/lookups/abbr_suffix.txt, abbreviate states, and ignore expanding 5-digit zip codes to 9. Then do string comparisons.