Indeed using some distance function seems like a good approach. But the problem then is to find the closest string from a given address, which is far from trivial.
You are describing a wide category of algorithms here. Check out Nearest neighbor search
As mentioned in a comment, if you find a way to separate the components of the address (street name, number, etc), it will make the task much easier.