4
\$\begingroup\$

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))))
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Thank you for your response, very insiteful. I posted two answers based upon your suggestions. Overall, I agree with helper functions, leaving defn at the top level, and combining when/let. The code seems to flow much better, however I wasn't ok with useing (parts) It was doing too much work too many times. Secondly, great suggestion with instaparse. I appreciate thinking out of the box. As I mentioned in my answer, your grammar was pretty much dead on. I only needed minor tweaks. The code seems to be much easier to read. However, it is a bit slower. \$\endgroup\$ – pgreen2 Jul 12 '14 at 3:45
  • \$\begingroup\$ Good catch on parts! I don't know how I missed that -- you could easily just make it part of the let binding for the extract-us-address function, and that way it is only evaluated once. \$\endgroup\$ – Dave Yarwood Jul 14 '14 at 11:46
  • \$\begingroup\$ And kudos on your revised solutions! Both are very nice. I'm tempted to say the non-instaparse solution is better because it's shorter and more performant, but the advantage of the instaparse solution is that it's super flexible -- changing the way an address is parsed is just a matter of editing the grammar. On the other hand, though, this might be a simple enough use case that your other solution is good enough, without having to involve a PEG grammar. \$\endgroup\$ – Dave Yarwood Jul 14 '14 at 11:49
1
\$\begingroup\$

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))))
\$\endgroup\$
1
\$\begingroup\$

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)))) 
\$\endgroup\$
  • \$\begingroup\$ Writing a grammar can be tricky! Major kudos for taking it a step beyond what I could figure out. The key to catching the whole word "avenue" instead of "ave" is just to list "avenue" first in your list of possible suffixes -- the parser will then look for "avenue" before it looks for "ave." I think the key to catching cases like "Avenue St" has to do with negative lookahead, but admittedly I've never really understood how to use that correctly :) \$\endgroup\$ – Dave Yarwood Jul 14 '14 at 11:59
  • \$\begingroup\$ On second thought, maybe a positive lookahead would fix it? street-address = word+ &suffix i.e. any number of words, and the next thing has to be a suffix. I believe the parser will then parse the longest possible string of words ending in a street suffix as the street address, because of greedy consumption. \$\endgroup\$ – Dave Yarwood Jul 14 '14 at 12:04
  • \$\begingroup\$ ...ah, nevermind. There would still be an inherent problem in that it's ambiguous whether a given word like "avenue" should be considered a "street address word" or a suffix. I'm actually not sure whether or not you can solve this problem using a PEG grammar. \$\endgroup\$ – Dave Yarwood Jul 14 '14 at 12:06
  • \$\begingroup\$ That was the same conclusion I came to as well. I can either fix it for street address or city, but not both. \$\endgroup\$ – pgreen2 Jul 14 '14 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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