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

Ответ 1

Может быть, вы можете попытаться разделить один из двух списков (самый большой? Хотя интуитивно я бы порезал listStrings) на меньшие, а затем использовать многопоточность для параллельного выполнения этого поиска (класс multiprocessing Pool предлагает удобный способ сделать это)? У меня было значительное ускорение, используя что-то вроде:

from multiprocessing import Pool
from itertools import chain, islice

# The function to be run in parallel :
def my_func(strings):
    return [j+i for i in strings for j in listSubstrings if i.find(j)>-1]

# A small recipe from itertools to chunk an iterable :
def chunk(it, size):
    it = iter(it)
    return iter(lambda: tuple(islice(it, size)), ())

# Generating some fake & random value :
from random import randint
listStrings = \
    [''.join([chr(randint(65, 90)) for i in range(randint(1, 500))]) for j in range(10000)]
listSubstrings = \
    [''.join([chr(randint(65, 90)) for i in range(randint(1, 100))]) for j in range(1000)]

# You have to prepare the searches to be performed:
prep = [strings for strings in chunk(listStrings, round(len(listStrings) / 8))]
with Pool(4) as mp_pool:
    # multiprocessing.map is a parallel version of map()
    res = mp_pool.map(my_func, prep)
# The 'res' variable is a list of list, so now you concatenate them
# in order to have a flat result list
result = list(chain.from_iterable(res))

Тогда вы можете написать целую переменную result (вместо того, чтобы писать ее построчно):

with open('result_file', 'w') as f:
    f.write('\n'.join(result))

Изменить 01/05/18: сгладить результат, используя itertools.chain.from_iterable вместо уродливого обходного пути с использованием побочных эффектов map, следуя совету ShadowRanger.

Ответ 2

Для того, что вы пытаетесь (ищите фиксированный набор из целой связки строк во множестве других строк), распараллеливание и незначительные изменения не сильно помогут. Вам нужны алгоритмические улучшения.

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

Таким образом, вместо того, чтобы сканировать 60К строк 50K+ раз по каждой (три миллиарда сканирований?!?), Вы можете сканировать их по одному только с чуть более высокой стоимостью, чем при обычном одиночном сканировании, и получить все попадания.

Самое приятное, что ты сам не пишешь. PyPI (индекс пакета Python) уже имеет пакет pyahocorasick, написанный для вас. Так что попробуйте.

Пример использования:

import ahocorasick

listStrings = [ACDE, CDDE, BPLL, ...]
listSubstrings = [ACD, BPI, KLJ, ...]

auto = ahocorasick.Automaton()
for substr in listSubstrings:
    auto.add_word(substr, substr)
auto.make_automaton()

...

for astr in listStrings:
    for end_ind, found in auto.iter(astr):
        w.write(found+astr)

Это будет write несколько раз, если подстрока ("игла") найдена в строке, в которой выполняется поиск ("стог сена"), более одного раза. Вы можете изменить цикл так, чтобы он write только первый удар для данной иглы в данном стоге сена, используя set для дедупликации:

for astr in listStrings:
    seen = set()
    for end_ind, found in auto.iter(astr):
        if found not in seen:
            seen.add(found)
            w.write(found+astr)

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

from future_builtins import map  # Only on Py2, for more efficient generator based map
from itertools import groupby
from operator import itemgetter

auto = ahocorasick.Automaton()
for i, substr in enumerate(listSubstrings):
    # Store index and substr so we can recover original ordering
    auto.add_word(substr, (i, substr))
auto.make_automaton()

...

for astr in listStrings:
    # Gets all hits, sorting by the index in listSubstrings, so we output hits
    # in the same order we theoretically searched for them
    allfound = sorted(map(itemgetter(1), auto.iter(astr)))
    # Using groupby dedups already sorted inputs cheaply; the map throws away
    # the index since we don't need it
    for found, _ in groupby(map(itemgetter(1), allfound)):
        w.write(found+astr)

Для сравнения производительности я использовал вариант ответа mgc, который, скорее всего, будет содержать совпадения, а также увеличение стога сена. Сначала настройте код:

>>> from random import choice, randint
>>> from string import ascii_uppercase as uppercase
>>> # 5000 haystacks, each 1000-5000 characters long
>>> listStrings = [''.join([choice(uppercase) for i in range(randint(1000, 5000))]) for j in range(5000)]
>>> # ~1000 needles (might be slightly less for dups), each 3-12 characters long
>>> listSubstrings = tuple({''.join([choice(uppercase) for i in range(randint(3, 12))]) for j in range(1000)})
>>> auto = ahocorasick.Automaton()
>>> for needle in listSubstrings:
...     auto.add_word(needle, needle)
...
>>> auto.make_automaton()

А теперь, чтобы проверить его (используя ipython %timeit magic для микробенчмарков):

>>> sum(needle in haystack for haystack in listStrings for needle in listSubstrings)
80279  # Will differ depending on random seed
>>> sum(len(set(map(itemgetter(1), auto.iter(haystack)))) for haystack in listStrings)
80279  # Same behavior after uniquifying results
>>> %timeit -r5 sum(needle in haystack for haystack in listStrings for needle in listSubstrings)
1 loops, best of 5: 9.79 s per loop
>>> %timeit -r5 sum(len(set(map(itemgetter(1), auto.iter(haystack)))) for haystack in listStrings)
1 loops, best of 5: 460 ms per loop

Таким образом, для проверки ~ 1000 маленьких строк в каждой из 5000 строк среднего размера pyahocorasick побеждает индивидуальные тесты членства в ~ 21x раз на моей машине. Он хорошо масштабируется по мере увеличения размера listSubstrings; когда я инициализировал его тем же способом, но с 10 000 маленьких строк вместо 1000, общее требуемое время увеличилось с ~ 460 мс до ~ 852 мс, умножитель времени в 1,85 раза, чтобы выполнить в 10 раз больше логических поисков.

Для записи, время для создания автоматов тривиально в такого рода контексте. Вы платите один раз авансом, а не один раз за стог сена, и тестирование показывает, что ~ 1000-строковому автомату потребовалось ~ 1,4 мс для сборки и заняло ~ 277 КБ памяти (выше самих строк); для строкового автомата ~ 10000 потребовалось ~ 21 мс, и он занял ~ 2,45 МБ памяти.

Ответ 3

Являются ли ваши подстроки одинаковыми? В вашем примере используются 3-буквенные подстроки. В этом случае вы можете создать dict с 3-буквенными подстроками в виде ключей к списку строк:

index = {}
for string in listStrings:
    for i in range(len(string)-2):
        substring = string[i:i+3]
        index_strings = index.get(substring, [])
        index_strings.append(string)
        index[substring] = index_strings

for substring in listSubstrings:
    index_strings = index.get(substring, [])
    for string in index_strings:
        w.write(substring+string)

Ответ 4

Вы можете значительно ускорить внутренний цикл, присоединив listString к одной длинной строке (или прочитайте строки из файла, не разбивая их на разрывы строк).

with open('./testStrings.txt') as f:
    longString = f.read()               # string with seqs separated by \n

with open('./testSubstrings.txt') as f:
    listSubstrings = list(f)

def search(longString, listSubstrings):
    for n, substring in enumerate(listSubstrings):
        offset = longString.find(substring)
        while offset >= 0:
            yield (substring, offset)
            offset = longString.find(substring, offset + 1)

matches = list(search(longString, listSubstrings))

Смещения могут быть сопоставлены beck с индексом строки.

from bisect import bisect_left
breaks = [n for n,c in enumerate(longString) if c=='\n']

for substring, offset in matches:
    stringindex = bisect_left(breaks, offset)

Мой тест показывает скорость 7x против вложенных циклов (11 сек против 77 секунд).

Ответ 5

Вы можете ускорить работу с помощью встроенных функций списка.

for i in listSubstrings:
   w.write(list(map(lambda j: i + j, list(lambda j: i in j,listStrings))))

Из анализа временной сложности времени, кажется, ваш худший случай будет n ^ 2 сравнениями, так как вам нужно пройти через каждый список, учитывая текущую структуру проблем. Еще одна проблема, о которой вам нужно беспокоиться, - это потребление памяти, поскольку с большими масштабами больше памяти обычно является бутылочной шейкой.

Как вы сказали, вы можете индексировать список строк. Есть ли какой-либо шаблон для списка подстрок или списка строк, которые мы можем знать? Например, в вашем примере мы могли бы индексировать, какие строки имеют символы в алфавите { "A": [ "ABC", "BAW", "CMAI" ]...}, и поэтому нам не нужно будет проходить список строк каждый раз для каждого списка элемента подстроки.