Нечеткое сравнение строк в списках огромной длины (с учетом производительности) ⇐ Python

[Anonymous]

У меня есть два списка:
Первый список, который я получаю из базы данных, — это названия различных компаний (могут быть написаны прописными, строчными буквами или их комбинацией)

list_from_DB = ["Reebok", "MAZDA", "PATROL", "AsbEngland-bank", "Mazda INCC",
"HIGHWAY lcc", "mazda", "015 Amazon", ......]

В этом списке около 400 000 элементов.

Второй список я получаю путем парсинга текста от пользователя (здесь могут быть абсолютно любые слова, цифры, знаки и т.д.)

list_from_user = ['ts', '$243', 'mazda', 'OFFICERS', 'SIGNATURE',
'Date:07/20/2022', 'Wilson', 'Bank', .......]

В этом списке около 1000 элементов.

Что мне нужно сделать, так это найти, какие элементы из list_from_user находятся в list_from_DB и отобразите их в порядке наибольшего сходства. Как видно ниже, элементы в двух списках могут быть идентичными или различаться по написанию.
Вывод

["mazda", "MAZDA", "Mazda INCC", "AsbEngland-bank"]


Что я делаю: да, я знаю о библиотеках нечеткого сопоставления символов, я используйте RapidFuzz.

Код: Выделить всё

res = []
for e in list_from_user:
r = rapidfuzz.process.extract_iter(e, list_from_DB, processor=str.lower, scorer=rapidfuzz.fuzz.ratio, score_cutoff=95)
res += r

Да, результат рабочий, но очень долго, около 30 секунд, так как цикл должен выполнить 1000 * 400.000 = 400.000.000 операций.
Поэтому вопрос следующий: можно ли решить эту задачу не перебором всех вариантов, а каким-то другим способом? (Я не против метода с перебором всех вариантов, но если он подходит по времени)
Моя цель по времени — максимум 3 секунды.

Подробнее здесь: https://stackoverflow.com/questions/769 ... nt-perform