Häufigste Folge

Ein String hat $2^n$ Untersequenzen, die jedoch normalerweise nicht alle verschieden sind. Wie komplex ist es, die maximale Häufigkeit einer Teilsequenz zu finden?

Beispielsweise enthält die Zeichenfolge "Subsequence" 7 Kopien der Subsequence "Sue" und dies ist das Maximum.

Beispiel für einen Brute-Force-Code unter http://ideone.com/UIp3t

Gibt es verwandte Struktursätze? Beides erweist sich als falsch :

Die längste der maximal frequenten Teilsequenzen ist eindeutig
Die maximale Frequenz einer beliebigen Länge- $k$ Folge ist in unimodal $k$

Möglicherweise verwandte Links:

Zählen von # unterschiedlichen Untersequenzen $\in \mathbf{P}$ http://11011110.livejournal.com/254164.html
Zugehöriges Wettbewerbsproblem für mehrere Quellen http://www.spoj.pl/problems/CSUBSEQS/
In Verbindung stehendes Papier http://dx.doi.org/10.1016/j.tcs.2008.08.035

Bearbeiten Sie 10 Tage später: Vielen Dank, dass Sie einen Blick darauf werfen! Ich hatte mich gefragt, ob dies ein nettes Problem mit einem polynomiell lösbaren Programmierwettbewerb darstellen würde. Ich denke nicht, aber ich hoffe, später noch einmal darüber nachzudenken.

ds.algorithms string-search daveagp
quelle

Eine möglicherweise naive Ausgangsfrage: Ist klar, dass dieses Problem auch in NP besteht ? Das heißt: Wie würde ein Zertifikat für die Frage aussehen , ob es eine Teilfolge mit mindestens k Vorkommen in einer n- Zeichenfolge gibt? Zum Beispiel würde eine Auflistung aller Indextupel, die die Instanzen einer gegebenen Teilsequenz angeben, für die Zeichenfolge aaa ... aa (die zwar eine langweilige Eingabe enthält, jedoch eine Teilzeichenfolge mit ungefähr

keine polynomielle Größe haben. Vorkommen).

n C (n / 2)

$n \mathbf C (n/2)$

Niel de Beaudrap

@Niel de Beaudrap: Ich denke, dass wir durch dynamische Programmierung die Anzahl der Vorkommen als Teilfolgen in der Polynomzeit zählen können, wodurch es möglich wird, die Teilfolge selbst als Zertifikat zu verwenden.

Tsuyoshi Ito

Ich bin ein wenig verwirrt: Ist die Frage "Wenn eine Zeichenfolge angegeben wird, finden Sie die Teilfolge, die maximal so oft vorkommt?"

Suresh Venkat

@ SureshVenkat: Ja, das ist mein Verständnis. Beispielsweise wäre bei einer Folge von

X als Eingabe die richtige Antwort eine Folge von

n

$n$

n / 2

$n/2$

Jeffs

@ Marzio-de-Biasi: Die Frage, mit der Sie verknüpft sind, ist anders (und viel einfacher): Dort erhalten Sie die Teilfolge.

David

Antworten:

Nach einer Recherche finden Sie hier einen Artikel mit Recherchen und Ergebnissen für die Forschung auf Hochschulniveau, jedoch (Vorbehalt) keine Referenzen. Es enthält einige Heuristiken, Schätzungen, empirische Ergebnisse und Kommentare zum Problem sowie einige Ideen zum Nachweis der (Approximations-) Komplexität usw.

Identifizierung der häufigsten Folgen
CSE 549 Computational Biology Project Abschlussbericht
Mikhail Bautin 2006

(Während es einige Standard-Subsequenzprobleme gibt, die ähnlich sind und untersucht wurden, z. B. in der Arbeit von Elzinga et al., ist es möglich, dass dieses spezielle Subsequenzproblem nicht zu viel untersucht wurde?)

vzn
quelle

Ich verstehe nicht, warum dies abgelehnt wurde. Es ist vielleicht kein sehr ausführliches Papier, aber es scheint direkt zum Thema zu gehören.

David Eppstein

fyi / addendum Bautin sagt auch, dass er am Ende des Papiers 5K Zeilen C ++ & Python-Code zum Problem / Papier für alle Interessierten hat

vzn

@ David, ich denke nicht, dass die Ablehnung auf das verlinkte Papier zurückzuführen ist, sondern eher auf die Tatsache, dass diese Antwort (im Wesentlichen) wie eine einzeilige Link-Antwort aussieht (ohne zu erklären, wie das Papier mit der Frage zusammenhängt) und beantwortet es). Dies hätte als Kommentar angemessener sein können.

Kaveh

ok kaveh, also klargestellt: das papier scheint zu enthüllen (es sei denn, jemand kann einen besseren ref finden oder sich selbst einen beweis für dieses schwierige problem liefern), dass die genaue komplexität des problemes bisher unbekannt / offen ist (außer dem offensichtlichen) PSpace / ExpTime) und enthält möglicherweise die bekanntesten Analysen / Lösungsansätze

vzn 29.08.12

Ich habe dieses Papier schon einmal gefunden und mich dafür entschuldigt, dass ich oben nicht darauf verlinkt habe, da ich nicht dachte, dass es viele konkrete Informationen enthält. Ich habe dem Autor vor einiger Zeit eine E-Mail geschickt, in der er gefragt wurde, ob er noch etwas zu dem sagen könne, was passiert ist, seit es geschrieben wurde, aber er hat noch keine Antwort erhalten.

Daveagp

Keine Antwort, nur ein Lemma.

Zuallererst könnte man sich fragen, was die häufigste Folge von Strings wie 12..t12..t12..t .. ist. Nach einigem Überlegen merkt man, dass es auch die Form 12..t12..t12 .. haben muss, nur offensichtlich kürzer. Wenn die ursprüngliche Zeichenfolge die Länge nt und die Teilfolge dieser Sonderform die Länge k hat, ist die Anzahl ihrer Vorkommen genau ${n+k-\lceil k/t\rceil \choose k}={n+k-\lceil k/t\rceil \choose n-\lceil k/t\rceil}$ $t$ $k$ $t$

domotorp
quelle