Algorithmique : Recherche Textuelle

k777-9791_30

La recherche d’un motif (une sous-chaîne) dans un texte est un problème fondamental en informatique. Que ce soit pour la fonction « Rechercher » de votre éditeur de texte ou pour l’analyse de séquences génomiques en bioinformatique, l’efficacité de ces algorithmes est cruciale.

1. Le problème de la recherche textuelle

L’objectif est de déterminer si une chaîne de caractères appelée motif est présente dans une chaîne plus longue appelée texte, et si oui, à quel(s) indice(s).

Exemple :

  • Texte : L'informatique est la science du traitement automatique.
  • Motif : mati
  • Résultat : Le motif est présent à l’indice 8. (Rappel : l’indice commence à 0 et les espaces comptent).

2. L’algorithme de recherche « Naïf »

L’approche la plus simple consiste à faire glisser le motif devant le texte, caractère par caractère, et à vérifier la correspondance à chaque position.

Fonctionnement :

  1. On aligne le début du motif avec le début du texte.
  2. On compare les caractères un par un.
  3. Dès qu’une différence apparaît, on décale le motif d’une seule position vers la droite et on recommence.

Limites :

Cet algorithme est peu efficace. Dans le pire des cas, si le texte et le motif sont très longs et répétitifs, le nombre de comparaisons devient colossal.

def occurrence(m, t, i):
    """indique s’il y a une occurrence de la chaîne m dans la chaîne t à la position i"""
    if i < 0 or i > len(t) - len(m):
        return False
    for j in range(len(m)):
        if t[i + j] != m[j]:
            return False
    return True

def recherche(m, t):
    """affiche toutes les occurrences de m dans t"""
    for i in range(0, len(t) - len(m) + 1):
        if occurrence(m, t, i):
            print("occurrence à la position", i)

3. L’algorithme de Boyer-Moore-Horspool

L’algorithme de Boyer et Moore est un algorithme de recherche textuelle très efficace developpé en 1977. Robert Stephen Boyer et J Strother Moore travaillaient alors à l’université d’Austin au Texas en tant qu’informaticiens.

En 1980, Nigel Horspool a conçu une variante simplifiée de l’algorithme de Boyer-Moore.
C’est cette version qu’on va étudier dans ce paragraphe.

Robert Stephen BoyerJ Stroter MooreNigel Horspool

L’algorithme de Boyer-Moore (souvent étudié en NSI via sa version simplifiée, l’algorithme de Boyer-Moore-Horspool) améliore considérablement les performances grâce à deux idées géniales :

  1. Sens de lecture : On compare les caractères du motif en partant de la droite (la fin du motif) vers la gauche.
  2. Sauts stratégiques : Au lieu de décaler de 1, on effectue un prétraitement du motif pour savoir de combien de cases on peut « sauter » en cas d’erreur.

Exemple de fonctionnement :

Soit le texte ADN suivant : CGTGCCTACTTACT et le motif : TACT.

  1. Alignement initial : On compare la dernière lettre du motif (T) avec la lettre correspondante du texte.
  2. Saut de caractère : Si la lettre du texte n’existe pas du tout dans le motif, on peut décaler le motif de toute sa longueur !
  3. Alignement partiel : Si la lettre du texte existe dans le motif, on décale pour faire correspondre la dernière occurrence de cette lettre dans le motif.

[Image d’illustration : Comparaison du motif « TACT » sur un texte. Montrer une flèche de saut qui dépasse plusieurs caractères d’un coup grâce à la règle du mauvais caractère.] Mode d’emploi image : Générez un schéma montrant le texte CGTGCCTACT... et le motif TACT. Montrez que comme ‘G’ (dans le texte) n’est pas dans TACT, on déplace le motif directement après le ‘G’.

4. Mise en pratique : Analyse d’ADN

En bioinformatique, on cherche souvent des séquences spécifiques dans l’ADN (composé des bases A, T, G, C).

À faire vous-même 1

Appliquez manuellement l’algorithme de Boyer-Moore pour trouver le motif ACCTTCG dans la séquence suivante : CAATGTCTGCACCAAGACGCCGGCAGGTGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAG

À faire vous-même 2 : Implémentation Python

Voici une implémentation de l’algorithme utilisant la table des sauts (prétraitement du motif). Étudiez le code :

NO_CAR = 256 # Taille du jeu de caractères ASCII

def recherche_boyer_moore(txt, motif):
    m = len(motif)
    n = len(txt)
    
    # Prétraitement : on stocke la dernière position de chaque caractère du motif
    tab_car = [-1] * NO_CAR
    for i in range(m):
        tab_car[ord(motif[i])] = i
        
    decalage = 0
    res = []
    
    while(decalage <= n - m):
        j = m - 1 # On commence par la fin du motif
        
        # On remonte vers la gauche tant que les caractères correspondent
        while j >= 0 and motif[j] == txt[decalage + j]:
            j = j - 1
            
        if j < 0:
            # Motif trouvé !
            res.append(decalage)
            # Décalage pour trouver l'occurrence suivante
            if decalage + m < n:
                decalage += m - tab_car[ord(txt[decalage + m])]
            else:
                decalage += 1
        else:
            # Erreur de correspondance : on utilise la table de sauts
            # On décale au maximum entre 1 et la règle du mauvais caractère
            decalage += max(1, j - tab_car[ord(txt[decalage + j])])
            
    return res

# Test
mon_texte = "CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCG"
mon_motif = "ACCTTCG"
print(f"Motif trouvé aux indices : {recherche_boyer_moore(mon_texte, mon_motif)}")

À faire vous-même 3

  1. Copiez le code ci-dessus dans votre IDE (Spyder, VS Code ou EduPython).
  2. Testez-le avec la séquence ADN complète fournie dans l’exercice 1.
  3. Comparez le temps d’exécution (théorique) avec l’algorithme naïf sur de très gros fichiers (comme un chromosome complet).

à retenir : L’algorithme naïf compare de gauche à droite et décale de 1. Complexité O(n×m).

4. L’algorithme de Boyer-Moore (Bonus)

L’algorithme Boyer-Moore compare de droite à gauche et utilise un prétraitement pour effectuer des sauts. Il est beaucoup plus efficace sur des alphabets larges et de longs motifs.

super exemple d’utilisation de l’algorithme avec beaucoup d’explication au deuxième tiers de la page suivante. 

def table_bm(m):
    """construit la table de décalages de Boyer-Moore :
       d[j][c] est le plus grand k < j tel que m[k] == c,
       s’il existe, et n’est pas défini sinon"""
    d = [{} for _ in range(len(m))]
    for j in range(len(m)):
        for k in range(j):
            d[j][m[k]] = k
    return d

def decalage(d, j, c):
    """utilise la table d lorsque le caractère j est c
       au lieu du caractère attendu"""
    if c in d[j]:
        # c apparaît en d[j][c] et on décale de la différence
        return j - d[j][c]
    else:
        # c n’apparaît pas du tout dans m[0..j-1]
        return j + 1

def recherche(m, t):
    """affiche toutes les occurrences de m dans t
       avec l’algorithme de Boyer-Moore"""
    d = table_bm(m)
    i = 0
    while i <= len(t) - len(m):
        k = 0
        for j in range(len(m) - 1, -1, -1):
            if t[i + j] != m[j]:
                k = decalage(d, j, t[i + j])
                break
        if k == 0:
            print("occurrence à la position", i)
            k = 1
        i += k

Exercices d’application

Exercice 1 : Analyse de l’algorithme Naïf

En utilisant l’algorithme naïf, déterminez le nombre de comparaisons de caractères effectuées lors de la recherche du motif "chercher" dans le texte "chercher, rechercher et chercher encore". Note : On compte chaque comparaison, même celles qui échouent dès le premier caractère.

Exercice 2 : Première occurrence

En vous inspirant du fonctionnement de l’algorithme naïf, écrivez en Python une fonction premiere_occurrence(m, t) qui renvoie l’indice de la première occurrence du motif m dans le texte t. La fonction devra renvoyer None si le motif n’est pas présent.

Exercice 3 : Table de décalages (Boyer-Moore)

Construisez manuellement la table de décalages utilisée par l’algorithme de Boyer-Moore pour le motif suivant : "banane". Rappel : Pour chaque position j du motif, on cherche la position de la dernière occurrence du caractère lu dans le texte au sein de la partie gauche du motif.

Exercice 4 : Table de décalages avancée

Construisez manuellement la table de décalages de l’algorithme de Boyer-Moore pour le motif "chercher".

Exercice 5 : Déroulé complet et comparaison

En utilisant la table de décalages obtenue à l’exercice précédent, déroulez manuellement l’exécution de l’algorithme de Boyer-Moore pour la recherche du motif "chercher" dans le texte "chercher, rechercher et chercher encore".

  1. Listez les valeurs successives de la variable d’indice i.
  2. Indiquez le nombre total de comparaisons effectuées.
  3. Comparez ce résultat avec celui de l’exercice 1. Quel algorithme est le plus efficace ici ?

Corrections des exercices

Correction Exercice 1

Le motif "chercher" fait 8 caractères. Le texte fait 38 caractères.

  • À la position 0 : 8 comparaisons (succès).
  • À la position 1 (l’espace) : 1 comparaison (échec).
  • À la position 10 (début de « rechercher ») : 1 comparaison (‘r’ vs ‘c’).
  • À la position 12 (le ‘c’ de « rechercher ») : 8 comparaisons (succès).
  • En suivant ce processus, on compte toutes les tentatives de décalage de 1 en 1. Total : 54 comparaisons.

Correction Exercice 2

def premiere_occurrence(m, t):
    n = len(t)
    len_m = len(m)
    for i in range(n - len_m + 1):
        match = True
        for j in range(len_m):
            if t[i + j] != m[j]:
                match = False
                break
        if match:
            return i
    return None

Correction Exercice 3 (Motif « banane »)

On liste pour chaque index j le dictionnaire des caractères rencontrés précédemment :

  • j=0 : {}
  • j=1 (‘a’) : {'b': 0}
  • j=2 (‘n’) : {'b': 0, 'a': 1}
  • j=3 (‘a’) : {'b': 0, 'a': 1, 'n': 2}
  • j=4 (‘n’) : {'b': 0, 'a': 3, 'n': 2} (le ‘a’ en 3 écrase le ‘a’ en 1)
  • j=5 (‘e’) : {'b': 0, 'a': 3, 'n': 4}

Correction Exercice 4 (Motif « chercher »)

  • j=0 : {}
  • j=1 (‘h’) : {'c': 0}
  • j=2 (‘e’) : {'c': 0, 'h': 1}
  • j=3 (‘r’) : {'c': 0, 'h': 1, 'e': 2}
  • j=4 (‘c’) : {'c': 0, 'h': 1, 'e': 2, 'r': 3}
  • j=5 (‘h’) : {'c': 4, 'h': 1, 'e': 2, 'r': 3}
  • j=6 (‘e’) : {'c': 4, 'h': 5, 'e': 2, 'r': 3}
  • j=7 (‘r’) : {'c': 4, 'h': 5, 'e': 6, 'r': 3}

Correction Exercice 5

  1. Valeurs de i :
    • i=0 (Trouvé, on décale de 1 par défaut).
    • i=1 (Espace ‘ ‘, pas dans le motif : décalage j+1, ici 7+1=8).
    • i=9 (‘r’ vs ‘r’ OK, ‘e’ vs ‘e’ OK… jusqu’au ‘c’ de « rechercher »).
    • i=12 (Trouvé).
    • … et ainsi de suite.
  2. Nombre de comparaisons : Environ 22 comparaisons.
  3. Comparaison : Boyer-Moore est environ 2,5 fois plus efficace que l’algorithme naïf (54 vs 22 comparaisons) sur cet exemple grâce aux sauts de plusieurs caractères.

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *