Programme officiel

Contenus	Capacités attendues	Commentaires
Recherche textuelle.	Étudier l’algorithme de Boyer- Moore pour la recherche d’un motif dans un texte.	L’intérêt du prétraitement du motif est mis en avant.L’étude du coût, difficile, ne peut être exigée

La recherche d’une sous-chaine a des applications importantes en informatiques, par exemple dans les moteurs de recherche. Nous commencerons par une application naïve puis nous verrons qu’il est bien plus efficace de faire la recherche en sens inverse en partant du dernier caractère du mot pour ne pas tester toutes les positions.

Nous allons visualiser la vidéo ci-dessous et effectuer les implémentation sous python en mettent la vidéo en pause, les solutions des programme python sont données plus loin dans l’article.

Algorithme naïf

Nous allons appliquer une méthode itérative brute pour rechercher une sous-chaine dans une chaine de caractères.

Nous allons avancer dans le texte caractère par caractère, puis si le caractère considéré correspond au premier caractère du mot, nous comparerons les caractères suivants à ceux du mot. si la recherche s’avère fructueuse on renvoie True.

implémentation algorithme naïf python corrigé

L’exécution est relativement lente, la fonction doit tester N-n positions dans texte et pour chacune effectuer jusqu’à N-n comparaisons, soit jusqu’à (N−n)×n.

La complexité de cet algorithme est dans le pire des cas O ((N−n)×n), c’est une complexité quadratique O(N²) car souvent  N>>n.

Nous allons voir qu’il est beaucoup plus efficace de faire la recherche à l’envers à partir de la fin du mot.

L’algorithme de Boyer-Moore : version simplifiée de Horspool

Nous allons étudier une version simplifiée du meilleur algorithme connu : l’algorithme de Boyer-Moore qui a été proposé par Nigel Horspool.

Cet algorithme repose sur deux idées :

1. On compare le mot de droite à gauche à partir de sa dernière lettre.
2. On n’avance pas dans le texte caractère par caractère, mais on utilise un décalage dépendant de la dernière comparaison effectuée.

Déroulement de l’algorithme

Nous considérons ici la recherche du motif mot = 'dab' dans le texte texte = 'abracadabra'.

On commence la recherche à l’index 2 :

abracadabra
dab

Il n’y a pas de correspondance à la fin du mot : 'r' != 'b', donc on avance, mais de combien de caractères avance-t-on. Pour le décider, on utilise le fait que le caractère 'r' n’apparait pas dans le mot cherché, donc on peut avancer de n = len(mot) = 3 caractères sans crainte de rater le mot.

On recherche donc à l’indice 2 + 3 = 5 :

abracadabra
   dab

Il n’y a pas de correspondance à la fin du mot : 'a' != 'b', donc on avance, cependant, cette fois, comme le caractère 'a' apparait pas dans le mot cherché en avant-dernière position, on ne peut avancer que de une case pour faire une comparaison en alignant les 'a'.

On recherche donc à l’indice 5 + 1 = 6 :

abracadabra
    dab

Il n’y a pas de correspondance à la fin du mot : 'd' != 'b', donc on avance, cependant, cette fois, comme le caractère 'd' apparait dans le mot cherché en avant-avant-dernière position(première position, mais on doit lire à l’envers !), on avance de deux cases pour faire une comparaison en alignant les 'd'.

On recherche donc à l’indice 6 + 2 = 8 :

abracadabra
      dab

Maintenant lorsqu’on effectue les comparaisons à l’envers : les 'b', puis les 'a', puis les 'd' correspondent. On a trouvé le mot on renvoie VRAI.

Implémentation en Python

Pour implémenter efficacement cet algorithme, on va passer par un pré-traitement du nom pour facilement accéder au décalage à effectuer. On utilise un dictionnaire pour cela.

Implémentation du pré-traitement python corrigé.

Maintenant la fonction de recherche :

Implémentation recherche en python corrigé.