Для этого ответа я буду работать со следующими данными:
import string
import random
random.seed(18)
str_options = string.ascii_uppercase + string.ascii_lowercase + string.digits + ' '
query = \'\'.join(random.choice(str_options) for _ in range(30))
choices = [\'\'.join(random.choice(str_options) for _ in range(30)) for s in range(6500000)]
Я не буду сейчас использовать многопроцессорность, но это можно сделать и параллельно.
1) это примерно то, как выглядит ваше текущее решение:
from fuzzywuzzy import fuzz
results = []
for choice in choices:
if fuzz.QRatio(query, choice) >= 80:
results.append(choice)
Как вы упомянули, fuzzywuzzy уже использует python -Levenshtein для вычислений Левенштейна, что довольно оптимизировано. Однако перед вычислением fuzzywuzzy проверяет, являются ли обе строки пустыми или равными, чтобы он мог вернуться раньше, не вычисляя расстояние Левенштейна. Хотя это звучит как хорошая идея, на самом деле это не так, поскольку для проверки того, совпадают ли две строки, требуется перебрать всю строку, чтобы проверить ее. Намного лучше удалить общий префикс и суффикс перед вычислением левенштейна (ускоряет его, например, для одинаковых строк он линейен во времени). Это немного медленнее, когда строки точно такие же, но при работе с нечеткими данными это очень маловероятно. Это первое решение работает примерно на 55 seconds на моей машине
2) Это заменяет fuzzywuzzy на RapidFuzz (я автор), который является лицензированной MIT повторной реализацией FuzzyWuzzy, которая в основном реализована в C ++ и работает намного лучше, поскольку он исправляет довольно много проблем с производительностью в FuzzyWuzzy
from rapidfuzz import fuzz
results = []
for choice in choices:
if fuzz.QRatio(query, choice) >= 80:
results.append(choice)
Для этого требуется только 18 seconds на моей машине, так что это уже примерно 3-кратное улучшение. Другая проблема заключается в том, что при использовании fuzz.QRatio обе строки предварительно обрабатываются, чтобы они были строчными и удалялись некоторые нежелательные символы. Хотя это обычно имеет смысл, это означает, что запрос здесь получает предварительную обработку 6,5 миллионов раз, а не один раз.
3) Это только один раз выполняет предварительную обработку запроса
from rapidfuzz import fuzz, utils
results = []
processed_query = utils.default_process(query)
for choice in choices:
processed_choice = utils.default_process(choice)
if fuzz.ratio(processed_query, processed_choice, score_cutoff=80):
results.append(choice)
Это занимает 14 seconds на моем машина. Это показывает, что вы, возможно, захотите сохранить свои имена файлов в предварительно обработанном виде, поэтому вам не нужно их предварительно обрабатывать при поиске (это снизит его примерно до 11 seconds). На этом этапе основным требованием времени является вычисление расстояния Левенштейна, что является операцией O (m * n). Так что было бы хорошо уменьшить количество результатов там, где это нужно сделать. Быстрый способ, который уже используется RapidFuzz по умолчанию, - это сравнение длины двух строк, поскольку они не могут достичь требуемого соотношения, когда они имеют большую разницу в длине, и могут быть рассчитаны за постоянное время, поскольку длины в любом случае уже известны. . Однако в моем тестовом примере это никогда не будет применяться, так как все строки имеют длину 30. Есть второе соотношение строк, которое я реализовал для вызова RapidFuzz fuzz.quick_lev_ratio, который оценивает расстояние Левенштейна путем подсчета необычных букв между двумя строками. Таким образом, он всегда будет возвращать соотношение для отсортированных строк fuzz.ratio(''.join(sorted(s1)), ''.join(sorted(s2))), которое гарантированно будет таким же высоким или большим, чем fuzz.ratio(s1, s2), но может быть вычислено за линейное время
4) фильтрует выбор, используя fuzz.quick_lev_ratio перед их сравнением
from rapidfuzz import fuzz, utils
results = []
processed_query = utils.default_process(query)
for choice in choices:
processed_choice = utils.default_process(choice)
if not fuzz.quick_lev_ratio(processed_query, processed_choice, score_cutoff=80, processor=None):
continue
if fuzz.ratio(processed_query, processed_choice, score_cutoff=80, processor=None):
results.append(choice)
Для этого окончательного решения требуется только 7 seconds на моей машине (или 4 seconds, если предварительная обработка вариантов не требуется). Когда требуется еще более быстрое решение, вы все равно можете рассчитать этот последний вариант на нескольких ядрах. Вы также можете использовать версию C ++ RapidFuzz- cpp (она еще не имеет всех функций из версии python, но достаточно для ее реализации)
Чистая версия C ++ RapidFuzz еще требует небольшой доработки и особенно документации, но это можно реализовать с его помощью следующим образом:
using rapidfuzz::string_utils::default_process;
using rapidfuzz::fuzz::quick_lev_ratio;
using rapidfuzz::fuzz::ratio;
std::string query("example");
std::vector<std::string> choices{"example", "example2", "example3"};
std::string processed_query = default_process(query);
std::vector<std::string> results;
for (const auto& choice : choices) {
std::string processed_choice = default_process(choice);
if (!quick_lev_ratio(processed_query, processed_choice, 80)) {
continue;
}
if (ratio(processed_query, processed_choice, 80)) {
results.push_back(choice);
}
}