Gilles Didier
I2M, CNRS, Marseille
/user/gilles.didier/
Date(s) : 24/05/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 Bernoulli. 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 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 (a priori tous les algorithmes usuels peuvent être codés sous cette forme). Étant donné 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|). Nous montrons que si un texte est Bernoulli alors la séquence des états internes d’un algorithme est une chaîne de Markov à états cachés dont on sait expliciter les probabilités de transition, ce qui permet d’en calculer la vitesse asymptotique.
Notre résultat principal est, qu’étant donnés un motif w, un entier k≤|w|-1 et un modèle Bernoulli, 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, …, n}vers l’alphabet telles que, pour tout i<|w|, si f(i) est défini alors f(i) = 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 Bernoulli donnés.
Average complexity of pattern matching algorithms and optimality
We study the asymptotic speed of pattern matching algorithms looking for a pattern w in a Bernoulli random text. The asymptotic speed is defined as the limit, as n approaches infinity, of the expectation of the ratio of n by the number of read accesses made for a random text of size n. The study is limited to algorithms which, at each iteration and from the current position, read a relative position determined by their internal state and, depending on the letter read, change internal state, increment (or not) the current position. and, where appropriate, signal a match (a priori all the usual algorithms can be coded in this form). Given w, the order of an algorithm is the largest position, relative to the current position, that it reads while searching for w (usually |w|-1 or |w|). We show that if a text is Bernoulli then the sequence of internal states of an algorithm is a Markov chain with hidden states whose transition probabilities we know how to make explicit, which makes it possible to calculate its asymptotic speed.
Our main result is, that given a pattern w, an integer k≤ | w | -1 and a Bernoulli model, there exists, among the algorithms of order k, a maximal asymptotic speed algorithm whose set of states internal is in bijection with a subset of the partial functions f from {0,…, n} to the alphabet such that, for all i<|w|, if f(i) is defined then f (i) = wᵢ .
The number of algorithms verifying this property being finite, it is possible to evaluate them all and thus to determine an optimal algorithm for a given pattern, order and Bernoulli model.
https://arxiv.org/abs/1604.08437
Catégories