One idea is to remove what you do know first somehow then parse the remainder.

As said the postal code can be shuffled off first if the format is constant.

Next create a list of towns, this will probably be shorter than a list of streets. Now use this list to remove the town/city from the data.

Parsing out the street bits may be more tricky if it's multipart and with business names, street numbers, street names and combinations there of. What would you do with an address like

Some business
Unit n
Sometown retail park
Some street
Some district
Sometown
Postal code
[download]