Алгоритм параллельного поиска максимальных, общих подстрок в двух строках, и его имплементация на C++ (C++11)

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

  1. Поделиться со всеми интересным алгоритмом и его реализацией на С++ (стандарт С++11);
  2. Узнать, есть ли у данного алгоритма название и/или формальное описание;


Предыстория


Все началось с конкурса, проводимого Intel, о котором я узнал из поста. Суть конкурса сводилась к разработке и реализации алгоритма, решающего задачу нахождения в двух строках максимально длинной общей подстроки (переписывать полностью задачу сюда, думаю, не имеет смысла). К той задачке прилагался референсный код, т.е. решение на которое надо было «равняться». Чуть позже, из форума, посвященному этому конкурсу, стало понятно, что референсный код не решает эту задачу в том виде в котором она сформулирована на сайте Intel. Т.е. весь смысл конкурса сводился к следующему: «сделать программу, которая в точности повторяет вывод референсного кода, при одинаковых входных параметрах, только чтобы она была быстрее и параллельнее».
Ну да ладно, даже несмотря на абсурдность ситуации с описанием задачи, участие в конкурсе я сразу отбросил еще и потому что там могли участвовать только студенты и выпускники. Мне понравилась сама задача, та что описана на сайте.

Постановка задачи


Вот как я понял из описания эту задачу:
Есть две строки S1 и S2, нужно найти максимально длинную общую подстроку(и) (далее будем называть искомые подстроки — подмножествами), длина которой не меньше M. В качестве результата вывести ее координаты.
Координатами являются четыре целых числа.
Первые два относятся к строке S1 — это номера позиций первого и последнего символов найденной подстроки.
Вторые два числа имеют тоже значение, только относятся ко второй строке — S2.

Например, если мы имеем следующие входные параметры:

S1 = ABCCA
S2 = ACCABABCCBAABCBAABCBACBACBACBAC
M = 2

то ответом будет:
0 3 5 8

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

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

Срезюмируем то что нам дается на вход:
  1. S1, S2 — две строки, в которых необходимо произвести поиск;
  2. M — минимально возможная длина искомой подстроки;
  3. K — число потоков которое можно использовать для распаралеливания;


Алгоритм


По сути, идея решения очень проста и состоит из 3-х шагов:
  1. Разбить S1 на минимально-возможные (длиной M) сегменты.
  2. Спроецировать сегменты на S2.
  3. На полученной проекции, найти максимально длинные подмножества (состоящие из максимального количества подряд идущих сегментов).

Рассмотрим работу алгоритма на следующем примере:

S1 = ABCCA
S2 = ACCABABCCBAABCBAABCBACBACBACBAC
M = 2
K = 2

1) Разбиваем S1 на сегменты, каждый длиной M = 2:
AB, BC, CC, CA

2) Проецируем каждый полученный сегмент на S2:

image

или в виде смещений:

image

таким образом мы получили проекцию S1 на S2:

image

дальше будем называть эту проекцию — картой пересечений.

По сути, карта пересечений представляет из себя матрицу координат всех сегментов длина которых равна M. Т.е. каждый элемент матрицы характеризует координату в строке S2, в то время как номер строки матрицы характеризует координату в строке S1. Имея в распоряжении карту пересечений, мы можем найти все пересечения (подмножества) и выбрать из них максимальные.

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

image

если брать во внимание что каждый сегмент может служить началом подмножества, то используя карту пересечений, можно вычислить длину всех подмножеств, началом которых, являются сегменты составляющие эту проекцию.
Следующая иллюстрация демонстрирует, как производится вычисление длины подмножества, началом которого служит сегмент с координатой 5:

image

т.е. подмножество начинающееся с координаты 5 имеет максимальную длину — len = 4, для подмножества начинающегося с координаты 3 длина будет равна 2 и т.д.

Аналогичным образом, пробегая по каждому сегменту в карте пересечений, мы находим, что максимально длинным подмножеством является подмножество длиной 4 с координатами в S1 и S2 строках: 0 и 5 соответственно.

Распараллеливание


Как можно было заметить каждый шаг в решении этой задачи (шаги 1, 2, 3) легко распараллеливается, возможно применение Map-Reduce.

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

image

3.1) Каждому потоку назначается свой порядковый номер (n). Далее n-ый поток, начиная c n-ой позиции, обрабатывает каждый K-ый элемент карты пересечений. Таким образом мы разбиваем карту пересечений на несколько (число потоков) частей. Из этих частей, выбирают, вышеописанным образом, максимальные подмножества:

image

3.2) После того как все потоки отработают, мы получим несколько групп подмножеств. Из полученных групп выбираем группы с максимальной длиной сегментов. В нашем примере это две группы: группа образованная потоком #1, содержащая в себе сегменты длиной 3 символа (с начальными координатами: 0; 11 и 1; 6), а также группа образованная потоком #2, содержащая в себе один сегмент длиной 4 символа (с координатами 0; 5). Поскольку вторая группа имеет наибольшую длину сегментов, то первую группу отбрасываем сразу.
В результате мы получили начальные координаты подмножества (0; 5) и его длину — 4. Для нахождения конечных координат применяем формулу: end_coord = start_coord + len — 1.

Таким образом получаем ответ: 0 3 5 8.

Заключение


Я решил не затрагивать рассмотрение деталей реализации, данного алгоритма на С++, так как это уже выходит за рамки данной статьи. Ознакомится с реализацией данного алгоритма на С++ (С++11) можно здесь, для компиляции при помощи GCC не забываем ставить флаги -pthread и -std=с++0X.

Вопрос


Этот алгоритм пришел мне в голову как очевидное решение задачи, но я не знаю, есть ли у него официальное название и/или формальное описание?
Поделиться публикацией

Комментарии 26

    +2
    Интересно, сам не участвовал в этом конкурсе, но по причине, что мне не понравилось условие задачи ( сделать то, что делает код жури. ИМХО это скучно и не интересно ).

    Так же, если я правильно понял, то вы неверно поняли условие. Так как авторское решение ищет именно такие позиции, которые нельзя как-то сдвинуть вправо, что ещё больше теряет для меня интерес к задаче.

    В вашем условии всё гораздо приятнее, и тут можно придумать множество решений. Например те же хэши, или даже распаралелленное суффиксное дерево.

    И да, важный факт тут, использовать число M, потому как некоторые участники тупо на него забивали, а ведь если это число большое, решение, эффективно использующее M, будет работать куда шустрее.

    У вас интересное решение, и оно как раз тоже использует M, что хорошо.

    Могу ли я вас попросить в конце добавить оценку сложности времени выполнения и потребления памяти для вашего решения, так будет видно ещё больше насколько оно хорошее или плохое в отношении к другим решениям. Спасибо :)
      +1
      Код жюри задачу не решает. При вполне практических по размерах входных строках он работает года (лучшие решения — меньше минуты).
        +1
        Не знаю к какой строчке вы это написали, но я знаю, что код жюри не решает задачу.
        0
        И да, важный факт тут, использовать число M, потому как некоторые участники тупо на него забивали, а ведь если это число большое, решение, эффективно использующее M, будет работать куда шустрее.

        Кстати, заметил что скорость референсного кода, практичеки, не зависит от M, конечно я понимаю что сравнивать референсный код с реализацией этого алгоритма — не корректно, но всеже это удивило)

        Могу ли я вас попросить в конце добавить оценку сложности времени выполнения и потребления памяти для вашего решения, так будет видно ещё больше насколько оно хорошее или плохое в отношении к другим решениям. Спасибо :)

        Если допустить, что M — константа (хотя от этого параметра сильно зависит скорость), то, если я не ошибаюсь, суммарная сложность будет:
        O((N1 — M + 1) * N2) + O step3 = O(N1 * N2) + O step3, где N1, N2 — длина первой и второй строк соответственно; O step3 — сложность шага 3.
        Пока что не могу точно сказать какова сложность шага 3, так как тут идет не совсем прямая зависимость от N1, N2.
        +5
        implementation → реализация ;-)
          0
          Спасибо, за заметку, поправил в теле поста)
          Также благодарю Lockal, за то что указал на ошибки пунктуации.
          +3
          Скажите, Вы разве ушли куда-то от квадратичной сложности? Основной поток решений задачи на форуме конкурса был на суффиксных структурах данных (дерево, автомат, массив), дающих логарифмическую сложность.
            0
            Если очень захотеть, то линейную. Хотя, к примеру, мои линейные наброски с суффиксным автоматом едва ли можно было как-то осмысленно распараллелить иначе чем в обработке всех тестов из входных данных. Интересно, как это у других участников.
              0
              Да, конечно, линейную. Что-то я торможу.
              0
              Скажите, Вы разве ушли куда-то от квадратичной сложности?

              Нет конечно, не ушел)
              Основной целью было разработать и реализовать алгоритм, который хорошо параллелится. Как я и написал в «Заключении» — алгоритм пришел мне на ум почти сразу же после прочтения условия задачи, конечно это были только наброски, без деталей. После этого удалось более детализировать и более выгодным образом его распараллелить.
                0
                Алгоритмы на суффиксных структурах тоже отлично параллелятся. (Это не в укор Вашему решению, а просто мысли вслух).
              +1
              Плюсанул, бо код очень нравится, так сказать, максимум "++11"
                0
                мне алгоритм понравился, но я наверно бы решал «в лоб»:
                1) взял бы строку и разбил бы её на n-частей (по потоку на каждую часть)
                тут есть маленькая тонкость — части должны перекрываться как минимум на кол-во символов в сегменте подстроки (2-3 символа).
                2) каждую часть начал бы параллельно проверять на вхождение первого сегмента.
                3) если бы первый сегмент вошел — то запустил новый поток на проверку всей подстроки или следующего сегмента.
                  +2
                  Поздравляю, вы практически изобрели BLAST алгоритм :)

                  Очень активно применяется в генетике для анализа последовательностей.

                  en.wikipedia.org/wiki/BLAST
                    0
                    Спасибо за инфу!
                    Значит можно считать что статья выполнила все поставленные цели.
                    Надо будет почитать про BLAST.
                    0
                    А можете подсказать какой-нибудь классический алгоритм поиска в первой строке максимальной подстроки, которая соответствует началу второй строки? Т.е. у нас есть строки S1 и S2, и надо в S1 найти максимальную подстроку, которая является началом S2.
                      +1
                      FASTA вам поможет en.wikipedia.org/wiki/FASTA, это классика.

                      Для своей задачи можете просто ввести туда ограничения.
                        0
                        Спасибо, буду изучать.
                        +1
                        Ночью туго соображаю, но почему-то кажется, что можно чуть-чуть подправить классический алгоритм Кнута-Морриса-Пратта, что работает за O(|S1|+|S2|). Собственно, алгоритм ищет префиксы строки S2 в строке S1, заканчивая работу, когда/если префикс достигает длины S2, — вам же нужно запомнить самый длинный совпавший префикс, то бишь изменить один if.
                          0
                          Это выглядит более классическим и пригодным. Спасибо. :)
                        +1
                        Можно искать проекции хешированием. Поскольку у нас фиксированная длинна M, можно преподсчитать все хеши подстрок S2 длины M, а потом при проверке высчитать хеш нужной для проекции строки и сразу узнать позиции. Итого — O(|S2|) на препроцесс и O(M+log|S2|)
                          0
                          Возникала подобная мысль, только я хотел использовать хеш-таблицу или что-нибудь подобное для кеширования уже найденных проекций сегментов. Но идею отложил в сторону, так как, пока что не нашел метода, как параллельно, без блокировок, строить кеш.
                          Если конечно Ваше решение как-нибудь возможно распараллелить, то будет отлично, в противном же случае у нас появится последовательный участок, который, несмотря на то что в последовательном режиме может дать большой прирост всему алгоритму, в параллельном думаю может снизить эффективность (закон Амдаля).
                            0
                            Вы сами строите хеш-функцию.
                            Скажем F(pos) = Spos * p0 + Spos+1 * p1 +… + Spos+M-1 * pM-1
                            для pos = 0..|S|-M
                            p — простое число. желательно первое после количества букв в алфавите, тоесть 29 или 31. Функцию можно взять по модулю большого числа. Преподсчитываем за линию еще до вычислений для обоих строк.

                            Теперь, когда мы берем подстроку строки S2 — это преподсчитанное значение нашей функции. O(1). Нужно определить, в каких позициях это число находится в строке S. Это тривиально, так как работаем мы уже с числами, а не со строками.
                            0
                            > Поскольку у нас фиксированная длинна M
                            В условии дана минимальная длина ответа M. То бишь она не фиксирована, а подстрок и их хешей все еще порядка квадрата длины строки.
                              0
                              нет, нам нужны частичные суммы хешей. К примеру, если нужно узнать сумму на подотрезке, Вы делаете массив частичных сумм и тогда за О(1) узнаете ответ, неважно какой длины запрашивается отрезок.
                              Так же и здесь — сделать массив частичных сумм хешей и для любого M конкретный хеш извлекается за O(1)
                            +1
                            Хотел поучавствовать в конкурсе, даже реализовал прототип, который использовал 2 алгоритма — суффиксный массив и еще один простой квадратичный алгоритм, но который использовал SSE4.2. План был в зависимости от входных параметров выбирать алгоритм. Но время защиты диплома подкралось незаметно и я так и не доделал программу.

                            В статье описан интересный алгоритм. Возможно, для некоторых входных параметров он может быть оптимальнее других.

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое