Levenshtein Distance
I&#x27;ve been playing around with the data made available [1] by the states that are part of the Streamlined Sales Tax system [2].<p>The boundary file address records include, among other things:<p><pre><code>  address range start
  address range end
  odd&#x2F;even&#x2F;both flag
  directional prefix
  street name
  street suffix
  directional postfix
  zip code
</code></pre>
The address range specifies the range of numerical addresses that the record applies to, and the odd&#x2F;even&#x2F;both flag indicates if it is for just the odd address, just the even addresses, or both.<p>The direction prefix and suffix are supposed to be one of {blank, N, S, E, W, NE, NW, SE, SW}, but some states botch that and I&#x27;ve seen EA, EB, NO, SO, and WE end up in there.<p>The suffix field is for things like LANE, AVE, ST, and the like. It is a 4 character field, so a street that residents thing of as ELM AVENUE would be name=ELM suffix=AVE in the boundary file. Or it would be name=&quot;ELM AVENUE&quot; with no suffix. (There are even some with AVENUE in the name and something else in the suffix, such as ROOSEVELT AVENUE ALY in Albany GA. The ALY is the suffix). (There are a 318 distinct suffixes across all the SST states, for the curious [3]).<p>Anyway, my point is that the data is kind of loose.<p>I want to be able to take what a user puts on an address form:<p><pre><code>  address
  city
  state
  zip code
</code></pre>
and find a good match in the boundary files. Most people manage to put something reasonable in the city, state, and zip code fields, and manage to put their street address at the start of the address field, so I can pretty reliably get the zip code and the street number. It&#x27;s the rest of the address line that is problematic.<p>At first I was trying to figure out what in there might be prefix, postfix, and suffix to isolate just the street name. But because of both the aforementioned looseness of the boundary data, and differences between how the user might think of their address and how their state thinks of it, this didn&#x27;t work too well.<p>I was considering keeping an index that maps words that occur in street names to those street names, and then looking for the longest word in the user supplied address and looking up all streets in the user&#x27;s zip code that contain that word and that include the user&#x27;s street number. If that returned more than one match, the idea was then to look at the prefix, postfix, and suffix and see how well those matched with things in the user address. Looking at a few addresses that had given me trouble, though, it looked like this plan to resolve them would still be tricky and unreliable.<p>So then I decided to try a Levenshtein distance approach. Given zip, street number, street, where street is whatever the user included in the &quot;address&quot; field after the street number, I pull up all records in my boundary DB that match on zip code and street number. I don&#x27;t even include street name in the query.<p>Then for each result, I take the prefix, name, suffix, and postfix and join them separated by space. I then simply take the one with the smallest Levenshtein distance from what the user supplied. With this, I no longer care if something is name=ELM, suffix=AVE or name=&quot;ELM AVE&quot;, suffix=&quot;&quot;.<p>This has worked remarkably well. Even if the user throws on stuff that doesn&#x27;t belong (some people manage to put the city, state, and&#x2F;or zip in the address box) it usually doesn&#x27;t throw it off. It raises the Levenshtein distance of the correct match by sometimes a lot...but it also raises the incorrect match distances too, so the correct one still wins.<p>The boundary files also have secondary address fields, for things like apartments, unit, suites, and the like. These are an abbreviation (APT, e.g.) and low and high ends of a range, and an odd&#x2F;even&#x2F;both flag. Unfortunately the ranges for these aren&#x27;t always numeric. E.g., there is 695 E MORRILL AVE in Columbus, OH, which has secondary fields of &quot;AP&quot;, &quot;A&quot;, &quot;M&quot;, and the odd&#x2F;even&#x2F;both flag set to both. I assume that means Apartments A-M.<p>So far, I&#x27;ve ignored the secondary address fields. Every time I&#x27;ve seen more than one result for the lowest Levenshtein distance, the matches have been close enough to each other to be in the same taxing districts, so would have the same rate and the tax would be allocated to the same entities, so further resolution is not necessary.<p>At some point I&#x27;ll take my scripts that clean up the raw rate and boundary files and transform them into a form more suitable for DB use, and that make sqlite and mysql databases from those, and that do the address matching and also sales tax lookups by address, and put &#x27;em on Github, but that will probably not be very soon.<p>[1] <a href="https:&#x2F;&#x2F;www.streamlinedsalestax.org&#x2F;Shared-Pages&#x2F;rate-and-boundary-files&#x2F;rate-and-boundary-file-updates" rel="nofollow">https:&#x2F;&#x2F;www.streamlinedsalestax.org&#x2F;Shared-Pages&#x2F;rate-and-bo...</a><p>[2] <a href="https:&#x2F;&#x2F;www.streamlinedsalestax.org&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.streamlinedsalestax.org&#x2F;</a><p>[3] <a href="https:&#x2F;&#x2F;pastebin.com&#x2F;tQLGTGS9" rel="nofollow">https:&#x2F;&#x2F;pastebin.com&#x2F;tQLGTGS9</a>