16
$\begingroup$

I would like to know how to match postal addresses when their format differ or when one of them is mispelled.

So far I've found different solutions but I think that they are quite old and not very efficient. I'm sure some better methods exist, so if you have references for me to read, I'm sure it is a subject that may interest several persons.

The solution I found (examples are in R) :

  • Levenshtein distance, which equals the number of characters you have to insert, delete or change to transform one word into another.

    agrep("acusait", c("accusait", "abusait"), max = 2, value = TRUE) ## [1] "accusait" "abusait"

  • The comparison of phonemes

    library(RecordLinkage) soundex(x<-c('accusait','acusait','abusait')) ## [1] "A223" "A223" "A123"

  • The use of a spelling corrector (eventually a bayesian one like Peter Norvig's), but not very efficient on address I guess.

  • I thought about using the suggestions of Google suggest, but likewise, it is not very efficient on personal postal addresses.

  • You can imagine using a machine learning supervised approach but you need to have stored the mispelled requests of users to do so which is not an option for me.

Improve this question
$\endgroup$
3
  • $\begingroup$ I'd suggest using a real database that supports fuzzy string matching: posgres. It'll be efficient. $\endgroup$
    – Emre
    Commented Mar 21, 2016 at 21:36
  • $\begingroup$ US only, Canadian, UK, French, Japanese, multi-country...? Presumably for each one, you first determine/guess what language and country it is, then apply a country-specific classifier? Do you have a training-set and if so what is its distribution of countries? $\endgroup$
    – smci
    Commented Dec 12, 2016 at 22:37
  • $\begingroup$ Where did you end up with this? The solution we devised was to scrub and enrich the addresses and place names and hit the google geocoding and place web APIs and then do some rough calculations to determine the correct result compared to the raw data. Its a little clunky but works but there must be a more elegant way to normalize addresses and places/locations. $\endgroup$
    – Chris Smith
    Commented Mar 19, 2019 at 3:12

4 Answers 4

Reset to default
10
$\begingroup$

As you are using R you might want to look into the stringdist package and the Jaro-Winkler distance metric that can be used in the calculations. This was developed at the U.S. Census Bureau for linking .

See for more information on the Jaro and Jaro-Winkler distance in this journal.

For a comparison of different matching techniques, read this paper

Improve this answer
$\endgroup$
0
4
$\begingroup$

There are lots of clever ways to extend the Levenshtein distance to give a fuller picture. A brief intro to a pretty useful module (for python) called 'Fuzzy Wuzzy' is here by the team at SeatGeek.

A couple things you can do is partial string similarity (if you have different length strings, say m & n with m < n), then you only match for m characters. You can also separate the string into tokens (individual words) and look at how sets of tokens match or arrange them alphabetically and order them.

Improve this answer
$\endgroup$
0
4
$\begingroup$

Another popular technique for detecting partial string matches (though typically at the document-level) is shingling. In essence it is a moving-window approach that extracts out a set of n-grams for the target word/doc and compares them to the sets of n-grams for other words/docs via the Jaccard coefficient. Manning and colleagues (2008) discuss near duplicates and shingling in the context of informational retrieval.

Improve this answer
$\endgroup$
4
$\begingroup$

I've written a generic probabalistic fuzzy matcher in Python which will do a reasonable job of matching any type of data:

https://github.com/robinl/fuzzymatcher

It's in memory, so you probably don't want to use it to match datasets which are above about 100k rows.

I've also written a similar project specific to UK addresses, but this assumes you have access to Addressbase Premium. This one isn't in memory, so has been used against the 100m or so UK addresses. See here:

https://github.com/RobinL/AddressMatcher

If you want to get this going quickly I'd reccommend using libpostal to normalise your addresses and then feed them into my generic fuzzymatcher (pip install fuzzymatcher).

You can find usage examples here.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hi Robin, I'm interested in your AddressMatcher library. Do you happen to have any documentation on how to use it? I have this exact problem - need to match 1 set of addresses (messy) to another (official postal addresses). Thanks $\endgroup$
    – SCool
    Commented Aug 9, 2019 at 15:31
  • 1
    $\begingroup$ sadly with the address matcher it's not at all trivial and i don't have good documentation. main thing you need is to load addressbase premium, a commercial product, into postgresql. $\endgroup$
    – RobinL
    Commented Aug 16, 2019 at 9:23
  • $\begingroup$ Ok, thanks for getting back to me. I am working with I suppose the Irish version of Addressbase premium called Eircode which will be incompatible. Do you think fuzzy matcher would be up to the task in production environment address matching? I just want to append postcodes to addresses in my data that don't have them, e.g. search the Eircode databse for '1 Main Street, Some Town, County' and if I find a match - bring back the postcode. $\endgroup$
    – SCool
    Commented Aug 16, 2019 at 9:48
  • 1
    $\begingroup$ fuzzy matcher - yes i definitely think worth a go. it should work reasonably well for a smallish list of addresses to find within a large list of authoratative addresses (i.e. eircode) on a beefy machine. Another option is the fastlink pacakge in R $\endgroup$
    – RobinL
    Commented Aug 16, 2019 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.