Какой алгоритм поиска подстроки (из множества подстрок) в строке выбрать?

Рейтинг: 2Ответов: 3Опубликовано: 09.04.2015

Есть список подстрок (пусть несколько тысяч). Есть список строк (несколько сот тысяч). Необходимо найти все соответствия подстрокам в первом списке. Решение 'в лоб' не годится, там получается значительное количество итераций, как минимум O(n³):

substring_list = ['one', 'two', ..., 'one thousand']
data_list = ['one spam', 'two ham', ..., 'one billion jam']
out_list = []
for item in data_list:
    for s in substring_list:
       if s in item:
           out_list.append(item)

Какой способ лучший способ, для решения этой задачи?

python алгоритм поиск
Источник: Stack Overflow на русском

Ответы

▲ 4Принят

Насколько я понимаю, вам нужен алгоритм Ахо-Корасик. Он применяется для эффективного поиска набора подстрок.

▲ 2

Можно попробовать воспользоваться алгоритмом Рабина-Карпа поиска подстроки в строке.

Пусть есть подстрока sub длины m и строка s длины n, в которой мы ищем подстроку.

  1. Для начала вычислим хэш от подстроки sub
  2. В строке s для каждой подстроки, длины m, вычислим её хэш. Если хэш этой подстроки и строки sub совпадают, то, потенциально, мы нашли вхождение подстроки sub в строку s.
  3. Проверим, что вхождение действительно имеет место быть, вручную сравнив строку sub и подстроку строки s, с которой совпал хэш.

Аппроксимированно такой поиск будет требовать O(n + m) времени, в худшем случае до O(n*m).

Для того, чтобы быстро пересчитывать хеш в строке s используется кольцевой хэш, который позволяет быстро вычислить значение hash(s[1:m+1]), зная значение hash(s[0:m]). Вычисляется он по следующему принципу:

hash(s[0:m]) = p**(m-1) * ord(s[0]) + 
               p**(m-2) * ord(s[1]) + 
               ... + 
               p * ord(s[m-2]) + 
               ord(s[m-1])

И для того, чтобы получить из этого хэша значение для s[1:m+1], достаточно выполнить следующие действия:

hash(s[1:m+1]) = hash(s[0:m]) * p - p**m * ord(s[0]) + ord(s[m])

что выполняется за константное время.

Требуется только выбрать нужное значение p, рекомендуется обычно взять относительно большое простое число, например, 1000000007. Также стоит заранее посчитать и запомнить степени числа p до p**m.

Так как в этой задаче много подстрок, то если среди них есть строки совпадающей длины, можно воспользоваться уже вычисленными ранее значениями хэшей, т.е. если строка sub1 и строка sub2 имеют одинаковые длины, то для строки sub2 можно будет воспользоваться вычисленными хэшами строки s для sub1.

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

▲ 1

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