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

Question

У меня есть необходимость совместить холодные провода с базой данных наших клиентов.

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

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

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

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

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

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

Edit:

Саундэкс, по крайней мере, в моем дб, не ведет себя так же, как difflib.

Вот простой тест - искать «Джо Лопеса» в таблице, содержащей «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') 

Вышеприведенные возвращает «Джо Сатриани» в качестве единственного матча. Даже уменьшение порога подобия до 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'] 

Edit после ответа gruszczy в:

Прежде чем писать мои собственные, я искал и found a T-SQL implementation of Levenshtein Distance in the repository of all knowledge.

В тестировании, он по-прежнему не будет выполнять более подходящую работу, чем difflib.

Это привело меня к изучению того, какой алгоритм стоит за difflib. Кажется, это modified version алгоритма Ratcliff-Obershelp.

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

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

Answer 1

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

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

Answer 2

Это возможно с trigram_similar поисками, начиная с Django 1.10 см документации для PostgreSQL specific lookups и Full text search