# 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
• @alto I believe CRF takes into consideration neighboring context. HMM can't see past state, you are right that it probably wouldn't work very well. – J T Oct 19 '16 at 15:22

I had to solve a very similar problem to validate whether an address is valid or invalid.

Typically address have the structure "1600 Pennsylvania Ave, Washington DC, 20500"

A string such as

"I went down 2000 steps and reached Pennsylvania Ave in Washington DC."

This can be solved by classification techniques such as SVM, Neural Networks etc.

The idea is to identify a key set of features. Some of these could be:

1) Does the street name start with a valid block number. Most US block numbers are either numbers (e.g. 1200) or a number followed by a single letter (120A) or a number following a single letter (e.g. S200).

2) If the address is well formatted, the street names end in suffixes like Ave for avenue, Dr for Drive, Blvd for Boulevard. It is possible to obtain the US street suffix list from USPS site.

3) The number of words in the street address field can also be an interesting feature. If there are too many words, it is probably not a valid address. E.g. see the example above.

4) How many words occur between the block number and the street suffix in address field ?

These can be used to train a learning algorithm and the resulting model can be used to validate if a given address is valid or not.

This is a bit of a hack that does not require your own solution: reverse geocoding. This can either give you cleaner data or actually do all the work for you.

For example, here's some Stata code with geocode3 from SSC, which uses Google. I guess this is similar to Fuzzy Gazetteer. The first address is pretty messy, the second is clean, and the third is foreign. Other software can handle this is as well.

clear
set obs 3
replace address = "Big Foot Museum in Felton CA" in 1
replace address = "1600 Pennsylvania Ave, Washington, DC 20500 USA" in 2
replace address = "ул. Ильинка, д. 23 103132, Москва, Россия" in 3
gen coord = string(g_lat) + "," + string(g_lon)
geocode3, reverse coord(coord)


This works reasonably well:

. list r_addr , clean noobs

121 San Lorenzo Avenue, Felton, CA 95018, USA
1600 Pennsylvania Avenue Northwest, President's Park, Washington, DC 20500, USA
ulitsa Ilyinka, 23, Moscow, Russia, 101000


The Kremlin does have a pretty different format.

This sounds like a problem to be solved with bidirectional LSTM classification. You tag each character of the sample as one category for example

street: 1 city: 2 province: 3 postcode: 4 country: 5

1600 Pennsylvania Ave, Washington, DC 20500 USA
111111111111111111111, 2222222222, 33 44444 555


Now, train your classifier based on these labels. Boom!