TNSI : Recherche dans un Texte.
Activité 2 : Algorithme de Boyer-Moore de Recherche de Texte, Version Simplifiée de Horspool

Nigel Horspool est né en Grande-Bretagne mais est citoyen Canadien . Il est professeur émérite d’informatique de l’université de Victoria, retraité depuis \(2016\).

L'algorithme détaillé ci-dessous est appelé Algorithme de Boyer-Moore, Version Simplifiée de Horspool. C'est un algorithme de recherche textuelle (de recherche d'un motif dans un texte). Il reprend les idées de l'algorithme de recherche naïf précédent, mais en l'améliorant un peu (le décalage peut quelquefois être strictement supérieur à \(1\))

Deux Idées

• La première idée consiste à comparer le motif avec la portion du texte qui apparaît dans la fenêtre de droite à gauche, et non pas de gauche à droite. Ainsi, on fait décroître \(j\) à partir de \(p − 1\) jusqu’à ce que le caractère qui lui fait face dans le texte, c’est-à-direx = texte[i + j], soit différent du caractère y = motif[j] du motif.
• La deuxième idée consiste à opérer un décalage de la fenêtre qui varie en fonction de la paire de caractères qui ont révélé la non-correspondance, c’est-à-dire en fonction de \((x, y)\)

Déroulement de l'Algorithme de Boyer-Moore, Version Simplifiée de Horspool

Nous considérons ici la recherche du motif 'dab' dans le texte 'abracadabra'.
Avec nos notations, \(p = 3\), \(n = 11\) et la première occurrence du motif dans le texte apparaît en position \(i = 6\).

Pour \(i=0\)

On commence avec la fenêtre tout à gauche, c’est-à-dire avec \(i = 0\).

abracadabra
dab

Comme on commence à comparer de droite à gauche, c’est pour \(j = 2\) qu’il y a non-correspondance car motif[2] != texte[0 + 2] (en effet : 'b' != 'r')

On note x ='r' le caractère du texte qui ne correspond pas à y ='b' le caractère du motif qui lui fait face.
De combien peut-on décaler la fenêtre ? Comme \(x\) n’apparaît nulle part dans le motif, on peut carrément décaler le motif de \(p = 3\) unités vers la droite ! \(décalage = 3\)

Pour \(i=3\)

abracadabra
   dab

Ainsi on se retrouve avec \(i = 3\) et le premier échec intervient avec \(j = 2\), où le caractère x =texte[3 + 2]=='a' du texte est distinct du caractère face à lui dans le motif, c’est-à-dire y =motif[2]=='b'.
Mais à la différence du cas précédent, le caractère \(x\) apparaît bien dans le motif. On décale donc la fenêtre de \(1\) unité vers la droite.

Pour \(i=4\)

abracadabra
    dab

\(i = 4\), x ='d', y ='b', décalage de \(2\)

Pour \(i=6\)

Finalement, pour \(i = 6\), on trouve la première occurrence du motif.

abracadabra
      dab

Calcul du Décalage

• Dans le cas où \(x\) n’apparaît pas du tout dans le motif, il convient de déplacer la fenêtre pour qu’elle débute juste à droite du couple \((x, y)\) qui a provoqué l’échec de la recherche. Autrement dit, dans ce cas, le décalage est \(δ = j + 1\).
• Dans le cas où \(x\) apparaît dans le motif, il convient de déplacer la fenêtre pour que \(x\) apparaisse juste au-dessus de la lettre du motif qui lui est égale. Si on note \(r\) la position de \(x\) la plus à droite dans le motif, il s’agit donc d’utiliser un décalage de \(δ = j − r\) si cette quantité est strictement positive. À défaut, (c’est-à-dire si \(δ ⩽ 0\)) on se contentera d’un décalage d’une unité, comme dans l’algorithme naïf

Programmation de Boyer-Moore en Python

Il faut donc commencer par calculer un dictionnaire dont les clés sont les caractères du motif et les valeurs la position la plus à droite du caractère.
C’est ce que réalise la fonction calculeADroite(). Dans le cas du mot maman, par exemple, on exécute tour à tour des affectations

aDroite['m'] = 0
aDroite['a'] = 1
aDroite['m'] = 2
aDroite['a'] = 3
aDroite['n'] = 4

de sorte qu’à la fin de l’exécution, aDroite['m'] est bien égal à 2, position la plus à droite de la lettre 'm' dans le mot 'maman'. Cela dit, on voudrait calculer le décalage de la fenêtre même quand le caractère qui provoque l’échec n’apparaît pas dans le motif. Mais aDroite['Z'] par exemple n’existe pas et demander sa valeur déclenche une erreur d’exécution. C’est pourquoi on a écrit la fonction droite qui renvoie −1 si le caractère n’est pas dans le dictionnaire aDroite

def calculeADroite(motif, p):
    # remplit (partiellement) un dictionnaire pour donner les positions les plus à ↪ droite de chaque caractère
    global aDroite
    aDroite = {}
    for j in range(p):
        aDroite[motif[j]] = j
def droite(c):
    global aDroite
    # renvoie -1 si c n'est pas dans le motif ou sinon aDroite[c]
    if c in aDroite.keys():
        return aDroite[c]
    else:
        return -1

Remarque

On a utilisé une variable globale pour le dictionnaire aDroite. Ce n’est pas toujours une bonne pratique, mais elle semble ici raisonnable

Algorithme de Boyer-Moore de Recherche d'un motif dans un Texte
(mis en ligne par L. Abdal, d'après un travail de N. Reveret)

Aide

On pourra remarquer que :

• La comparaison commence par la fin du motif
• On a construit un tableau indiquant pour chaque caractère du motif sa dernière occurrence dans le motif
• Par rapport à une recherche naïve, on peut parfois décaler le motif de plusieurs emplacements

Remarque

L'algorithme présenté dans cette activité est une version simplifiée de l'algorithme de Boyer-Moore par Horspool. L'algorithme complet, plus complexe, n'est pas étudié en nsi. Le lecteur intéressé pourra consulter les ressources en ligne (par exemple la page wikipedia)

Algorithme Complet de Boyer-Moore

Nous n’avons présenté qu’une version simplifiée de l’algorithme complet. L’algorithme complet de Boyer-Moore utilise une deuxième table de décalage, beaucoup plus difficile à calculer, qui permet de tenir compte des caractéristiques du motif dans le cas où celui-ci présente des similarités internes, ce qui permet d’effectuer des décalages plus importants, donc d’augmenter l’efficacité de la recherche. L’algorithme complet de Boyer-Moore présente des difficultés en termes de justification et de programmation effective qui dépassent le niveau attendu en NSI. C’est pourquoi nous ne l’évoquons pas ici. Le lecteur curieux pourra lire les pages 360–366 de l’ouvrage de Berstel, Beauquier et Chrétienne, disponible en ligne :

• http://www-igm.univ-mlv.fr/~berstel/Elements/Elements.pdf

Références

Cette page est directement issue de Eduscol