title: Is there a way to filter a django queryset based on string similarity (a la python difflib)?
body: <p>I have a need to match cold leads against a database of our clients. </p>
  
  <p>The leads come from a third party provider in bulk (thousands of records) and sales is asking us to (in their words) "filter out our clients" so they don't try to sell our service to a established client.</p>
  
  <p>Obviously, there are misspellings in the leads. Charles becomes Charlie, Joseph becomes Joe, etc. So I can't really just do a filter comparing lead_first_name to client_first_name, etc. </p>
  
  <p>I need to use some sort of <a href="https://stackoverflow.com/questions/682367/good-python-modules-for-fuzzy-string-comparison">string similarity</a> mechanism.</p>
  
  <p>Right now I'm using the lovely <a href="http://docs.python.org/library/difflib.html" rel="nofollow noreferrer">difflib</a> to compare the leads' first and last names to a list generated with <code>Client.objects.all()</code>. It works, but because of the number of clients it tends to be slow.</p>
  
  <p>I know that most sql databases have soundex and difference functions. See my test of it in the update below - it doesn't work as well as difflib.</p>
  
  <p>Is there another solution? Is there a better solution?</p>
  
  <p><strong>Edit:</strong></p>
  
  <p>Soundex, at least in my db, doesn't behave as well as difflib. </p>
  
  <p>Here is a simple test - look for "Joe Lopes" in a table containing "Joseph Lopes":</p>
  
  <pre><code>with temp (first_name, last_name) as (
  select 'Joseph', 'Lopes'
  union
  select 'Joe', 'Satriani'
  union
  select 'CZ', 'Lopes'
  union
  select 'Blah', 'Lopes'
  union
  select 'Antonio', 'Lopes'
  union
  select 'Carlos', 'Lopes'
  )
  select first_name, last_name
    from temp
   where difference(first_name+' '+last_name, 'Joe Lopes') &gt;= 3
   order by difference(first_name+' '+last_name, 'Joe Lopes')
  </code></pre>
  
  <p>The above returns "Joe Satriani" as the only match. Even reducing the similarity threshold to 2 doesn't return "Joseph Lopes" as a potential match.</p>
  
  <p>But difflib does a much better job:</p>
  
  <pre><code>difflib.get_close_matches('Joe Lopes', ['Joseph Lopes', 'Joe Satriani', 'CZ Lopes', 'Blah Lopes', 'Antonio Lopes', 'Carlos Lopes'])
  ['Joseph Lopes', 'CZ Lopes', 'Carlos Lopes']
  </code></pre>
  
  <p><strong>Edit after gruszczy's response:</strong></p>
  
  <p>Before writing my own, I looked for and <a href="https://stackoverflow.com/questions/560709/levenstein-distance-in-t-sql">found a T-SQL implementation of Levenshtein Distance in the repository of all knowledge.</a></p>
  
  <p>In testing it, it still won't do a better matching job than difflib. </p>
  
  <p>Which led me to research what algorithm is behind difflib. It seems to be a <a href="http://docs.python.org/library/difflib.html#difflib.SequenceMatcher" rel="nofollow noreferrer">modified version</a> of the <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/ratcliffObershelp.html" rel="nofollow noreferrer">Ratcliff-Obershelp</a> algorithm.</p>
  
  <p>Unhappily I can't seem to find some other kind soul who has already created a T-SQL implementation based on difflib's... I'll try my hand at it when I can.</p>
  
  <p>If nobody else comes up with a better answer in the next few days, I'll grant it to gruszczy. Thanks, kind sir.</p>