Probleme – L'automate d'un motif, et le coût de la recherche

1. Les états. L'état après avoir lu un préfixe $u$ du texte est

$$q(u)=\text{longueur du plus long preˊfixe de }m\text{ qui soit un suffixe de }u.$$

Il y a $|m|+1$ valeurs possibles, de $0$ à $|m|$, et l'on trouve une occurrence exactement quand $q(u)=|m|$. La transition est alors forcée :

$$\delta (q,x)=\text{le plus grand }k\le \min (q+1,|m|)\text{ tel que }m[\mathrm{0..}k-1]\text{ soit un suffixe de }m[\mathrm{0..}q-1]x.$$

2. Le programme.

/* Construit la table delta de l'automate qui suit le motif.
   delta[q][x] = longueur du plus long suffixe de (motif[0..q-1] . x)
                 qui soit un prefixe du motif.
   Precondition : m = strlen(motif), 1 <= m < MAXM. */
static void construire(const char motif[], int m, int delta[][ALPHA]) {
    assert(m >= 1 && m < MAXM);
    for (int q = 0; q <= m; q = q + 1) {
        for (int x = 0; x < ALPHA; x = x + 1) {
            int k = (q + 1 < m) ? q + 1 : m;
            while (k > 0) {
                bool ok = (motif[k - 1] == 'a' + x);
                for (int i = 0; ok && i < k - 1; i = i + 1) {
                    if (motif[i] != motif[q - k + 1 + i]) { ok = false; }
                }
                if (ok) { break; }
                k = k - 1;
            }
            delta[q][x] = k;
        }
    }
}

/* Compte les occurrences (recouvrements compris) du motif dans le texte.
   Precondition : texte terminee par '\0', delta construite pour ce motif.
   INVARIANT : q vaut toujours la longueur du plus long prefixe du motif
               qui est un suffixe de texte[0..i-1].
   Complexite : Theta(n), une lecture par caractere, aucun retour en arriere. */
static int chercher(const char texte[], int delta[][ALPHA], int m) {
    int q = 0, occ = 0;
    for (int i = 0; texte[i] != '\0'; i = i + 1) {
        q = delta[q][indice(texte[i])];
        if (q == m) { occ = occ + 1; }
    }
    return occ;
}

3. La correction. Elle tient dans l'invariant écrit au-dessus de la boucle : $q$ est la longueur du plus long préfixe du motif qui est un suffixe de ce qui a été lu. Il est vrai avant le premier tour ($q=0$, rien de lu) ; il est conservé par définition même de $\delta$, qui calcule cette quantité pour le caractère suivant. À la sortie, chaque passage par $q=|m|$ correspond à une position où le motif se termine, et réciproquement.

Terminaison : variant $n-i$, où $n$ est la longueur du texte.

Complexités. La recherche est en $\Theta (n)$ : une lecture par caractère, jamais deux. La table écrite ainsi coûte $O(|m{|}^2\cdot |\Sigma |)$ — on peut descendre à $O(|m|\cdot |\Sigma |)$ en calculant les bords une fois pour toutes, ce qui est l'algorithme de Knuth-Morris-Pratt proprement dit. La table occupe $\Theta (|m|\cdot |\Sigma |)$ en mémoire, ce qui est la limite du procédé : sur un alphabet Unicode, elle devient coûteuse.

Le programme exécuté affiche la table du motif aba :

  delta(0, a) = 1   delta(0, b) = 0
  delta(1, a) = 1   delta(1, b) = 2
  delta(2, a) = 3   delta(2, b) = 0
  delta(3, a) = 1   delta(3, b) = 2

puis compare, sur cinq couples, le compte de l'automate à celui d'une recherche naïve par strncmp :

Le nombre de lectures est exactement la longueur du texte, dans les cinq cas, et les comptes coïncident, recouvrements compris : abababa contient trois fois aba.

4. La comparaison. Le chapitre chap:textes donne la méthode naïve, Boyer-Moore et Rabin-Karp ; voici où l'automate se place.

L'automate est le seul de la liste dont la borne du pire cas soit linéaire, et c'est ce qu'on achète en payant le prétraitement le plus cher. En calculant les bords une fois pour toutes plutôt que par la recherche naïve écrite plus haut, on descend le prétraitement à $\Theta (m\cdot |\Sigma |)$ : c'est l'algorithme de Knuth-Morris-Pratt, qui n'est pas au programme mais dont on vient d'écrire la table.

Mais surtout : l'automate généralise à un motif quelconque, décrit par une expression régulière, là où Knuth-Morris-Pratt ne sait chercher qu'un mot fixé. C'est le sens de la phrase du chapitre : le coût reste $\Theta (n)$ quelle que soit la complexité du motif cherché — et c'est exactement ce que fait grep.