Permutationsmusterabgleich in Zeichenfolgen

10

Der Permutationsmusterabgleich befasst sich grob gesagt mit Problemen der folgenden Art:

Gegebenen Permutationen in S n und σ in S m , wobei m n , tut π eine enthalten Subsequenz τ der Länge m , deren Elemente geordnet nach σ ?πSnσSmmnπ τmσ

Wenn beispielsweise und σ = 2 1 3 , dann sind die Subsequenz 3 1 4 Matches & sgr; . Wie Sie sehen können, suchen wir hier nicht nach einer genauen Übereinstimmung, sondern nach etwas, das dem angegebenen Muster "ähnelt".π=3 1 5 4 2 8 6 7σ=2 1 33 1 4σ

Weiß jemand, ob daran gearbeitet wurde, Permutationsmuster-Matching-Probleme auf Strings auszudehnen? Google hat leider nicht geholfen, da das bekannte Pattern-Matching-Problem bei Strings nichts damit zu tun hat.

Anthony Labarre
quelle
Ich forsche derzeit an affinen Permutationsmustern. Es gibt einige Arbeiten, aber die meisten davon sind nur für Akademiker verfügbar.
abigail3306

Antworten:

3

Baars, Löh und Swierstra implementierten Permutationsparser für Haskell (Journal of Functional Programming / Band 14 / Ausgabe 06, S. 635 - 646). Diese können verwendet werden, um die Permutation einer Sammlung von Parsern anzugeben. Wenn jeder dieser Parser ein optionaler Parser für ein einzelnes Zeichen ist (dh mit dem Zeichen oder nichts übereinstimmt), haben Sie die Zutaten, nach denen Sie suchen. Ich glaube, dass ihre Bibliothek mit GHC verfügbar ist.

Dave Clarke
quelle
0

Sie sollten von Revital Eres, Gad M. Landau und Laxmi Parida ausgehen: Entdeckung von Permutationsmustern in Biosequenzen . Journal of Computational Biology 11 (6): 1050 & ndash; 1060 (2004).

Gianluca Della Vedova
quelle
Dies scheint nicht dasselbe zu sein: Sie sind daran interessiert, Gruppen von Zeichen zu lokalisieren, die zusammen auftreten, ohne die Reihenfolge zu berücksichtigen . Das gleiche Problem bei Permutationen wird als "Identifizieren gemeinsamer Intervalle" bezeichnet.
Anthony Labarre
@Labarre Ich stimme Ihrem Kommentar zu. Soll ich meine Antwort löschen?
Gianluca Della Vedova
1
Bitte nicht löschen. Ihre Antwort und Labarres Kommentar haben mir geholfen, die Frage besser zu verstehen.
Aaron Sterling
@ Aaron Sterling Dann sollten wir die Frage bearbeiten, nicht wahr?
Gianluca Della Vedova
2
Ich denke, die Frage ist derzeit relativ klar.
Suresh Venkat