Subsecuencia más común

Una cadena tiene $2^n$ subsecuencias, pero generalmente no son todas distintas. ¿Cuál es la complejidad de encontrar la frecuencia máxima de cualquier subsecuencia?

Por ejemplo, la cadena "subsecuencia" contiene 7 copias de la subsecuencia "demandar" y este es el máximo.

Ejemplo de código de fuerza bruta en http://ideone.com/UIp3t

¿Hay teoremas estructurales relacionados? Ambas resultan ser falsas :

la más larga de las subsecuencias de frecuencia máxima es única
la frecuencia máxima de cualquier longitud- $k$ subsecuencia es unimodal en $k$

Posiblemente enlaces relacionados:

Contando # subsecuencias distintas $\in \mathbf{P}$ http://11011110.livejournal.com/254164.html
Problema de concurso relacionado para múltiples fuentes http://www.spoj.pl/problems/CSUBSEQS/
Documento relacionado http://dx.doi.org/10.1016/j.tcs.2008.08.035

Editar 10 días después: ¡ gracias por echar un vistazo! Me preguntaba si esto sería un buen problema de concurso de programación solucionable en tiempo polinómico. Supongo que no, pero espero volver a pensarlo más tarde.

ds.algorithms string-search daveagp
fuente

Una pregunta inicial posiblemente ingenua: ¿está claro que este problema está incluso en NP ? Es decir: para el problema de determinar si hay una subsecuencia con al menos k ocurrencias en una cadena de n caracteres, ¿cómo sería un certificado? Por ejemplo, enumerar todas las tuplas de índices que indican que las instancias de una subsecuencia dada no tendrían un tamaño polinómico para la cadena aaa ... aa (que, aunque es una entrada aburrida, tiene una subcadena con aproximadamente

ocurrencias).

n C (n / 2)

$n \mathbf C (n/2)$

Niel de Beaudrap

@Niel de Beaudrap: Creo que podemos contar el número de ocurrencias como subsecuencias en tiempo polinómico mediante programación dinámica, lo que hace posible utilizar la subsecuencia misma como un certificado.

Tsuyoshi Ito

Estoy un poco confundido: ¿la pregunta "dada una cadena s, encuentra la subsecuencia que ocurre el número máximo de veces?"

Suresh Venkat

@SureshVenkat: Sí, ese es mi entendimiento. Por ejemplo, dada una secuencia de

X como entrada, la respuesta correcta sería una secuencia de

n

$n$

n / 2

$n/2$

Jeffε

@ marzio-de-biasi: la pregunta a la que te vinculaste es diferente (y mucho más fácil): allí tienes la subsecuencia.

David

Respuestas:

de una búsqueda, aquí hay un documento con algunas investigaciones y hallazgos para la investigación a nivel de posgrado pero (advertencia) sin referencias. tiene algunas heurísticas, estimaciones, resultados empíricos y comentarios sobre el problema y algunas ideas para probar su complejidad (aproximación), etc.

Identificación de las subsecuencias más frecuentes
CSE 549 Proyecto Final de Biología Computacional Informe final
Mikhail Bautin 2006

(Si bien hay algunos problemas de subsecuencia estándar que son algo similares y estudiados, por ejemplo, en el artículo de Elzinga et al, ¿es posible que este problema de subsecuencia en particular no se haya estudiado demasiado?)

vzn
fuente

No entiendo por qué esto fue rechazado. Puede que no sea un documento muy profundo, pero parece estar directamente sobre el tema.

David Eppstein

para su información / apéndice Bautin también dice que al final del documento tiene 5K líneas de código C ++ y Python en el problema / documento para cualquier persona interesada

vzn

@David, no creo que el voto negativo se deba al documento vinculado, probablemente tenga más que ver con el hecho de que esta respuesta parece (esencialmente) una respuesta de enlace de una línea (sin explicar cómo se relaciona el documento con la pregunta y lo contesta). Esto podría haber sido más apropiado como comentario.

Kaveh

ok kaveh, entonces, deletreado: el documento parece revelar (a menos que alguien pueda encontrar una mejor referencia o presentar una prueba de este difícil problema) que la complejidad exacta del problema es hasta ahora desconocida / abierta (aparte de lo obvio PSpace / ExpTime) y puede contener los análisis / enfoques más conocidos para resolverlo hasta ahora

vzn

Encontré este documento antes y me disculpé por no vincularlo anteriormente, lo cual fue porque no pensé que proporcionara mucha información concreta. Le envié un correo electrónico al autor hace algún tiempo preguntándole si podía decir algo más sobre lo que sucedió desde que fue escrito, pero aún no obtuve respuesta.

daveagp

No es una respuesta, solo un lema.

${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$ $t$ $k$ $t$

domotorp
fuente