Самая распространенная подпоследовательность

Строка имеет подпоследовательностей, но обычно они не все различны. Какова сложность нахождения максимальной частоты любой подпоследовательности? $2^n$

Например, строка «подпоследовательность» содержит 7 копий подпоследовательности «иск», и это максимум.

Пример кода перебора на http://ideone.com/UIp3t

Есть ли связанные структурные теоремы? Оба из них оказываются ложными :

самая длинная из подпоследовательностей максимальной частоты уникальна
максимальная частота любой подпоследовательности длины является унимодальной в $k$ $k$

Возможно связанные ссылки:

Подсчет # различных подпоследовательностей http://11011110.livejournal.com/254164.html $\in \mathbf{P}$
Связанная задача конкурса для нескольких источников http://www.spoj.pl/problems/CSUBSEQS/
Документ по теме http://dx.doi.org/10.1016/j.tcs.2008.08.035

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

ds.algorithms string-search daveagp
источник

Возможно, наивный начальный вопрос: ясно ли, что эта проблема есть даже в NP ? То есть: для задачи определения, существует ли подпоследовательность, по крайней мере, с k вхождениями в строке n- символов, как будет выглядеть сертификат? Например, перечисление всех кортежей индексов, указывающих на экземпляры данной подпоследовательности, не будет иметь полиномиального размера для строки aaa ... aa (которая, хотя и является скучным вводом, тем не менее имеет подстроку с примерно происшествия).

n C (n / 2)

$n \mathbf C (n/2)$

Ниль де Бодрап,

@Niel de Beaudrap: Я думаю, что мы можем посчитать количество вхождений как подпоследовательности за полиномиальное время с помощью динамического программирования, что позволяет использовать саму подпоследовательность в качестве сертификата.

Цуёси Ито

Я немного сбит с толку: вопрос "задана ли строка s, найти подпоследовательность, которая встречается максимальное количество раз?"

Суреш Венкат

@SureshVenkat: Да, это мое понимание. Например, если в качестве входных данных указать последовательность из X, правильным ответом будет последовательность из X.

n

$n$

n / 2

$n/2$

Джефф

@ marzio-de-biasi: вопрос, на который вы ссылаетесь, отличается (и гораздо проще): там вам дается последовательность.

Дэвид

Ответы:

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

Идентификация наиболее
частых подпоследовательностей Окончательный отчет проекта CSE 549 по вычислительной биологии
Михаил Баутин 2006

(хотя существуют некоторые стандартные проблемы подпоследовательностей, которые в некоторой степени похожи и изучены, например, в статье Elzinga et al., возможно ли, что эта конкретная проблема подпоследовательности не была слишком изучена?)

ВЗН
источник

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

Дэвид Эппштейн

fyi / addendum Баутин также говорит, что в конце статьи он имеет 5K строк кода C ++ и Python по этой проблеме / статье для всех, кто заинтересован

vzn

@ Дэвид, я не думаю, что отрицательное голосование связано с тем, что этот документ связан, скорее всего, это связано с тем, что этот ответ выглядит (по сути) как однострочный ответ (без объяснения того, как статья связана с вопросом. и отвечает на него). Это могло бы быть более подходящим в качестве комментария.

Каве

Хорошо, тогда, изложено: статья, кажется, показывает (если кто-то не может найти лучшего реферата или придумать доказательство этой трудной проблемы самостоятельно), что точная сложность проблемы до сих пор неизвестна / открыта (кроме очевидной PSpace / ExpTime) и может содержать лучшие из известных на данный момент анализов / подходов к их решению

vzn

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

daveagp

Не ответ, просто лемма.

Поэтому, прежде всего, можно задаться вопросом, какова самая распространенная подпоследовательность строк типа 12..t12..t12..t .. Подумав немного, понимаешь, что он также должен иметь форму 12..t12..t12 .., явно короче. Если исходная строка имеет длину nt, а подпоследовательность этой специальной формы имеет длину k, то число ее вхождений точно равно . Это означает, что наиболее распространенная подпоследовательность также заканчивается на (т. должно делиться на ). Но где это взять максимум и сколько это стоит ??? Довольно неловко, но я не мог этого понять ... ${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$ $t$ $k$ $t$

domotorp
источник