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

Question

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

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

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

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

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

Спасибо!

Answer 1

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

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

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

Также есть ссылкив связанном сообщении переполнения стека, в котором упоминаются другие алгоритмы, такие как Рабин-Карп: Алгоритм для линейного сопоставления с образцом?

Answer 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)

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

Answer 3

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

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

1. предварительно рассчитать некоторый хешкаждое ключевое слово (например, xor hash):

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

Примерно так

Answer 4

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

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

Answer 5

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

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