Correspondance du modèle de permutation dans les chaînes

10

En gros, l'appariement des modèles de permutation traite des problèmes du type suivant:

Étant donné les permutations dans et dans , avec , contient-il une sous- séquence de longueur dont les éléments sont ordonnés selon ?πSnσSmmnπ τmσ

Par exemple, si et , la sous-séquence correspond . Comme vous pouvez le voir, nous ne recherchons pas ici une correspondance exacte, mais plutôt quelque chose qui "ressemble" au modèle spécifié.π=3 1 5 4 2 8 6 7σ=2 1 33 1 4σ

Quelqu'un sait-il si des travaux ont été menés pour étendre les problèmes de correspondance des modèles de permutation aux chaînes? Google n'a malheureusement pas aidé, car le problème bien connu de correspondance de motifs sur les chaînes n'a rien à voir avec cela.

Anthony Labarre
la source
Je fais actuellement des recherches sur les modèles de permutation affine. Il y a du travail, mais la plupart d'entre eux ne sont disponibles que pour les universitaires.
abigail3306

Réponses:

5

J'ai finalement réussi à déterrer une belle enquête de Kitaev et Mansour , qui donne des indications sur la littérature relative à la correspondance des modèles de permutation sur les permutations et les mots «habituels» / signés / colorés.

Anthony Labarre
la source
3

Baars, Löh et Swierstra ont implémenté des analyseurs de permutation pour Haskell (Journal of Functional Programming / Volume 14 / Numéro 06, pp 635 - 646). Ceux-ci peuvent être utilisés pour spécifier la permutation d'une collection d'analyseurs. Si chacun de ces analyseurs est un analyseur facultatif pour un seul caractère (c'est-à-dire, correspond au caractère ou rien), alors vous auriez les ingrédients que vous recherchez. Je crois que leur bibliothèque est disponible avec GHC.

Dave Clarke
la source
0

Vous devriez commencer par Revital Eres, Gad M. Landau, Laxmi Parida: Découverte de modèles de permutation dans les bioséquences . Journal of Computational Biology 11 (6): 1050-1060 (2004).

Gianluca Della Vedova
la source
Cela ne semble pas être la même chose: ils sont intéressés à localiser des groupes de personnages qui se produisent ensemble, sans tenir compte de l'ordre . Le même problème sur les permutations est appelé "identification des intervalles communs".
Anthony Labarre
@Labarre Je suis d'accord avec votre commentaire. Dois-je supprimer ma réponse?
Gianluca Della Vedova
1
Veuillez ne pas supprimer. Votre réponse et le commentaire de Labarre m'ont aidé à mieux comprendre la question.
Aaron Sterling
@Aaron Sterling Ensuite, nous devrions modifier la question, non?
Gianluca Della Vedova
2
Je pense que la question est relativement claire en l'état.
Suresh Venkat