Parse usable Street Address, City, State, Zip from a string

Question

Problem: I have an address field from an Access database which has been converted to Sql Server 2005. This field has everything all in one field. I need to parse out the individual sections of the address into their appropriate fields in a normalized table. I need to do this for approximately 4,000 records and it needs to be repeatable.

Here are the rules for this exercise:

1 - no whining about how this should have been separate fields in the first place, we are often confronted with less than ideal situations and have to make the best of them

2- for this post, use any language you want

3- feel free to play code golf

4 - Assume an address in the US (for now)

5 - assume that the input string will sometimes contain an addressee (the person being addressed) and/or a second street address (i.e. Suite B)

6 - states may be abbreviated

7 - zip code could be standard 5 digit or zip+4

8 - there are typos in some instances

UPDATE: In response to the questions posed, standards were not universally followed, I need need to store the individual values, not just geocode and errors means typo (corrected above)

Sample Data:

• A. P. Croll & Son 2299 Lewes-Georgetown Hwy, Georgetown, DE 19947

• 11522 Shawnee Road, Greenwood DE 19950

• 144 Kings Highway, S.W. Dover, DE 19901

• Intergrated Const. Services 2 Penns Way Suite 405 New Castle, DE 19720

• Humes Realty 33 Bridle Ridge Court, Lewes, DE 19958

• Nichols Excavation 2742 Pulaski Hwy Newark, DE 19711

• 2284 Bryn Zion Road, Smyrna, DE 19904

• VEI Dover Crossroads, LLC 1500 Serpentine Road, Suite 100 Baltimore MD 21

• 580 North Dupont Highway Dover, DE 19901

• P.O. Box 778 Dover, DE 19903

Answer 1

This won't solve your problem, but if you only needed lat/long data for these addresses, the Google Maps API will parse non-formatted addresses pretty well.

Answer 2

Are there any standards at all in the way that the addresses are recorded? For example:

1. Are there always commas or new-lines separating street1 from street2 from city from state from zip?
2. Are address types (road, street, boulevard, etc) always spelled out? always abbreviated? Some of each?
3. Define "error".

My general answer is a series of Regular Expressions, though the complexity of this depends on the answer. And if there is no consistency at all, then you may only be able to achieve partial success with a Regex (ie: filtering out zip code and state) and will have to do the rest by hand (or at least go through the rest very carefully to make sure you spot the errors).

Answer 3

Couple of questions: 1. Any delimiters? 2. What is the field order in the string? 3. What behavior do you want in the case of a data error (E.G. shove address into a single field in the SQL table, leave others blank)

Answer 4

I've done a lot of work on this kind of parsing. Because there are errors you won't get 100% accuracy, but there are a few things you can do to get most of the way there, and then do a visual BS test. Here's the general way to go about it. It's not code, because it's pretty academic to write it, there's no weirdness, just lots of string handling.

(Now that you've posted some sample data, I've made some minor changes)

1. Work backward. Start from the zip code, which will be near the end, and in one of two known formats: XXXXX or XXXXX-XXXX. If this doesn't appear, you can assume you're in the city, state portion, below.
2. The next thing, before the zip, is going to be the state, and it'll be either in a two-letter format, or as words. You know what these will be, too -- there's only 50 of them. Also, you could soundex the words to help compensate for spelling errors.
3. before that is the city, and it's probably on the same line as the state. You could use a zip-code database to check the city and state based on the zip, or at least use it as a BS detector.
4. The street address will generally be one or two lines. The second line will generally be the suite number if there is one, but it could also be a PO box.
5. It's going to be near-impossible to detect a name on the first or second line, though if it's not prefixed with a number (or if it's prefixed with an "attn:" or "attention to:" it could give you a hint as to whether it's a name or an address line.

I hope this helps somewhat.

Answer 5

There are data services that given a zip code will give you list of street names in that zip code.

Use a regex to extract Zip or City State - find the correct one or if a error get both. pull the list of streets from a data source Correct the city and state, and then street address. Once you get a valid Address line 1, city, state, and zip you can then make assumptions on address line 2..3

Answer 6

Based on the sample data:

1. I would start at the end of the string. Parse a Zip-code (either format). Read end to first space. If no Zip Code was found Error.

2. Trim the end then for spaces and special chars (commas)

3. Then move on to State, again use the Space as the delimiter. Maybe use a lookup list to validate 2 letter state codes, and full state names. If no valid state found, error.

4. Trim spaces and commas from the end again.

5. City gets tricky, I would actually use a comma here, at the risk of getting too much data in the city. Look for the comma, or beginning of the line.

6. If you still have chars left in the string, shove all of that into an address field.

This isn't perfect, but it should be a pretty good starting point.

Answer 7

Another request for sample data.

As has been mentioned I would work backwards from the zip.

Once you have a zip I would query a zip database, store the results, and remove them & the zip from the string.

That will leave you with the address mess. MOST (All?) addresses will start with a number so find the first occurrence of a number in the remaining string and grab everything from it to the (new) end of the string. That will be your address. Anything to the left of that number is likely an addressee.

You should now have the City, State, & Zip stored in a table and possibly two strings, addressee and address. For the address, check for the existence of "Suite" or "Apt." etc. and split that into two values (address lines 1 & 2).

For the addressee I would punt and grab the last word of that string as the last name and put the rest into the first name field. If you don't want to do that, you'll need to check for salutation (Mr., Ms., Dr., etc.) at the start and make some assumptions based on the number of spaces as to how the name is made up.

I don't think there's any way you can parse with 100% accuracy.

Answer 8

I've done this in the past.

Either do it manually, (build a nice gui that helps the user do it quickly) or have it automated and check against a recent address database (you have to buy that) and manually handle errors.

Manual handling will take about 10 seconds each, meaning you can do 3600/10 = 360 per hour, so 4000 should take you approximately 11-12 hours. This will give you a high rate of accuracy.

For automation, you need a recent US address database, and tweak your rules against that. I suggest not going fancy on the regex (hard to maintain long-term, so many exceptions). Go for 90% match against the database, do the rest manually.

Do get a copy of Postal Addressing Standards (USPS) at http://pe.usps.gov/cpim/ftp/pubs/Pub28/pub28.pdf and notice it is 130+ pages long. Regexes to implement that would be nuts.

For international addresses, all bets are off. US-based workers would not be able to validate.

Alternatively, use a data service. I have, however, no recommendations.

Furthermore: when you do send out the stuff in the mail (that's what it's for, right?) make sure you put "address correction requested" on the envelope (in the right place) and update the database. (We made a simple gui for the front desk person to do that; the person who actually sorts through the mail)

Finally, when you have scrubbed data, look for duplicates.

Answer 9

You're all overthinking this

a) Split on commas.

b) If the name appears in the first line of the address either :

• If the name exists in another field (Likely), remove the name from the first address line (using a replace with Blank).
• If the name doesn't appear anywhere else, strip to the first numeric character if the length of that first field is > 40 characters.

You'll end up with some errors, but export the whole lot to Excel and get the customer to tidy it up. Because most addresses will be correct, they'll be able to quickly get the data correctly. i.e. 4000 lines should be sortable in a couple of hours.

Answer 10

If it's human entered data, then you'll spend too much time trying to code around the exceptions.

Try:

1. Regular expression to extract the zip code

2. Zip code lookup (via appropriate government DB) to get the correct address

3. Get an intern to manually verify the new data matches the old

Answer 11

This won't solve your problem, but if you only needed lat/long data for these addresses, the Google Maps API will parse non-formatted addresses pretty well.

Good suggestion, alternatively you can execute a CURL request for each address to Google Maps and it will return the properly formatted address. From that, you can regex to your heart's content.

Answer 12

I've been working in the address processing domain for about 5 years now, and there really is no silver bullet. The correct solution is going to depend on the value of the data. If it's not very valuable, throw it through a parser as the other answers suggest. If it's even somewhat valuable you'll definitely need to have a human evaluate/correct all the results of the parser. If you're looking for a fully automated, repeatable solution, you probably want to talk to a address correction vendor like Group1 or Trillium.

Answer 13

After the advice here, I have devised the following function in VB which creates passable, although not always perfect (if a company name and a suite line are given, it combines the suite and city) usable data. Please feel free to comment/refactor/yell at me for breaking one of my own rules, etc.:

    Public Function parseAddress(ByVal input As String) As Collection
      input = input.Replace(",", "")
      input = input.Replace("  ", " ")
      Dim splitString() As String = Split(input)
      Dim streetMarker() As String = New String() {"street", "st", "st.", "avenue", "ave", "ave.", "blvd", "blvd.", "highway", "hwy", "hwy.", "box", "road", "rd", "rd.", "lane", "ln", "ln.", "circle", "circ", "circ.", "court", "ct", "ct."}
      Dim address1 As String
      Dim address2 As String = ""
      Dim city As String
      Dim state As String
      Dim zip As String
      Dim streetMarkerIndex As Integer

      zip = splitString(splitString.Length - 1).ToString()
      state = splitString(splitString.Length - 2).ToString()
      streetMarkerIndex = getLastIndexOf(splitString, streetMarker) + 1
      Dim sb As New StringBuilder

      For counter As Integer = streetMarkerIndex To splitString.Length - 3
        sb.Append(splitString(counter) + " ")
      Next counter
      city = RTrim(sb.ToString())
      Dim addressIndex As Integer = 0

      For counter As Integer = 0 To streetMarkerIndex
        If IsNumeric(splitString(counter)) _
        Or splitString(counter).ToString.ToLower = "po" _
        Or splitString(counter).ToString().ToLower().Replace(".", "") = "po" Then
            addressIndex = counter
            Exit For
        End If
      Next counter

      sb = New StringBuilder
      For counter As Integer = addressIndex To streetMarkerIndex - 1
        sb.Append(splitString(counter) + " ")
      Next counter

      address1 = RTrim(sb.ToString())

      sb = New StringBuilder

      If addressIndex = 0 Then
          If splitString(splitString.Length - 2).ToString() <> splitString(streetMarkerIndex + 1) Then
              For counter As Integer = streetMarkerIndex To splitString.Length - 2
                sb.Append(splitString(counter) + " ")
              Next counter
          End If
      Else
          For counter As Integer = 0 To addressIndex - 1
            sb.Append(splitString(counter) + " ")
          Next counter
      End If
      address2 = RTrim(sb.ToString())

      Dim output As New Collection
      output.Add(address1, "Address1")
      output.Add(address2, "Address2")
      output.Add(city, "City")
      output.Add(state, "State")
      output.Add(zip, "Zip")
      Return output
End Function

Private Function getLastIndexOf(ByVal sArray As String(), ByVal checkArray As String()) As Integer
    Dim sourceIndex As Integer = 0
    Dim outputIndex As Integer = 0
    For Each item As String In checkArray
        For Each source As String In sArray
            If source.ToLower = item.ToLower Then
                outputIndex = sourceIndex
                If item.ToLower = "box" Then
                    outputIndex = outputIndex + 1
                End If
            End If
            sourceIndex = sourceIndex + 1
        Next
        sourceIndex = 0
    Next
    Return outputIndex
End Function

Passing the parseAddress function "A. P. Croll & Son 2299 Lewes-Georgetown Hwy, Georgetown, DE 19947" returns:

2299 Lewes-Georgetown Hwy

A. P. Croll & Son

Georgetown

DE

19947

Answer 14

I think outsourcing the problem is the best bet: send it to the Google (or Yahoo) geocoder. The geocoder returns not only the lat/long (which aren't of interest here), but also a rich parsing of the address, with fields filled in that you didn't send (including ZIP+4 and county).

For example, parsing "1600 Amphitheatre Parkway, Mountain View, CA" yields

{
  "name": "1600 Amphitheatre Parkway, Mountain View, CA, USA",
  "Status": {
    "code": 200,
    "request": "geocode"
  },
  "Placemark": [
    {
      "address": "1600 Amphitheatre Pkwy, Mountain View, CA 94043, USA",
      "AddressDetails": {
        "Country": {
          "CountryNameCode": "US",
          "AdministrativeArea": {
            "AdministrativeAreaName": "CA",
            "SubAdministrativeArea": {
              "SubAdministrativeAreaName": "Santa Clara",
              "Locality": {
                "LocalityName": "Mountain View",
                "Thoroughfare": {
                  "ThoroughfareName": "1600 Amphitheatre Pkwy"
                },
                "PostalCode": {
                  "PostalCodeNumber": "94043"
                }
              }
            }
          }
        },
        "Accuracy": 8
      },
      "Point": {
        "coordinates": [-122.083739, 37.423021, 0]
      }
    }
  ]
}

Now that's parseable!

Answer 15

RecogniContact is a Windows COM object that parses US and European addresses. You can try it right on http://www.loquisoft.com/index.php?page=8

Answer 16

Does anyone know about FINALIST?

Does it really useful for address verification?

Eager to know how it works?

Answer 17

I would LOVE to get Google's code, since it's optimized for the international address standard. Probably have to depend on them for continued service, and the enventual fees.

Answer 18

Try www.address-parser.com. We use their web service, which you can test online

Answer 19

Use www.match-logics.com Fuzzy Search Server that is designed specially for such king of problems.

Answer 20

+1 on James A. Rosen's suggested solution as it has worked well for me, however for completists this site is a fascinating read and the best attempt I've seen in documenting international addresses: http://www.columbia.edu/kermit/postal.html

Answer 21

I don't know HOW FEASIBLE this would be, but I haven't seen this mentioned so I thought I would go ahead and suggest this:

If you are strictly in the US... get a huge database of all zip codes, states, cities and streets. Now look for these in your addresses. You can validate what you find by testing if, say, the city you found exists in the state you found, or by checking if the street you found exists in the city you found. If not, chances are John isn't for John's street, but is the name of the addressee... Basically, get the most information you can and check your addresses against it. An extreme example would be to get A LIST OF ALL THE ADDRESSES IN THE US OF A and then find which one has the most relevant match to each of your addresses...