Быстрый поиск коротких строк в Python

Проблема: большой статический список строк представлен как A, длинная строка предоставляется как B, строки в A очень короткие (список ключевых слов), я хочу проверить, строка в A является подстрокой B и получает их.

Теперь я использую простой цикл, например:

result = []
for word in A:
    if word in B:
        result.append(word)

Но он сумасшедший, когда A содержит ~ 500 000 или более элементов.

Есть ли библиотека или алгоритм, который подходит для этой проблемы? Я старался изо всех сил искать, но не повезло.

Спасибо!

Ответ 1

Ваша проблема достаточно велика, что вам, вероятно, нужно ударить ее с помощью алгоритма bat.

Взгляните на алгоритм Aho-Corasick. Ваш оператор проблемы - это парафраз проблемы, которую этот алгоритм решает.

Кроме того, изучите работу Николаса Лехуэна с его пакетом PyTST.

В соответствующем сообщении есть ссылки, в которых упоминаются другие алгоритмы, такие как Rabin-Karp: Алгоритм для линейного сопоставления шаблонов?

Ответ 2

В зависимости от продолжительности вашей длинной строки, возможно, стоит сделать что-то вроде этого:

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)

Очевидно, что если длинная строка очень длинная, то она также становится слишком медленной, но она должна быть быстрее для любой строки под несколькими сотнями символов.

Ответ 3

Я не знаю, будет ли это быстрее, но это намного больше pythonic:

result = [x for x in A if x in B]

Ответ 4

Упакуйте все отдельные слова B в новый список, состоящий из исходной строки, разделенной на ' '. Затем, для каждого элемента в B, проверьте принадлежность к каждому элементу A. Если вы найдете одно (или больше), удалите его/их из A и закройте, как только A будет пустым.

Похоже, что ваш подход будет накаляться через 500 000 кандидатов без установки отказа.

Ответ 5

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

Я мог бы предложить следующее:

предварительно вычислить некоторый хеш для каждого ключевого слова (например, хэш-хэш):
```
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:]

Что-то вроде этого