I have a lot of address strings:
1600 Pennsylvania Ave, Washington, DC 20500 USA
I want to parse them into their components:
street: 1600 Pennsylvania Ave city: Washington province: DC postcode: 20500 country: USA
But of course the data is dirty: it comes from many countries in many languages, written in different ways, contains misspellings, is missing pieces, has extra junk, etc.
Right now our approach is to use rules combined with fuzzy gazetteer matching, but we'd like to explore machine learning techniques. We have labeled training data for supervised learning. The question is, what sort of machine learning problem is this? It doesn't really seem to be clustering, or classification, or regression....
The closest I can come up with would be classifying each token, but then you really want to classify them all simultaneously, satisfying constraints like "there should be at most one country;" and really there are many ways to tokenize a string, and you want to try each one and pick the best.... I know there exists a thing called statistical parsing, but don't know anything about it.
So: what machine learning techniques could I explore for parsing addresses?