Gilles Didier
I2M, CNRS, Marseille
/user/gilles.didier/
Date(s) : 17/06/2016 iCal
11 h 00 min - 12 h 00 min
Nous étudions la vitesse asymptotique d’algorithmes de pattern matching cherchant un motif w dans un texte aléatoire iid. La vitesse asymptotique est définie comme la limite, quand n tend vers l’infini, de l’espérance du rapport de n par le nombre d’accès en lecture effectués pour chercher un motif donné dans un texte aléatoire de taille n. L’étude est limitée aux algorithmes qui, à chaque itération et à partir de la position courante, lisent une position relative déterminée par leur état interne et, selon la lettre lue, changent d’état interne, incrémentent (ou pas) la position courante et, le cas échéant, signalent un match (tous les algorithmes usuels peuvent être « codés » sous cette forme). Étant donné un motif w, l’ordre d’un algorithme est la plus grande position, relativement à la position courante, qu’il lit en cherchant w (généralement |w|-1 ou |w| pour les algorithmes usuels, où |w| désigne la longueur du motif w). On montre que si un texte est iid alors la séquence des états internes d’un algorithme est une chaîne de Markov dont on sait expliciter les probabilités de transition, ce qui permet d’en calculer la vitesse asymptotique.
On montre ensuite, qu’étant donnés un motif w, un entier k>=|w|-1 et un modèle iid, il existe, parmi les algorithmes d’ordre k, un algorithme de vitesse asymptotique maximale dont l’ensemble des états internes est en bijection avec un sous-ensemble des fonctions partielles f de {0, …, k} vers l’alphabet qui sont telles que, pour tout i<|w|, si f(i) est défini alors f(i) = w_i (i.e. la ième lettre de w).
Le nombre d’algorithmes vérifiant cette propriété étant fini, il est possible de tous les évaluer et de déterminer ainsi un algorithme optimal pour un motif, un ordre et un modèle iid donnés. L’approche a été implémentée et appliquée à des textes réels (anglais et ADN).
Catégories