Как найти неизвестные повторяющиеся шаблоны в наборе строк?

Question

описание проблемы. Предположим, у вас есть набор строк (до 10 миллиардов строк, каждая строка длиной до 10 тыс. Символов, из которых может быть построено 1000 уникальных символов). Как я могу найти шаблоны длиной от 2 до длины N (скажем, 10 для простоты). Также я хотел бы видеть только те шаблоны, которые встречаются по крайней мере в 1% от всей строки (некоторый порог).

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

Спасибо Индекс

Answer 1

все ваши строки в дерево суффиксов (link). Это может быть O (количество символов), и вам нужно сделать это только один раз, прежде чем вы начнете.

Дерево суффиксов позволяет быстро (O (длина шаблона)) указать, появляется ли шаблон в любой из проиндексированных строк и сколько раз.

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

Теперь 10 миллиардов строк длиной 10k с 2 байтовыми символами (чтобы соответствовать 1000 уникальным символам) довольно велики (18TB, если моя математика правильная), которая не подходит в баране. Таким образом, вам придется либо подождать какое-то время, либо получить больше компьютеров и настроить распределенное решение. Вы можете применить решение выше к партиям строк, чтобы они вписывались в вашу доступную память, но поиск в структуре нужно умножать на количество партий, которые вы делаете.

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