II. Recherche textuelle

Cours

Introduction

Rechercher une chaîne de caractères dans une autre (une sous-chaine dans une chaîne) est un problème récurrent en informatique et dans d’autres sciences. La question se pose particulièrement en génétique pour localiser un motif M dans une séquence S d’ADN.

On peut, par exemple, rechercher le motif M dans la séquence S suivante :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

A. Approche « naïve »

Une première approche naïve est de placer le motif le plus sur la gauche possible, de le décaler vers la droite d’une lettre à la fois et de le comparer à la séquence jusqu’à trouver une correspondance.

Pseudo-code

fonction recherche_naive(S, M):
    n <- longueur de S
    m <- longueur de M
    pour i de 0 à n-m
        j <- 0
        tant que j est inférieur à m et S[i+j] est égal à M[j] :
            j <- j+1
            si j est égal à m :
                renvoyer (M, i)

Pourquoi fait-on une boucle bornée parcourant n-m caractères ?

La séquence s’arrête à l’indice n-1, mais puisque l’on cherche la correspondance du motif en entier, on peut s'arrêter à l'indice n-m-1.

Que stocke la variable j ?

j stocke le nombre de caractères qui coïncident entre S et M, à une position i donnée, en commençant par la gauche de M.

Comment décide-t-on quand s’arrêter ?

Deux cas sont possibles : à la fin de la boucle bornée, c’est-à-dire lorsqu’on a parcouru toute la séquence sans trouver le motif, ou bien lorsqu’on le trouve : on est dans ce cas lorsque j vaut m.

Estimons la complexité de cette approche. L’opération élémentaire comptabilisée est la comparaison entre 2 cases des chaînes S et M. Dans le pire des cas, les deux boucles (bornée et non-bornée) sont parcourues en entier. C’est-à-dire la boucle bornée est itérée \(n-m\) fois et la boucle non-bornée \(m\) fois. La complexité est donc en \(O((n-m)m)\).

B. L’algorithme de Boyer-Moore

B.1. Exemple

Pour améliorer cette méthode (c'est-à-dire avoir une meilleure complexité), nous allons utiliser l’algorithme de Boyer-Moore dans sa version simplifiée par Horspool.

Expliquons cet algorithme par un exemple, celui présenté en introduction. On commence par placer le motif M le plus à gauche possible de la séquence S :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

Le dernier caractère de M coïncide avec le 6ème de S. On compare alors les deux précédents.

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

Ces deux caractères ne coïncident pas. Mais le caractère de la séquence (C) apparaît tout de même dans M. On décale alors M pour que le caractère C de S coïncide avec le même caractère dans M :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

On recommence alors la comparaison en partant de la droite de M :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

Les caractères ne coïncident pas, mais G apparaît dans M. On décale donc ce dernier de manière à faire coïncider le G de S avec le premier G de M rencontré en partant de la droite :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

On recommence la comparaison en partant de la droite de M.

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

Les caractères les plus à droite coïncident, mais pas ceux précédant. On décale alors M pour faire coïncider le G de S avec le premier G de M rencontré en partant de la droite :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

Les derniers caractères ne coïncident pas, on décale alors M pour faire coïncider le T de S avec le T de M :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

Les derniers et avant-derniers caractères coïncident, mais pas ceux d’avant. On décale donc pour faire coïncider le A de S avec le A de M à gauche des caractères qui coïncidaient :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

Les derniers caractères ne coïncident pas. On décale donc M pour faire coïncider le G de S avec le premier G de M en partant de la droite :

S	A T A A C A G A G A A T A A G G C T A G G A A A T A C T G A A
M	A G G C T A

Il y a correspondance entre M et une partie de la séquence, l’algorithme s’arrête donc.

B.2. Principe de l’algorithme

Quelle partie du motif commence-t-on par comparer ?

On commence par comparer le dernier caractère du motif, puis l’avant-dernier, etc.

Quand sait-on que l’on doit décaler le motif ?

On sait que l’on doit décaler le motif lorsque que l’on arrive à un caractère dans la séquence qui ne coïncide pas avec caractère du motif à la même position.

Comment détermine-t-on alors de combien d’éléments décaler le motif, c’est-à-dire le nombre de sauts à effectuer ? Distinguer le cas dans lequel l'élément de la séquence n'est pas dans le motif, du cas dans lequel il est dans le motif.

Si l’élément de la séquence considéré n’est pas dans le motif, on décale le motif à la position de l’élément + 1. Si l’élément de la séquence considéré est à une autre place dans le motif, on décale le motif de manière à le faire coïncider avec ce caractère de la séquence, en prenant le caractère du motif le plus à droite possible, mais sans le faire revenir "en arrière".

Note : Nous avons pris l'exemple de la recherche d'un motif dans une séquence d'ADN, mais plus généralement on peut parler de la recherche de sous-chaîne dans une chaîne de caractères.

---

Exercice

1. Appliquer l’algorithme de Boyer-Moore pour rechercher le motif "EXEMPLE" dans le texte suivant :
   VOICI UN SIMPLE EXEMPLE

1. Appliquer l’algorithme de Boyer-Moore pour rechercher le motif "C T A G G" dans la séquence suivante :
   A T A A C A G A G A A T A A G G C T A G G A A A T A C

On détaillera toutes les étapes de la même façon que dans le cours.

---

Conclusion

L’étude de la complexité de cet algorithme dépasse le programme de NSI, mais on observe bien qu’avec les décalages effectués, on ne parcourt pas tous les éléments. Ces décalages, ou sauts, sont à la base de l’implémentation de cet algorithme que nous allons voir en TP.

---

TP : Implémentation des algorithmes de recherche textuelle

A. L’algorithme de recherche naïve

1. Reprendre l’algorithme de recherche naïve du cours et le traduire en Python par la fonction recherche.

2. Tester la fonction pour M valant "BRA" et S valant 'ABRACADABRA'.

3. Modifier cette fonction pour que le programme ne s’arrête pas la première fois le motif recherché, mais pour qu’il compte le nombre d’occurrence de ce motif dans l’ensemble de la séquence. La fonction compte ainsi créée ne retournera donc pas la position de la première occurrence du motif mais le nombre d’occurrences de celui-ci.

B. L’algorithme de Boyer-Moore-Horspool

B.0. Programme global

Code

def recherche(texte, motif):
    n = len(texte)
    m = len(motif)
    aDroite = calcule_a_droite(motif)
    i = 0
    while i + m <= n:
        ok, decalage = correspondance(texte, motif, i, aDroite)
        if ok:
            return i
        else:
            i = i + decalage
    return -1

Notre programme sera basé sur la fonction recherche. Cette fonction commence par calculer la table de sauts qui donne la position la plus à droite dans le motif de chaque caractère, et représentée par le dictionnaire aDroite avec la fonction calcule_a_droite. recherche fait ensuite appel à une fonction correspondance estimant si, à partir d’un indice i, il y a correspondance entre le texte et le motif. Cet appel à correspondance est fait tant que l’on n’a pas trouvé le motif et que l’on n’est pas arrivés à la fin.

Nous allons écrire les différentes fonctions intermédiaires utilisées par recherche, avant de faire fonctionner l’ensemble du programme.

B.1. La table de sauts

Pour implémenter l’algorithme, nous allons commencer par établir une table de sauts, indiquant la position la plus à droite de chaque caractère du motif. On utilisera un dictionnaire aDroite dont les clés sont les caractères du motif, et les valeurs l’indice de leur position la plus à droite par rapport au début du motif. On le remplit en effectuant une boucle for parcourant tous les caractères du motif.

Par exemple pour le motif « HELLO », on fera :

aDroite[‘H’] = 0
aDroite[‘E’] = 1
aDroite[‘L’] = 2
aDroite[‘L’] = 3
aDroite[‘O’] = 4

a. Après exécution de ce programme, quelles valeurs sont associées aux clés ‘H’, ‘E’, ‘L’ et ‘O’ ?

b. On utilise une fonction calcule_a_droite pour remplir ce dictionnaire. Compléter le code suivant :

Code

def calcule_a_droite(motif):
    m = len(motif)
    aDroite = { }
    for j in range(m):
        ………………………….
    return aDroite

c. Appeler calcule_a_droite sur le motif 'HELLO'.

B.2. Trouver le décalage

On utilisera la fonction droite suivante qui renvoie -1 si le caractère c n’est pas dans le motif et sinon la valeur associée à la clé c dans le dictionnaire aDroite :

Code

def droite(c, aDroite):
    if c in … :
        ...
    else:
        ...

B.3. Test de la correspondance

Nous allons maintenant écrire la fonction correspondance.

Pseudo-code, à compléter :

fonction correspondance(texte, motif, i, aDroite)
    Entrées :
        texte : séquence en chaîne de caractères
        motif : motif recherché en chaîne de caractères
        i : position actuelle dans le texte, correspondant à la position du caractère le plus à gauche du motif
        aDroite : table de sauts en dictionnaire

    Sorties :
        booléen indiquant si la correspondance a été trouvée
        decalage (entier) pour la prochaine étape, ou 0 si la correspondance a été trouvée

    Pour j variant de l’indice du dernier caractère du motif au premier de manière décroissante
        x ← le caractère à l’indice i+j de texte
        si x est différent de l’indice j du motif
            alors le décalage est égal au maximum entre 1 et j-droite(x, aDroite)
            renvoyer ???, ???
    renvoyer ???, ???

B.4. Tests

Tester l’ensemble du programme, comprenant les quatre fonctions calcule_a_droite, droite, recherche et correspondance, sur les exemples suivants :
a. texte : ‘AGTCCGTAATGATCGGTACCTGACTGTA’, motif : ‘CTGAC’
b. texte : ‘ALGORITHME DE BOYER-MOORE-HORSPOOL’, motif : ‘MOORE’