title: Fuzzy string matching in Python
body: <p>I have 2 lists of over a million names with slightly different naming conventions. The goal here it to match those records that are similar, with the logic of 95% confidence.</p>
  
  <p>I am made aware there are libraries which I can leverage on, such as the FuzzyWuzzy module in Python.</p>
  
  <p>However in terms of processing it seems it will take up too much resources having every string in 1 list to be compared to the other, which in this case seems to require 1 million multiplied by another million number of iterations.</p>
  
  <p>Are there any other more efficient methods for this problem?</p>
  
  <p>UPDATE:</p>
  
  <p>So I created a bucketing function and applied a simple normalization of removing whitespace, symbols and converting the values to lowercase etc...</p>
  
  <pre><code>for n in list(dftest['YM'].unique()):
      n = str(n)
      frame = dftest['Name'][dftest['YM'] == n]
      print len(frame)
      print n
      for names in tqdm(frame):
              closest = process.extractOne(names,frame)
  </code></pre>
  
  <p>By using pythons pandas, the data is loaded to smaller buckets grouped by years and then using the FuzzyWuzzy module, <code>process.extractOne</code> is used to get the best match.</p>
  
  <p>Results are still somewhat disappointing. During test the code above is used on a test data frame containing only 5 thousand names and takes up almost a whole hour.</p>
  
  <p>The test data is split up by.</p>
  
  <ul>
  <li>Name</li>
  <li>Year Month of Date of Birth</li>
  </ul>
  
  <p>And I am comparing them by buckets where their YMs are in the same bucket.</p>
  
  <p>Could the problem be because of the FuzzyWuzzy module I am using? Appreciate any help.</p>