Дерево суффиксов против массива суффиксов для LCS

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

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


c++ algorithm suffix-tree suffix-array
person zeus_masta_funk    schedule 05.01.2014    source источник
comment
Так какова конечная цель? Как найти пару, имеющую самую длинную общую подстроку? (т.е. найти две наиболее похожие строки в смысле общей подстроки)   -  person leemes    schedule 05.01.2014
comment
Замечу, что задача LCS для нескольких строк значительно сложнее, чем для двух строк. В первом предложении основного раздела сложности на странице en.wikipedia.org/wiki/Longest_common_subsequence_problem говорится, что это NP-сложно. Первая реализация, которую я смог найти, search.cpan .org/~vmoiseev/Algorithm-MLCS-1.0/lib/Algorithm/ — это эвристическая реализация, которая не гарантирует нахождения абсолютно наилучшего решения.   -  person mcdowella    schedule 05.01.2014
comment
Упс, игнорируйте последний комментарий. Я перепутал самую длинную общую подпоследовательность и самую длинную общую подстроку - извините.   -  person mcdowella    schedule 05.01.2014
comment
@leemes Цель состоит в том, чтобы найти точную общую подстроку между несколькими цепочками ДНК. Я не уверен точно, сколько подстрок будет, пока я не верну свои результаты, но я предполагаю, что всего 4 и целых 7 или 8 (вероятно, ближе к нижнему пределу).   -  person zeus_masta_funk    schedule 05.01.2014

Ответы (1)


arrow_upward
1
arrow_downward

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

Теперь вам нужно найти длину общего префикса, разделяемого всеми подстроками, начиная с указателей в окне. Это должно быть минимальное значение LCP между указателями в окне. Если вы используете красно-черное дерево, такое как набор деревьев Java, с ключом, который состоит из значения LCP в качестве наиболее важного компонента и некоторого прерывателя связи, такого как сам указатель, в качестве менее значимого компонента, тогда вы можете поддерживать минимальный Значение LCP в пределах окна примерно равно логарифмическому размеру окна на настройку окна.

person mcdowella    schedule 05.01.2014
comment
Когда вы найдете несколько подстрок в своем окне, как вы можете быть уверены, что каждая из них находится в другой исходной строке? Это могут быть повторения определенной подстроки в одной и той же исходной строке, не так ли? - person jogojapan; 05.01.2014
comment
Я предполагаю, что есть какой-то маркер с указателями. Например, если вы создаете массив суффиксов, объединяя все входные строки, вы можете отслеживать, какие диапазоны индексов соответствуют какой входной строке, а затем определять по индексу, с которого начинается подстрока, из какой входной строки она взята. В начале и каждый раз, когда вы перемещаете положение заднего окна вперед, вы можете использовать эти проверки, чтобы убедиться, что положение переднего окна достаточно далеко вперед, чтобы оно включало хотя бы один указатель из каждой входной строки. - person mcdowella; 05.01.2014
comment
Да, но в таком случае как определить размер окна? Он больше не ограничен количеством исходных строк. - person jogojapan; 05.01.2014
comment
По мере того, как заднее положение окна перемещается, его переднее положение должно смещаться ровно настолько, чтобы оно содержало по одной входной строке каждого типа. Для некоторых вариантов входных данных — например, если ответом является пустая строка — окно будет состоять почти из всего массива суффиксов, но стоимость обновления структур данных, необходимых для определения того, где заканчивается окно и каково минимальное значение LCP еще управляемо - про лог размера окна. - person mcdowella; 05.01.2014
comment
В порядке. Я просто думаю, что важно знать, что это красно-черное дерево в некоторых случаях вырастает очень большим. - person jogojapan; 06.01.2014