Есть ли способ отфильтровать набор запросов Django, основанный на сходстве строк (a la python difflib)?

Question

Мне нужно сопоставить холодные выводы с базой данных наших клиентов.

Лидеры поступают от стороннего поставщика в большом количестве (тысячи записей), и продажи просят нас (по их словам) «отфильтровать наших клиентов», чтобы они не пытались продать наш сервис установленному клиенту.

Очевидно, в отведениях есть ошибки. Чарльз становится Чарли, Джозеф становится Джо и т. Д. Поэтому я не могу просто сделать фильтр, сравнивающий lead_first_name с client_first_name и т. Д.

Мне нужно использовать какой-то механизм схожести строк .

Прямо сейчас я использую difflib , чтобы сравнить имена и фамилии потенциальных клиентов со списком, созданным с помощью Client.objects.all(). Это работает, но из-за количества клиентов это имеет тенденцию быть медленным.

Я знаю, что большинство баз данных sql имеют функции soundex и разности. Смотрите мой тест в обновлении ниже - он не работает так же хорошо, как difflib.

Есть ли другое решение? Есть ли лучшее решение?

Edit:

Soundex, по крайней мере, в моем БД, ведет себя не так, как difflib.

Вот простой тест - ищите «Джо Лопес» в таблице, содержащей «Джозеф Лопес»:

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')

Выше приведено «Джо Сатриани» как единственный матч. Даже снижение порога подобия до 2 не возвращает «Джозефа Лопеса» в качестве потенциального совпадения.

Но 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']

Редактировать после ответа Грущчи:

Прежде чем написать свой собственный, я искал и нашел реализацию хранилища Левенштейна-расстояния в T-SQL в хранилище всех знаний.

При тестировании он все равно не справится с работой лучше, чем difflib.

Что привело меня к исследованию того, какой алгоритм стоит за difflib. Кажется, это модифицированная версия алгоритма Ratcliff-Obershelp .

К сожалению, я не могу найти какую-то другую добрую душу, которая уже создала реализацию T-SQL на основе difflib ... Я попробую свои силы, когда смогу.

Если никто не придумает лучшего ответа в ближайшие несколько дней, я передам его грущу. Спасибо, добрый сэр.

Answer 1

Это возможно с trigram_similar поисками, начиная с Django 1.10, см. Документы для Специальных поисков PostgreSQL и Полнотекстовый поиск

Answer 2

soundex вам не поможет, потому что это фонетический алгоритм. Джо и Джозеф не похожи друг на друга фонетически, поэтому soundex не будет помечать их как похожие.

Вы можете попробовать Расстояние Левенштейна , которое реализовано в PostgreSQL. Может быть, в вашей базе данных тоже, а если нет, вы сможете написать хранимую процедуру, которая будет вычислять расстояние между двумя строками и использовать его в ваших вычислениях.

Answer 3

Если вам нужно попасть туда с помощью django и postgres и вы не хотите использовать введенное в 1.10 триграмм-сходство https://docs.djangoproject.com/en/2.0/ref/contrib/postgres/lookups/#trigram-similarity, вы можете реализовать с использованием Левенштейна, например:

Требуется расширение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.1016 *