Модификация Алгоритма Рабина-Карпа для поиска общих подстрок

Вот и подошел к концу период отправки решений на конкурс Accelerate Your Code 2012 и мы наконец-то можем поделиться своими идеями, использованными в решении задачи и пригласить остальных участников к обсужднию.

Задача состояла в том, чтобы найти общие подстроки длины не менее N из заданной ref строки (представляющей собой участок ДНК и потом состоящей только из символов A, G, C, T) и некоторого набора in строк (найти нужно именно подстроки, не подпоследовательности, то есть связные общие части). Мы не сразу поняли одну особенность этого конкурса: здесь фактически нужно было не написать программу, полностью соответствующую описанию, а скорее оптимизировать прилагающееся референсное решение, так как сама постановка была нечеткой, а на форуме мы получили ответ, что программа должна дать абсолютно такой же результат как и референсный код. Ну что же, задание необычное, но тем более интересное.

Для начала проанализируем референсное решение. В исходном алгоритме для каждой in-строки динамически строится матрица L[i][j] - максимальная длина общей подстроки в ref и in строках, с позициями конца подстроки i и j соответственно. После построения этой матрицы достаточно найти все элементы со значением не менее N. Также в референсном решении отсекаются случаи, когда можно сдвинуть правый конец одной или обоих подстрок на 1 вправо с неуменьшением длины общей подстроки.

Главная проблема исходного решения в том, что сложность и требование к памяти в этом решении – квадратичные. Это значит, что если входные данные будут иметь максимальный размер (по четыре миллиарда символов), то время исполнения будет исчисляться годами, не говоря уже про потребляемую память, поэтому в первую очередь мы стали искать более эффективный алгоритм. Существует Алгоритм Рабина - Карпа поиска подстроки в строке, вкратце его суть в том, что имея длинную строку и образец длины m, мы находим хеш подстроки и хеши всех подстрок длины m в большой строке. При аккуратном использовании хеш-функции (нужно считать новый хеш, исходя из старого за О(1), а не за O(m) )

h -= rem * int64(s[i-1]);

h = h * MOD + int64(s[i+minMatchLength-1]);

hash[i] = h;


мы потратим в среднем О(m+n) времени, просто сравнивая все хеши с хешем образца. Недостатком этого алгоритма является то, что в «плохих» случаях он может работать за квадратичное время, однако на форуме мы получили ответ, что плохих случаев в тестах не будет, что повлияло на выбор этого алгоритма.

Для данной конкретной задачи, конечно, пришлось делать модификации. Мы можем найти все хеши подстрок длины N из in строки и поместить их в хеш-таблицу, этот процесс можно распараллелить через библиотеку TBB. Далее мы можем пройтись по подстрокам длины N из ref строки и сверять их хеш с таблицей. При этом вставка в хеш-таблицу медленнее, чем проверка, поэтому заметим, что задача практически симметрична относительно ref и in строк, поэтому если ref строка длиннее, то создадим хеш таблицу для in строки и наоборот. Когда мы находим совпадение хешей, то находим наибольшую общую подстроку (зная начальные индексы) и запоминаем этот ответ. Есть еще небольшая сложность связанная с тем, что ответы получатся не в том порядке в котором они идут в референсном решении, поэтому придется еще применить сортировку для ответа, однако это не должно сильно замедлить алгоритм.

В итоге получается, что сложность этого алгоритма составляет O(N + KlogK), где N – суммарный размер входа, K – размер выхода, что уже является практически линейным решением.

Хотелось бы услышать комментарии, замечания или вопросы и от остальных участников и конечно, делитесь вашими идеями!
For more complete information about compiler optimizations, see our Optimization Notice.
Categories: