# Machine learning techniques for parsing strings?

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?

-
I am not an expert on your high-level problem as to post an answer, but I think the first step to machine learning is building informative features, then choosing the method that is right given their structure. You have a lot of structure; alnum vs non-alnum chars, numeric vs alpha tokens, token counts between ',' splits, numeric token lengths. e.g. split on ',' and count how many tokens in each split (street address vs city/state vs geo specific info); calc strlen of the numeric tokens (street address vs zip code). These give you features you can cluster on. – muratoa Aug 28 '12 at 15:05
Have a look at text chunking. – alto Aug 28 '12 at 17:29
Also look at named entity recognition, and the more general task of Information Extraction – Yuval F Aug 30 '12 at 10:46
@YuvalF I suggest to make this an answer. Can you elaborate a little bit, maybe an example paper where an ML method has been used ? – steffen Aug 31 '12 at 7:45
I am very interested in this specific problem as well - which is structuring a mailing addresss into its component parts. We are attempting to do this in a mobile device with no presumptions on connectivity to a reverse geo-coding service such as googles. It is ok to assume that we have an onboard source of linked data relating city, state, country and zip. Any help - either pointers - or willing to engage with a crazy startup team on this problem is heartily and openly welcome. – user17509 Dec 5 '12 at 13:45

This can be seen as a sequence labeling problem, in which you have a sequence of tokens and want to give a classification for each one. You can use hidden Markov models (HMM) or conditional random fields (CRF) to solve the problem. There are good implementations of HMM and CRF in an open-source package called Mallet.

In your example, you should convert the input to the format below. Moreover, you should generate extra-features.

1600 STREET
Pennsylvania STREET
Ave STREET
, OUT
Washington CITY
, OUT
DC PROVINCE
20500 POSTCODE
USA COUNTRY

-
 I don't think a standard sequence tagger (such as an HMM of CRF) is going to produce very good results in this situation. This is due the restrictions that the tags groups be contiguous and that each tag only occurs once per sequence. I don't think you can easily modify the search to incorporate this information either due to the dependence on past/future tags of arbitrary distance (I could be wrong about this though). – alto Aug 28 '12 at 23:31