Как рассчитать количество самых длинных общих подпоследовательностей

Question

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

например. Строка X = "efgefg"; Строка Y = "efegf";

вывод: Количество самых длинных общих последовательностей: 3 (т. е. efeg, efef, efgf - это не нужно вычислять по алгоритму, показанному здесь только для демонстрации)

Мне удалось сделать это в O (| X | * | Y |), используя динамическое программирование, основанное на общей идее: Алгоритм самого дешевого пути .

Кто-нибудь может придумать, как сделать этот расчет с лучшим временем выполнения?

- Отредактировано в ответ на комментарий Джейсона.

Answer 1

Самая длинная общая проблема подпоследовательности - хорошо изученная проблема CS.

Вы можете прочитать об этом здесь: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Answer 2

Лучшее объяснение (с кодом), которое я нашел:

Считать все LCS

Answer 3

Прежде всего, мы знаем, что нахождение любой самой длинной общей подпоследовательности из двух последовательностей с длиной n не может быть выполнено за время O (n ^2-ε ), если гипотеза сильного экспоненциального времени не удалась, см .: https://arxiv.org/abs/1412.0348

Это в значительной степени означает, что вы не можете подсчитать количество способов, как выровнять общие подпоследовательности для входных последовательностей за O (n ^2-ε ) времени. С другой стороны, можно подсчитать количество способов таких выравниваний за O (n ² ) времени. Также возможно сосчитать их за O (n ² / log (n)) с так называемым ускорением четырех русских.

Теперь реальный вопрос, действительно ли вы намеревались рассчитать это или вы хотите найти число различных подпоследовательностей? Я боюсь, что этот последний является # P-полной проблемой подсчета. По крайней мере, мы знаем, что подсчет количества последовательностей заданной длины, которые может сгенерировать регулярная грамматика, # P-complete:

S. Kannan, Z. Sweedyk и S.R. Mahaney. подсчет и случайная генерация строк на обычных языках. В симпозиуме ACM-SIAM по дискретным алгоритмам (SODA), стр. 551–557, 1995

Это аналогичная проблема в том смысле, что подсчет количества способов регулярной грамматики может генерировать последовательности заданной длины - это тривиальный алгоритм динамического программирования. Однако, если вы не хотите различать поколения, имеющие одинаковую последовательность, проблема превращается из простой в чрезвычайно сложную. Моя естественная гипотеза состоит в том, что это должно иметь место и для проблем с выравниванием последовательности (самая длинная общая подпоследовательность, расстояние редактирования, самая короткая общая суперструна и т.

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

Answer 4

Не знаю, но вот несколько попыток мыслить вслух:

Наихудший случай, который я смог построить, имеет экспоненту - 2 ** (0,5 | X |) - количество самых длинных общих подпоследовательностей:

X = "aAbBcCdD..."
Y = "AaBbCcDd..."

, где самые длинные общие подпоследовательности включают в себя ровно одну из {A, a}, ровно одну из {B, b} и т. Д. 2 ** 128 уже огромный.)

Однако вам не обязательно генерировать все подпоследовательности для их подсчета. Если у вас есть O (| X | * | Y |), вы уже лучше этого! Из этого мы узнаем, что любой алгоритм лучше вашего не должен пытаться генерировать фактические подпоследовательности .