Problème — Chercher k motifs en une seule passe — exercice corrigé d'informatique (MP2I/MPI) (chapitre 18)

1. L'algorithme. On range les $k$ empreintes dans une table de hachage (chapitre chap:hachage), puis on fait glisser une seule fenêtre sur le texte.


/* Affiche les couples (position, motif) pour tous les motifs trouves.
   Preconditions : les k motifs ont TOUS la longueur m, et n >= m >= 1.
   Complexite : Theta(km) de precalcul, puis Theta(n) en moyenne. */
typedef struct maillon { long long h; const char* p; struct maillon* suiv; } maillon;
static maillon* table[TAILLE_TABLE];

void multi_rabin_karp(const char t[], int n, const char* motifs[], int k, int m) {
    const long long B = 256, Q = 1000000007LL;
    for (int i = 0; i < TAILLE_TABLE; i = i + 1) { table[i] = NULL; }
    for (int i = 0; i < k; i = i + 1) { ajouter_motif(motifs[i], m); }

    long long ht = 0, puissance = 1;
    for (int j = 0; j < m - 1; j = j + 1) { puissance = (puissance * B) % Q; }
    for (int j = 0; j < m; j = j + 1) { ht = (ht * B + (unsigned char) t[j]) % Q; }

    for (int i = 0; i + m <= n; i = i + 1) {
        /* on ne parcourt QUE le seau de l'empreinte courante */
        for (maillon* x = table[ht % TAILLE_TABLE]; x != NULL; x = x->suiv) {
            if (x->h == ht && strncmp(t + i, x->p, (size_t) m) == 0) {
                printf("position %d : %s\n", i, x->p);       /* on VERIFIE toujours */
            }
        }
        if (i + m < n) {
            ht = (ht - (unsigned char) t[i] * puissance % Q + Q) % Q;
            ht = (ht * B + (unsigned char) t[i + m]) % Q;
        }
    }
}

Mesure sur un texte de $225$ caractères et les quatre motifs motif, texte, court, suite :


position  18 : motif      position  88 : texte      position 160 : motif
position  32 : texte      position 119 : texte      position 185 : motif
position  68 : motif      position 133 : suite      position 199 : texte
position  74 : court
                                            total : 10 occurrences

Une seule passe, une seule empreinte roulante.

2. Les complexités.

	$k$ recherches séparées	une passe multi-motifs
Précalcul	$Θ (k m)$	$Θ (k m)$
Parcours du texte	$Θ (k n)$	$Θ (n)$
Vérifications (moyenne)	$Θ (k n m / q)$	$Θ (k n m / q)$
Mémoire	$Θ (m)$	$Θ (k m)$

Le gain est le facteur $k$ sur le parcours, et il est exactement ce que le chapitre annonce : le texte n'est lu qu'une fois. Sur un antivirus à $1 0^{5}$ signatures, cela fait la différence entre une seconde et une journée.

La condition à ne pas perdre de vue : le nombre de vérifications reste proportionnel à $k$ . Si $q$ est trop petit devant $k$ , chaque fenêtre déclenche une vérification et l'on retombe en $Θ (k nm)$ . Le module doit croître avec le nombre de motifs, pas seulement avec leur longueur.

3. Des longueurs différentes. L'empreinte roulante suppose une fenêtre de taille fixe : on ne peut pas mélanger. Deux solutions.

Grouper par longueur : une passe par longueur distincte. Si les motifs ont $r$ longueurs différentes, le coût devient $Θ (r n)$ au lieu de $Θ (k n)$ — intéressant dès que $r ≪ k$ .
Tronquer : ne hacher que les $m_{m i n}$ premiers caractères de chaque motif, où $m_{m i n}$ est la plus petite longueur. Une fenêtre qui correspond devient une candidate, que l'on vérifie sur toute la longueur du motif. Une seule passe, au prix de plus de vérifications.

La vraie réponse à ce problème est l'algorithme d'Aho-Corasick, hors programme, qui traite $k$ motifs de longueurs quelconques en $Θ (n + \sum_{i} m_{i} + occurrences)$ dans le pire cas — en construisant un automate (chapitre chap:automates) sur l'ensemble des motifs. Rabin-Karp multi-motifs en est l'approximation probabiliste, et elle tient en trente lignes.

Problème — Chercher $k$ motifs en une seule passe

Énoncé

Corrigé

Exercices semblables