Существует ли быстрый алгоритм поиска общих подстрок во множестве больших строк?

Есть много строк большой (неограниченной) длины. Необходимо найти в них общие подстроки длины больше N. Существует ли готовый быстрый алгоритм для этого? Или только эвристические алгоритмы и только переборы? Что, как я вижу, нереализуемо?

На практике задача выглядит примерно так. Есть множество строк байтов разной длины, от 0 и до бесконечности, 75 процентов строк средней длины 1 гигабайт. Самая длинная строка - 150 гигабайт, самая короткая - 2 килобайта. Необходимо найти общие подстроки длины больше N, то есть, указать, что, например, строки с номерами x1, x2, x3, x4, ..., x153, имеют общую подстроку длины N+1234, начинающуюся в каждой строке с номера y1, y2, ... и т.д. На текущий момент есть 70 терабайт строк, они находятся на двенадцати компьютерах с 8 Гб RAM и процессорами i3 на 4 ядра. На каждом компьютере стоит три диска - системный на 2 Тб, и с данными - 2 hdd на 8 терабайт. Сеть 1 ГБит.

Писать думаю на C++. После того, как определюсь с концепцией - какие то куски буду переписывать на ассемблере.

Возможно ли это в принципе за разумное время сделать?
  • Вопрос задан
  • 521 просмотр
Решения вопроса 1
wataru
@wataru Куратор тега C++
Разработчик на С++, экс-олимпиадник.
Пока главная проблема, что надо сравнивать все строки со всеми. Если бы их поделить на какие-то части, когда сравнивается не так много строк, пусть даже этих частей много, то задача решается Гораздо проще.

Один вариант относительно быстрого поиска одинаковых подстрок - это суффиксные деревья. Придется много поломать голову, как хранить эффективно 256 ссылок на детей так, чтобы дерево не занимало в тысячи раз больше чем вохдная строка, но это возможно. Например, хранить отсортированный список исходящих символов в каждой вершине.

Вот построили вы деревья для всех строк, дальше надо их попарно сравнить простым рекурсивным обходом. Если оба дерева содержат переход по какому-то символу, рукурсивно идите по нему. Если дошли до глубины N - вы нашли совпадение. Можно вообще идти пока не обломитесь и взять максимальную глубину. Такой обход обойдет дерево один раз для каждой пары строк. Да, еще надо будет хорошенько потрахаться с хранением дерева на диске и подгрузкой его кусками, ибо в оперативку оно все не поместится никак.

Второй вариант, возможно более подходящий для таких объемов данных - это полиномиальные хеши. Можно для каждой строки вычислить L-N+1 хешей для всех подстрок длины N. Первый хеш считается тупо по формуле, а дальше дописывание одного символа справа и удаление одного символа слева можно за 2 операции пересчитать. Вот так вы быстро, за линейное время, можете построить все хеши для одной строки. Запишите их в файл, отсортируйте его (гуглите - известная задача сортировки очень большого файла). А потом операцией слияния можно найти повторяющиеся числа во всех файлах.

Более того, можно не сравнивать каждый файл с каждым, а выполнять слияние сразу на всех файлах. Для этого надо завести приоритетную очередь, она же куча, она же heap, в которую складывать текущие числа из всех файлов (по одному из файла) вместе с указателем на сам файл. Вам надо из этой очереди вынуть минимальное число, и потом вынимать дальше, пока минимум в очереди не изменился. Т.е. вынуть все одинаковые минимальные числа. Файлы, на которые они указывают - это строки с совпадениями. Пометьте это где-то, и для каждого файла прочитайте следующее число и положите его в очередь.

Ну, еще надо будет проверить, а не коллизия ли совпадение хеша и действительно сравнить строки. Поэтому вместе с хешами надо будет еще хранить позиции, где они были насчитаны. Тут же можно будет и расширить совпадение, если оно оказалось длиннее N.

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

Если все-таки надо искать совпадения по всем строкам глобально, то придется помучиться. Разбейте ваши данные на K частей примерно одинакового размера так, что каждый компьютер может обработать по 2 части, а хранить хотя бы по 3 части.

В идеале у вас должно быть еще и K/2 компьютеров, иначе схема усложняется.

Надо будет провести K-1 раундов. На первом раунде части 1 и 2 лежат на компьютере 1, части 3 и 4 на втором, и т.д. На втором раунде вы храните части 2 и 3 на компе 1, 4 и 5 на компе 2 ... K и 1 на последнем. При переходе между раундами каждый комп отдает одну часть куда-то, и одну откуда-то получает. На третьем и четвертом раунде вы обрабатываете все пары, в которых вторая часть имеет номер на 2 больше первой части (если брать по модулю K). И так далее. На последнем раунде будут обрабатываться пары, где одно число больше другого на (K-1)/2.

Например, для K=4 вы получаете такие пары на компах:
1. (1,2) (3,4)
2. (2,3) (4,1)
3. (1 3) (2 4)


Тут надо порисовать и составить схему так, чтобы поменьше данных перекладывалось. Для некоторых K так красиво не получится, и какие-то компы будут простаивать на каких-то раундах.

По поводу оптимизаций - узкое место будет загрузка данных с диска и передача их по сети. Ассемблером баловаться тут смысла нет особо. Запускайте кучу потоков, чтобы диск не простаивал. Еще репликацию данных можно запускать параллельно с обработкой предыдущего куска, если места хватает.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 2
begemot_sun
@begemot_sun
Программист в душе.
В grep реализовн умный алгоритм поиска вхождения подстроки в строку. А именно берется фрагмент строки по длине равный подстроке и сравнивается последний символ. Если символ совпадает с подстрокой, то сравнивается предпоследний, и т.д. если на каком-то этапе символы разные -- то сразу указатель текущей работы перемещается на + длина_искомой_подстроки .. т.о. можно увеличить производительность в N-раз.

https://www.gnu.org/software/grep/manual/grep.html... -- там в конце есть список алгоритмов, может поможет.
Ответ написан
Комментировать
Gremlin92
@Gremlin92
Целеустремленный
Думаю надо начать с strstr
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы