Parsing US address with Clojure

Question

The parser below is not designed for every single US address. I am parsing through a file where each line may or may not be an address. I am more focused on speed rather than robustness.

• state-abbreviation-lookup and street-suffix-lookup are booth used for consistency (addresses will always be "ST" instead of "STREET" or "STR")

• find-last-occurence-index-of searches through a list of string and finds the last string that matches a key in a hash-map. This is used with state-abbreviation-lookup and street-suffix-lookup to find where in the address the state and or street is.

• split-string removes commas, capitalizes everything and then splits on whitespace.

Next in the code is some checks for invalid values. I finally have to split the address into the appropriate parts: street, city, state, zipcode.

Overall, it feels like too much is going on, but I'm not sure how best to make it the most Clojure-like.

(def
 ^{:const true 
   :source "https://www.usps.com/send/official-abbreviations.htm"}
  state-abbreviation-lookup
  (hash-map 
    "AL" "AL"
    "ALABAMA" "AL"
    "AK" "AK"
    "ALASKA" "AK"
    ;... removed for brevity
    ))

(def
 ^{:const true 
   :source "https://www.usps.com/send/official-abbreviations.htm"}
  street-suffix-lookup
  (hash-map 
    ;... removed for brevity
    "STREET" "ST"
    "ST" "ST"
    "STR" "ST"
    "STRT" "ST"
    ;... removed for brevity
    ))

(defrecord UsAddress [street city state zipcode])

(letfn 
  [(find-last-occurence-index-of [lookup-map coll]
    (last (keep-indexed #(when (contains? lookup-map %2) %1) coll)))
   (split-string [s]
    ((comp #(clojure.string/split % #"\s+") 
                     clojure.string/upper-case 
                     #(clojure.string/replace % #"," "")) 
     s))]
(defn extract-us-address [s] 
  (let [parts (split-string s)]
    (when (re-matches #"^\d{5}$" (last parts))
      (let [state-index (find-last-occurence-index-of state-abbreviation-lookup parts)
            street-index (find-last-occurence-index-of street-suffix-lookup parts)]
        (when (and state-index street-index)
          (UsAddress. 
            (clojure.string/join " " (take (inc street-index) parts))
            (clojure.string/join " " (drop (inc street-index) (take state-index parts)))
            (state-abbreviation-lookup (nth parts state-index))
            (last parts))))))))

Tests:

(deftest extract-us-address-test
  (testing "extract-us-address"
    (testing "should determine if string is a US address"
      (are [i o] (= (extract-us-address i) o)
        "3526 HIGH ST SACRAMENTO CA 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 HIGH ST SACRAMENTO, CA 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 HIGH ST SACRAMENTO California 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 HIGH ST SACRAMENTO, California 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 high st sacramento ca 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 high st sacramento, ca 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 CALIFORNIA ST SACRAMENTO CA 95838"  (UsAddress. "3526 CALIFORNIA ST" "SACRAMENTO" "CA" "95838")
        "3526 CALIFORNIA ST SACRAMENTO, CA 95838"  (UsAddress. "3526 CALIFORNIA ST" "SACRAMENTO" "CA" "95838")
        "3526 AVENUE ST SACRAMENTO CA 95838"  (UsAddress. "3526 AVENUE ST" "SACRAMENTO" "CA" "95838")
        "3526 AVENUE ST SACRAMENTO, CA 95838"  (UsAddress. "3526 AVENUE ST" "SACRAMENTO" "CA" "95838")
        "California"  nil
        "CA"  nil
        ""  nil
        "SACRAMENTO"  nil
        "95838"  nil
        "3526 HIGH STREET"  nil
        "304 867 5309" nil))))

Answer 1

split-string can be simplified

You're defining a function that takes an argument s and applies the composite of 3 different clojure.string functions to s within the body of the function. You could simplify this in 2 ways:

1. (require '[clojure.string] :as s) -- now you can call all three functions in a much more concise way, e.g. s/split.

2. (comp fn1 fn2 fn3 s) is already a function, so you could actually define split-string as just that, without needing to repeat s as part of the function. See below:

   (require '[clojure.string :as s])
   
   (def split-string
     (comp #(s/split % #"\s+") s/upper-case #(s/replace % #"," "")))
   

This is just a matter of preference, but I would find it easier to read if you used a threading macro instead:

(defn split-string [s]
  (-> s (s/replace #"," "") s/upper-case (s/split #"\s+")))

defn should only be at the top level

In your code, you have the equivalent of this:

(letfn [(foo [x] (bar x))]
  (defn baz [y] (foo y)))

(To be more specific, I'm talking about (letfn [(find-last-occurrence-index-of ...) (split-string [s] ...)] (defn extract-us address [s] ...)))

Having a defn inside of a let form is un-idiomatic, and can be a little bit confusing at first glance. The general rule is to only have def forms (including defn, defmacro, etc.) at the top level of your code. You can fix this by simply flipping it so that the letfn part is inside the defn part, like this:

(defn baz [y]
  (letfn [(foo [x] (bar x))]
    (foo y)))

This way, it is more clear that the functions being "let'd" are internal to the function.

Combine when/let bindings when possible

The main thing I notice, looking at your extract-us-address function, is that there are multiple let and when statements. Sometimes this is unavoidable, but often you can tidy up your code by combining multiple bindings into a single let form. You could do something like the code below. Notice also that I've included your "letfns" find-last-occurrence-index-of and split-string as anonymous functions within the let bindings.

(defn extract-us-address [s]
  (let [find-last-occurrence-index-of 
        (fn [lookup-map coll]
          (last (keep-indexed #(when (contains? lookup-map %2) %1) coll)))

        split-string 
        (fn [s] 
          (-> s (s/replace #"," "") s/upper-case (s/split #"\s+")))

        parts (split-string s)]
    ...

Use helper functions

The other thing I notice is that you have one fairly complex function, where you could have one "main" function (extract-us-address) which relies on a handful of seperate "helper" functions. Doing it that way generally makes your code easier to read. Here's an idea of how you could refactor your code into several smaller functions:

; (to make it clearer which functions are helper functions, mark 
; them as private functions by using defn- instead of defn)

(defn- find-last-occurrence-index-of [lookup-map coll]
  (last (keep-indexed #(when (contains? lookup-map %2) %1) coll)))

; You could rename split-string to parts, then refer to (parts s),
; thereby avoiding needing to bind (split-string s) to parts in a
; let binding. I think this more clearly describes what the function
; is doing, as well.
(defn- parts [s]
  (-> s (s/replace #"," "") s/upper-case (s/split #"\s+")))

(defn- zip-code [s]
  (re-matches #"^\d{5}$" (last (parts s))))

(defn- street-index [s]
  (find-last-occurrence-index-of street-suffix-lookup (parts s)))

(defn- state-index [s]
  (find-last-occurrence-index-of state-abbreviation-lookup (parts s)))

(defn extract-us-address [s]
  ; this let binding is here to help performance -- we only want to evaluate
  ; each of these once, and bind it to a symbol
  (let [zip-code (zip-code s)
        street-index (street-index s)
        state-index (state-index s)]
    (when (and zip-code street-index state-index)
      (UsAddress. 
        (clojure.string/join " " (take (inc street-index) (parts s)))
        (clojure.string/join " " (drop (inc street-index) (take state-index (parts s))))
        (state-abbreviation-lookup (nth (parts s) state-index))
        zip-code))))

Is there a better way to do this?

I noticed that there are a couple of potential flaws with your algorithm:

1. It relies on the fact(/assumption?) that there are no street suffixes that overlap with state abbreviations. This might be OK (I can't think of any examples that would break this), but it seems like a potential problem. This is a really contrived idea, but what if the street suffix "Ca" for "calle" catches on? Your code wouldn't know how to tell apart CAlle from CAlifornia.

2. It doesn't return nil if the state is missing from where it's supposed to be, but present somewhere else, like in the street address. For example, try running your program on an address like "1000 NC HWY 70, RALEIGH, 27602." Assuming you have "HWY" listed as a suffix, you would expect nil (because the state is missing), but you would get #user.UsAddress{:street "1000 NC HWY", :city "", :state "NC", :zipcode "27602"}. The problem is that you're working with indices and the state-index has the potential to fall within the street address rather than after the city where you would expect it. This is only a problem if the state is missing from where it belongs, but it's still a problem.

I can think of two potential approaches that might be better:

A. Iterate through the address "parts" in reverse -- look at the last thing and see if it qualifies as a zip code -- if so, move on and look at the next-to-last thing -- does it qualify as a state or state abbreviation? if so, hang onto the state abbrevation and move on. Then you can separate the street address from the city by looking for the last thing that qualifies as a street suffix.

B. Use a parsing library such as Instaparse. This would be my preferred approach. I've found that using a parsing library tends to greatly simplify things, as the library does all of the hard work for you. All you have to do is specify a grammar and wrap it in a parser, then do (your-parser address-string) and it will return a structure (called a "parse tree") something like this:

[:address
  [:street-address "3526 HIGH" [:suffix "ST"]]
  [:city "SACRAMENTO"]
  [:state "CA"]
  [:zip "95838"]]

If you're new to defining a PEG grammar, there is a small learning curve, but it's actually surprisingly simple once you get the hang of it. Your grammar would look something like this:

address        = street-address <ows> city <ows> state <ows> zip
street-address = word+ suffix
city           = word+
word           = !suffix \w+ <ows>    
suffix         = "ST" | "STREET" | "DR" | "DRIVE" (* etc. *)
state          = "AK" | "AL" | (* etc. *)
zip            = #"\d{5}"
ows            = #"[\s,]*"   (* optional whitespace / commas *)

(Note: I haven't tested the above, so it may or may not work properly.)

From there, it's easy to transform your parse tree into whatever form you'd like to represent each address. Personally I find this method easier, and it definitely makes your code look a lot cleaner and simpler.

Answer 2

The following is the solution I came up with which is based on @Dave Yarwood first solution. It uses helper functions and it reduces whens and lets, but I didn't agree with his usage of (parts), though I did agree with the usage of threading: ->. It was parsing the line each time it was used (6 times), which could be a big deal if the line was long. I don't know if the line will be an address or not, so parsing a really long line 6 times was too much for me.

(defrecord UsAddress [street city state zipcode])

(defn- find-last-occurrence-index-of [lookup-map coll]
  (last (keep-indexed #(when (contains? lookup-map %2) %1) coll)))

(defn- split-potential-address-into-parts [s]
  (-> s (s/replace #"," "") s/upper-case (s/split #"\s+")))

(defn extract-us-address [s] 
  (let [parts (split-potential-address-into-parts s)
        state-index (find-last-occurrence-index-of state-abbreviation-lookup parts)
        street-index (find-last-occurrence-index-of street-suffix-lookup parts)
        zip-code (re-matches #"^\d{5}$" (last parts))]
    (when (and zip-code street-index state-index (< street-index state-index))
      (UsAddress. 
        (s/join " " (take (inc street-index) parts))
        (s/join " " (drop (inc street-index) (take state-index parts)))
        (state-abbreviation-lookup (nth parts state-index))
        zip-code))))

Answer 3

The following is the solution I came up with which is based on @Dave Yarwood second solution. He only provided the grammar and I'm including my implementation of handling the parse tree returned by instaparse. His grammar was very close, but it would split avenue at ave and would return the remaining nue as the first part of the city. I was able to correct for that usecase, but it still fails if the street contains a suffix (such as 3526 AVENUE ST). Overall, I feel the readability of instaparse is much better, but it was slower

(def ^:private parse-us-address-into-tree
  (letfn [(combine-strings-to-pattern [strings]
            (s/join " | " (map (partial format "'%s'") strings)))]
    (insta/parser
      (format 
      "<address>      = street-address <ows> city <ows> state <ows> zip
       street-address = word+ suffix
       city           = word+
       word           = #'\\w+' | #'\\w+' <ows>    
       suffix         = %s
       state          = %s
       zip            = #'\\d{5}'
       ows            = #'[\\s,]+'"
        (combine-strings-to-pattern (keys street-suffix-lookup))
        (combine-strings-to-pattern (keys state-abbreviation-lookup))))))


(defn- combine-words [parse-words]
  (s/join " " 
          (map (comp s/trim second) parse-words)))

(defn- extract-address-from-parse-tree [parse-tree]
  (let [[street-address-parts city-parts state-parts zip-code-parts] (map rest parse-tree)
        street-address-suffix (get street-suffix-lookup (second (last street-address-parts)))
        street-address-root (combine-words (butlast street-address-parts))
        street-address (s/join " " (list street-address-root street-address-suffix))
        city (combine-words city-parts)
        state (get state-abbreviation-lookup (first state-parts))
        zip-code (first zip-code-parts)]
      (UsAddress. 
        street-address
        city
        state
        zip-code)))

(defn parse-us-address [s]
  (let [parse-tree (parse-us-address-into-tree (s/upper-case s))]
    (when-not (insta/failure? parse-tree)
      (extract-address-from-parse-tree parse-tree))))

tests

(deftest parse-us-address-test
  (testing "parse-us-address"
    (testing "should determine if string is a US address"
      (are [i o] (= (parse-us-address i) o)
        "3526 HIGH ST SACRAMENTO CA 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 HIGH ST SACRAMENTO, CA 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 HIGH ST SACRAMENTO California 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 HIGH ST SACRAMENTO, California 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 high st sacramento ca 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 high st sacramento, ca 95838"  (UsAddress. "3526 HIGH ST" "SACRAMENTO" "CA" "95838")
        "3526 CALIFORNIA ST SACRAMENTO CA 95838"  (UsAddress. "3526 CALIFORNIA ST" "SACRAMENTO" "CA" "95838")
        "3526 CALIFORNIA ST SACRAMENTO, CA 95838"  (UsAddress. "3526 CALIFORNIA ST" "SACRAMENTO" "CA" "95838")
        ; FIXME double suffix isn't handled correctly in parse rules
        ; "3526 AVENUE ST SACRAMENTO CA 95838"  (outlierdetection.attribute.UsAddress. "3526 AVENUE ST" "SACRAMENTO" "CA" "95838")
        ; "3526 AVENUE ST SACRAMENTO, CA 95838"  (outlierdetection.attribute.UsAddress. "3526 AVENUE ST" "SACRAMENTO" "CA" "95838")
        "CONEJO RANCHO MURIETA, CA 95683" nil
        "California"  nil
        "CA"  nil
        ""  nil
        "SACRAMENTO"  nil
        "95838"  nil
        "1000 NC HWY 70, RALEIGH, 27602" nil
        "3526 HIGH STREET"  nil
        "304 867 5309" nil))))