有没有办法根据字符串相似度过滤 django 查询集（la python difflib）？

Question

我需要将冷线索与我们客户的数据库进行匹配。

潜在客户大量来自第三方提供商（数千条记录），销售人员要求我们（用他们的话说）“过滤掉我们的客户”，这样他们就不会试图向现有客户出售我们的服务。

显然，线索中存在拼写错误。查尔斯变成查理，约瑟夫变成乔，等等。所以我真的不能只做一个过滤器比较 Lead_first_name 和 client_first_name 等。

我需要使用某种 字符串相似度机制。

现在，我正在使用可爱的 difflib 来比较潜在客户的名字和姓氏使用 Client.objects.all() 生成的列表。它有效，但由于客户端数量较多，速度往往很慢。

我知道大多数sql数据库都有soundex和difference函数。请参阅下面的更新中我对它的测试 - 它的工作效果不如 difflib。

还有其他解决方案吗？有更好的解决方案吗？

编辑：

Soundex，至少在我的数据库中，表现不如 difflib。

这是一个简单的测试 - 在包含“Joseph Lopes”的表中查找“Joe 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')

上面返回“Joe Satriani”作为唯一匹配项。即使将相似度阈值降低到 2，也不会返回“Joseph Lopes”作为潜在匹配项。

但 difflib 做得更好：

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

在 gruszczy 的回复后编辑：

在编写自己的内容之前，我查找并 在所有知识库中找到了Levenshtein Distance的T-SQL实现。

在测试中，它仍然不会比difflib做更好的匹配工作。

这促使我研究 difflib 背后的算法。它似乎是 修改版本 ://www.itl.nist.gov/div897/sqg/dads/HTML/ratcliffObershelp.html" rel="noreferrer">Ratcliff-Obershelp 算法。

不幸的是，我似乎找不到其他已经创建了基于 difflib 的 T-SQL 实现的人...我会尽可能尝试一下。

如果在接下来的几天内没有其他人提出更好的答案，我会将其授予 gruszczy。谢谢，好心的先生。

Answer 1

根据 andilabs 的答案，您可以使用 Levenshtein 函数来创建自定义函数。 Postgres doc表明Levenshtein函数如下：

levenshtein(文本源，文本目标，int ins_cost，int del_cost，int sub_cost）返回int
levenshtein(text source, text target) returns int

andilabs 答案可以使用唯一的第二个函数。如果您想要具有插入/删除/替换成本的更高级搜索，您可以像这样重写函数：

from django.db.models import Func

class Levenshtein(Func):
    template = "%(function)s(%(expressions)s, '%(search_term)s', %(ins_cost)d, %(del_cost)d, %(sub_cost)d)"
    function = 'levenshtein'

    def __init__(self, expression, search_term, ins_cost=1, del_cost=1, sub_cost=1, **extras):
        super(Levenshtein, self).__init__(
            expression,
            search_term=search_term,
            ins_cost=ins_cost,
            del_cost=del_cost,
            sub_cost=sub_cost,
            **extras
        )

并调用该函数：

from django.db.models import F

Spot.objects.annotate(
    lev_dist=Levenshtein(F('name'), 'Kfaka', 3, 3, 1)  # ins = 3, del = 3, sub = 1
).filter(
    lev_dist__lte=2
)

Answer 2

soundex 不会帮助你，因为它是一种语音算法。 Joe 和 Joseph 在语音上并不相似，因此 soundex 不会将它们标记为相似。

您可以尝试 Levenshtein distance，它是在 PostgreSQL 中实现的。也许也在您的数据库中，如果没有，您应该能够编写一个存储过程，它将计算两个字符串之间的距离并在计算中使用它。

Answer 3

自 Django 1.10 起，可以使用 trigram_similar 查找，请参阅文档了解 PostgreSQL 特定查找 和 全文搜索

Answer 4

如果您需要使用 django 和 postgres 实现这一目标，并且不想使用 1.10 trigram-similarity 中引入的 https://docs.djangoproject.com/en/2.0/ref/contrib/postgres/lookups/#trigram-similarity 您可以使用 Levensthein 实现，如下所示：

< strong>需要扩展 fuzzystrmatch

您需要将 postgres 扩展添加到 psql 中的数据库：

CREATE EXTENSION fuzzystrmatch;

让我们定义自定义函数，我们可以用它来注释查询集。它只需要一个参数 search_term 并使用 postgres levenshtein 函数（请参阅文档）：

from django.db.models import Func

class Levenshtein(Func):
    template = "%(function)s(%(expressions)s, '%(search_term)s')"
    function = "levenshtein"

    def __init__(self, expression, search_term, **extras):
        super(Levenshtein, self).__init__(
            expression,
            search_term=search_term,
            **extras
        )

然后在项目中的任何其他位置，我们只需导入定义的 Levenshtein 和 F 来传递 django 字段。

from django.db.models import F

Spot.objects.annotate(
    lev_dist=Levenshtein(F('name'), 'Kfaka')
).filter(
    lev_dist__lte=2
)