Быстрая строка в списке поиска

Question

Используя Python 3, у меня есть список, содержащий более 100 000 строк (list1), каждая длиной не более 300 символов. У меня также есть список из более 9 миллионов подстрок (list2) - я хочу подсчитать, сколько элементов содержится в подстроке в list2. Например,

list1 = ['cat', 'caa', 'doa', 'oat']
list2 = ['at', 'ca', 'do']

Я хочу, чтобы функция возвращала (отображается на list2):

[2, 2, 1]

Обычно это очень просто и требует очень мало. Однако из-за огромного размера списков у меня есть проблемы с эффективностью. Я хочу найти самый быстрый способ вернуть этот список счетчиков.

Я пробовал составления списков, генераторы, карты, циклы всех видов, и мне еще предстоит найти быстрый способ выполнить эту простую задачу. Каков теоретически самый быстрый способ достижения этой цели, желательно очень быстро сделать O(len(list2)) шагов?

Answer 1

set M = len(list1) и N = len(list2)

Для каждой из N записей в list2 вам нужно будет выполнить M сравнений с записями в list1.Это худшее время выполнения O(M x N).Если продолжить, давайте возьмем каждую запись в list2 длиной 1 и каждую запись в list1 длиной 300, тогда вы получите время выполнения O(300M x N).

Еслипроизводительность действительно проблема, попробуйте динамическое программирование.Вот начало:

1) сортировка list2 в порядке возрастания длины, например, так:

['scorch', 'scorching', 'dump', 'dumpster', 'dumpsters']

2) сортировка их в подсписки, так что каждая предшествующая запись является подмножествомследующая запись:

[['scorch', 'scorching'] , ['dump', 'dumpster', 'dumpsters']]

3) Теперь, если вы сравните с list1, а 'scorch' там нет, то вам не нужно искать 'scorching'.Точно так же, если 'dump' там нет, также нет 'dumpster' или 'dumpsters'

, обратите внимание, что наихудшее время выполнения все равно

Answer 2

Я считаю, что эта задача может быть решена за линейное время с помощью машины Aho Corasick, сопоставляющей строку . См. этот ответ для получения дополнительной информации (возможно, вы также получаете идеи из других ответов на этот вопрос - это почти та же задача, и я думаю, что Aho Corasick - теоретически самый быстрый способ решить это).

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

Answer 3

Не уверен, как можно избежать использования алгоритма O (n ** 2).Вот простая реализация.

>>> def some_sort_of_count(list1, list2):
>>>     return [sum(x in y for y in list1) for x in list2]
>>> 
>>> list1 = ['cat', 'caa', 'doa', 'oat']
>>> list2 = ['at', 'ca', 'do']
>>> some_sort_of_count(list1, list2)
[2, 2, 1]