1

Есть список подстрок (пусть несколько тысяч). Есть список строк (несколько сот тысяч). Необходимо найти все соответствия подстрокам в первом списке. Решение 'в лоб' не годится, там получается значительное количество итераций, как минимум 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)

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

13
  • Недостаточно информации в плане условий для сравнения. Учитываются ошибки, опечатки или теоретически все верно, просто надо сравнить ? Если просто сравнить, то выбирай ответ про Рабина-Карпа, он будет идеален, лишь добавлю что кэш слов, лучше добавить куданить в таблицу и к ней запрос на условие in по кэшу, при этом закэшировав искомые строки. Тогда будет намного быстрее и без итераций :) А если поиск с учетом ошибок, то перебор прийдется делать и кэш не поможет. 9 апр 2015 в 8:53
  • @IvanZakirov: Рабин-Карп не умеет искать несколько подстрок одновременно => общее время пробега пропорционально размеру списка подстрок, т. к. приходится искать одну за одной.
    – VladD
    9 апр 2015 в 9:14
  • @IvanZakirov: Будем считать,что ошибки не учитываются, нужно просто сравнить, входит ли substring в string или нет.
    – to_night
    9 апр 2015 в 9:54
  • @VladD я же написал что по Карпу, но дополнительно засунуть в базу и запрос сделать IN, что ускорит и уберет итерации. А вообще можно и без КЭША, просто засунуть в базу и like '%...%' А вот Aho–Corasick метод.. ну я думаю он больше подходит для языков как Prolog и составления семантических сетей, нежели Python. Так что перебор ))) 9 апр 2015 в 10:29
  • 2
    А поиск при помощи питона - обязательное условие? Может быть имеет смысл воспользоваться стандартными средствами linux? Недавно вопрос был (сейчас не помню какой именно) - там тоже надо было искать строки по большому набору данных. Вроде как даже тов. @VladD советовал grep -F (или fgrep). Т.е. можно сначала получить все совпадения через grep, а потом уже обрабатывать их как вам надо
    – BOPOH
    9 апр 2015 в 19:26

3 ответа 3

4

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

2
  • 1
    Если входные данные на диске лежат, то grep -F -f substring_list data_list можно использовать (алгоритм тот же).
    – jfs
    9 апр 2015 в 19:28
  • @jfs, судя по "Я пишу утилиту для разбора логов" они там и лежат.
    – BOPOH
    9 апр 2015 в 19:31
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 значение хэша совпало.

2
  • @Timoey Bondarev Насколько реализация этого алгоритма именно на Python будет быстрее, чем простой перебор?
    – to_night
    9 апр 2015 в 13:51
  • @to_night На большом наборе строк должно быть достаточно заметное ускорение работы, но оно может зависеть также от способа реализации самого алгоритма и применяемых оптимизаций. Ожидаемое количество коллизий в среднем не так велико, чтобы сильно замедлить работу. Сам я, к сожалению, не сравнивал скорости работ этих подходов, чтобы ответить более обоснованно. 9 апр 2015 в 14:02
1

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

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.