Высокопроизводительная массовая короткая строка поиска в Python

Question

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

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

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

Но это безумие медленно, когда А содержит ~ 500000 или более пунктов.

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

Спасибо!

Answer 1

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

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

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

Есть также ссылки в родственном сообщении переполнения стеки, которые упоминают другие алгоритмы, такие как Рабин-Карп: Algorithm for linear pattern matching?

Answer 2

Я не знаю, если это будет какой-нибудь быстрее, но это намного больше вещий:

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

Answer 3

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

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

Answer 4

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

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) 

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

Answer 5

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

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

1. предвычислять некоторые хэш для каждого ключевого слова (например, исключающего хэш):

   hash256 = reduce(int.__xor__, map(ord, keyword)) 
   

2. создать словарь, где ключ является хэш и список значений из соответствующих ключевых слов

3. сохранить длину ключевого слова

   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:] 
   

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