Проблема: большой статический список строк представлен как A, длинная строка предоставляется как B, строки в A очень короткие (список ключевых слов), я хочу проверить, строка в A является подстрокой B и получает их.
Теперь я использую простой цикл, например:
result = []
for word in A:
if word in B:
result.append(word)
Но он сумасшедший, когда A содержит ~ 500 000 или более элементов.
Есть ли библиотека или алгоритм, который подходит для этой проблемы? Я старался изо всех сил искать, но не повезло.
Спасибо!
Ваша проблема достаточно велика, что вам, вероятно, нужно ударить ее с помощью алгоритма bat.
Взгляните на алгоритм Aho-Corasick. Ваш оператор проблемы - это парафраз проблемы, которую этот алгоритм решает.
Кроме того, изучите работу Николаса Лехуэна с его пакетом PyTST.
В соответствующем сообщении есть ссылки, в которых упоминаются другие алгоритмы, такие как Rabin-Karp: Алгоритм для линейного сопоставления шаблонов?
В зависимости от продолжительности вашей длинной строки, возможно, стоит сделать что-то вроде этого:
ls = 'my long string of stuff'
#Generate all possible substrings of ls, keeping only uniques
x = set([ls[p:y] for p in range(0, len(ls)+1) for y in range(p+1, len(ls)+1)])
result = []
for word in A:
if word in x:
result.append(word)
Очевидно, что если длинная строка очень длинная, то она также становится слишком медленной, но она должна быть быстрее для любой строки под несколькими сотнями символов.
Я не знаю, будет ли это быстрее, но это намного больше pythonic:
result = [x for x in A if x in B]
Упакуйте все отдельные слова B в новый список, состоящий из исходной строки, разделенной на ' '. Затем, для каждого элемента в B, проверьте принадлежность к каждому элементу A. Если вы найдете одно (или больше), удалите его/их из A и закройте, как только A будет пустым.
Похоже, что ваш подход будет накаляться через 500 000 кандидатов без установки отказа.
Предположим, что у вас есть все ключевые слова одинаковой длины (позже вы могли бы расширить этот алгоритм для разных длин)
Я мог бы предложить следующее:
предварительно вычислить некоторый хеш для каждого ключевого слова (например, хэш-хэш):
hash256 = reduce(int.__xor__, map(ord, keyword))
создать словарь, где ключ - хеш, и список значений соответствующих ключевых слов
сохранить длину ключевого слова
curr_keyword = []
for x in B:
if len(curr_keyword) == keyword_length:
hash256 = reduce(int.__xor__, map(ord, curr_keyword))
if hash256 in dictionary_of_hashed:
#search in list
curr_keyword.append(x)
curr_keyword = curr_keyword[1:]
Что-то вроде этого