title: Speeding up a "closest" string match algorithm
body: <p>I am currently processing a very large database of locations and trying to match them with their real world coordinates. </p>
  
  <p>To achieve this, I have downloaded <a href="https://www.geonames.org/export/" rel="noreferrer">the geoname dataset</a> which contains a lot of entries. It gives possible names and lat/long coordinates. To try and speed up the process, I have managed to reduce the huge csv file (of 1.6 GB) to 0.450 GB by removing entries that do not make sense for my dataset. It still contains however 4 million entries.</p>
  
  <p>Now I have many entries such as:</p>
  
  <ol>
  <li>Slettmarkmountains seen from my camp site in Jotunheimen, Norway, last week</li>
  <li>Adventuring in Fairy Glen, Isle of Skye, Scotland, UK</li>
  <li>Morning in Emigrant Wilderness, California</li>
  </ol>
  
  <p>Knowing that string matching with such long strings, I used <a href="https://nlp.stanford.edu/software/tagger.shtml" rel="noreferrer">Standford's NER</a> via NLTK to get a better string to qualify my location. Now I have strings like:</p>
  
  <ol>
  <li>Slettmarkmountains Jotunheimen Norway</li>
  <li>Fairy Glen Skye Scotland UK</li>
  <li>Emigrant Wilderness California</li>
  <li>Yosemite National Park</li>
  <li>Half Dome Yosemite National Park</li>
  </ol>
  
  <p>The geoname dataset contains things like:</p>
  
  <ol>
  <li>Jotunheimen Norway Lat Long </li>
  <li>Slettmarkmountains Jotunheimen Norway Lat Long</li>
  <li>Bryce Canyon Lat Long</li>
  <li>Half Dome Lat Long</li>
  <li>...</li>
  </ol>
  
  <p>And I am applying this <a href="http://www.catalysoft.com/articles/StrikeAMatch.html" rel="noreferrer">algorithm</a> to get a good possible match between my entries and the geoname csv containing 4M entries. I first read the geoname_cleaned.csv file and put all of the data into a list. For each entry I have I then call for each one of my entries <code>string_similarity()</code> between the current entry and all the entries of the geoname_list </p>
  
  <pre><code>def get_bigrams(string):
      """
      Take a string and return a list of bigrams.
      """
      s = string.lower()
      return [s[i:i+2] for i in list(range(len(s) - 1))]
  
  def string_similarity(str1, str2):
      """
      Perform bigram comparison between two strings
      and return a percentage match in decimal form.
      """
      pairs1 = get_bigrams(str1)
      pairs2 = get_bigrams(str2)
      union  = len(pairs1) + len(pairs2)
      hit_count = 0
      for x in pairs1:
          for y in pairs2:
              if x == y:
                  hit_count += 1
                  break
      return (2.0 * hit_count) / union
  </code></pre>
  
  <p>I have tested the algorithm on a subset of my original dataset and it works fine but it is obviously terribly slow (takes up to 40 seconds for a single location). Since I have more than a million entries to process, this will take a good 10000 hours or more. I was wondering if you guys had any idea on how to speed this up. I thought of parallel processing obviously but I don't have any HPC solution available. Perhaps simple ideas could help me speed this up.</p>
  
  <p>I'm open to any and every idea that you guys might have but would somehow prefer a python-compatible solution.</p>
  
  <p>Thanks in advance :).</p>
  
  <p>Edit:</p>
  
  <p>I have tried fuzzywuzzy with <code>fuzz.token_set_ratio(s1, s2)</code> and it gives worst performances (running time is worse, and results are not as good). Matches are not as good as they used to be with my custom technique and running time has increased by a good 15 seconds for a single entry.</p>
  
  <p>Edit 2: </p>
  
  <p>I also though of using some kind of sorting at the beginning to help with the matching but my naive implementation would not work. But I'm sure there are some ways to speed this up, by perhaps getting rid of some entries in geoname dataset, or sorting them in some way. I already did a lot of cleaning to remove useless entries, but can't get the number much lower than 4M </p>