Existe-t-il un moyen de filtrer un jeu de requête django basé sur la similarité de chaîne (à la python difflib)?

Question

J'ai besoin de faire correspondre les prospects froids à une base de données de nos clients. Les prospects proviennent d'un fournisseur tiers en masse (des milliers d'enregistrements) et les ventes nous demandent (selon leurs propres termes) de "filtrer nos clients" afin qu'ils n'essaient pas de vendre notre service à un client établi .

Évidemment, il y a des fautes d'orthographe dans les fils. Charles devient Charlie, Joseph devient Joe, etc. Je ne peux donc pas vraiment faire un filtre comparant lead_first_name à client_first_name, etc.

Je dois utiliser un mécanisme string similarity.

En ce moment j'utilise la belle difflib pour comparer les prénoms et les noms des prospects à une liste générée avec Client.objects.all(). Cela fonctionne, mais en raison du nombre de clients, il a tendance à être lent.

Je sais que la plupart des bases de données sql ont des fonctions soundex et difference. Voir mon test dans la mise à jour ci-dessous - il ne fonctionne pas aussi bien que difflib.

Existe-t-il une autre solution? Y a-t-il une meilleure solution?

Edit:

Soundex, au moins dans ma db, ne se comporte pas aussi bien que difflib.

Voici un test simple - chercher "Joe Lopes" dans une table contenant "Joseph Lopes":

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') >= 3 
order by difference(first_name+' '+last_name, 'Joe Lopes') 

Les rendements ci-dessus "Joe Satriani" comme le seul match. Même en réduisant le seuil de similarité à 2, on ne retrouve pas "Joseph Lopes" en tant que correspondance potentielle.

Mais difflib fait un travail beaucoup mieux:

difflib.get_close_matches('Joe Lopes', ['Joseph Lopes', 'Joe Satriani', 'CZ Lopes', 'Blah Lopes', 'Antonio Lopes', 'Carlos Lopes']) 
['Joseph Lopes', 'CZ Lopes', 'Carlos Lopes'] 

Modifier après la réponse gruszczy:

Avant d'écrire mon propre, je regardais et found a T-SQL implementation of Levenshtein Distance in the repository of all knowledge.

En testant, il reste ne fera pas un meilleur travail de comparaison que difflib.

Ce qui m'a conduit à rechercher quel algorithme est derrière difflib. Il semble être un modified version de l'algorithme Ratcliff-Obershelp. Malheureusement, je n'arrive pas à trouver quelqu'un d'autre qui ait déjà créé une implémentation T-SQL basée sur difflib ... Je vais essayer quand je le pourrai.

Si personne d'autre ne trouve une meilleure réponse dans les prochains jours, je l'accorderai à gruszczy. Merci, gentil monsieur.

Answer 1

soundex ne vous aidera pas, parce que c'est un algorithme phonétique. Joe et Joseph ne sont pas similaires phonétiquement, donc soundex ne les marquera pas comme similaires.

Vous pouvez essayer Levenshtein distance, qui est implémenté dans PostgreSQL.Peut-être que dans votre base de données aussi et sinon, vous devriez être capable d'écrire une procédure stockée, qui va calculer la distance entre deux chaînes et l'utiliser dans votre calcul.

Answer 2

Il est possible avec trigram_similar depuis Django 1.10 lookups, voir docs pour PostgreSQL specific lookups et Full text search