TP2 : Algorithme de Boyer-Moore-Horspool

Ce TP a pour but de vous faire programmer l'algorithme de recherche textuelle selon la méthode de Horspool, qui est une version simplifiée de l'algorithme de Boyer-Moore.

Voici les deux principes de l'algorithme proposé par Nigel Horspool pour optimiser l'algorithme naïf :

  1. Dans la fenêtre glissante, les caractères sont comparés de droite à gauche plutôt que de gauche à droite.

  2. En cas de non-correspondance, le décalage de la fenêtre va dépendre du caractère de texte. Ce principe s’appelle la règle du mauvais caractère.

L'idée est d'améliorer le code précédent (celui on parcourt le motif à l'envers) en sautant directement au prochain endroit potentiellement valide.

Pour cela on regarde le caractère X du texte sur lequel on s'est arrêté (car X n'était pas égal au caractère de rang équivalent dans le motif):

  • si X n'est pas dans le motif, il est inutile de se déplacer "de 1" : on retomberait tout de suite sur X, c'est du temps perdu. On se décale donc juste assez pour dépasser X, donc de la longueur du motif cherché.

  • si X est dans le motif (sauf à la dernière place du motif !), on va regarder la place de la dernière occurrence de X dans le motif et de déplacer de ce nombre, afin de faire coïncider le X du motif et le X du texte.

Voici une petite vidéo qui illustre cet algorithme :

Vidéo illustrant l'algorithme Boyer-Moore-Horspool
Informations[1]

Téléchargez le fichier python « à trous » ci-dessous (clic droit -> [Enregistrer la cible du lien sous]) et enregistrez-le dans votre dossier crée pour l'occasion.

TP2 Recherche Textuelle Boyer Moore Horspool [py]

Des exemples de tests sont proposés à partir des motifs et des textes ci-après. Il faudra ajouter vos propres tests dans le main de votre programme.

1
motif1 = 'witch'
2
texte1 = 'A witch which switch'
3
4
motif2 = 'scribe'
5
texte2 = """Vous savez, moi je ne crois pas qu’il y ait de bonne ou de mauvaise situation. Moi, si je devais résumer ma vie aujourd’hui avec vous, je dirais que c’est d’abord des rencontres. Des gens qui m’ont tendu la main, peut-être à un moment où je ne pouvais pas, où j’étais seul chez moi. Et c’est assez curieux de se dire que les hasards, les rencontres forgent une destinée… Parce que quand on a le goût de la chose, quand on a le goût de la chose bien faite, le beau geste, parfois on ne trouve pas l’interlocuteur en face je dirais, le miroir qui vous aide à avancer. Alors ça n’est pas mon cas, comme je disais là, puisque moi au contraire, j’ai pu : et je dis merci à la vie, je lui dis merci, je chante la vie, je danse la vie… je ne suis qu’amour ! Et finalement, quand beaucoup de gens aujourd’hui me disent « Mais comment fais-tu pour avoir cette humanité ? », et bien je leur réponds très simplement, je leur dis que c’est ce goût de l’amour ce goût donc qui m’a poussé aujourd’hui à entreprendre une construction mécanique, mais demain qui sait ? Peut-être simplement à me mettre au service de la communauté, à faire le don, le don de soi…"""
6
7
motif3 = 'ment'
8
texte3 = """Et d'abord, bourdonnement dans les oreilles, éblouissement dans les yeux. Au-dessus de nos têtes une double voûte en ogive, lambrissée en sculptures de bois, peinte d'azur, fleurdelysée en or; sous nos pieds, un pavé alternatif de marbre blanc et noir. À quelques pas de nous, un énorme pilier, véritable menhir, puis un autre, puis un autre; en tout sept piliers dans la longueur de la salle, soutenant au milieu de sa largeur les retombées de la double voûte. Autour des quatre premiers piliers, des boutiques de marchands, tout étincelantes de verre et de clinquants; autour des trois derniers, des bancs de bois de chêne, usés et polis par le haut-de-chausses des plaideurs et la robe des procureurs. À l'entour de la salle, le long de la haute muraille, entre les portes, entre les croisées, entre les piliers, l'interminable rangée des statues de tous les rois de France depuis Pharamond; les rois fainéants, les bras pendants et les yeux baissés; les rois vaillants et bataillards, la tête et les mains hardiment levées au ciel."""
9
Partie A : Pré-traitement du motif et décalage
Dans l'optimisation de Horspool, le dictionnaire des « mauvais caractères » associe à chaque caractère du motif son indice « le plus à droite ».
Question
Question A.1 :
Complétez la définition de la fonction bad_carac_horspool() qui prend en paramètre une chaîne de caractères (le motif) et qui renvoie un dictionnaire dont les clefs sont les différents caractères du motif associés à leur plus grand indice.
1
def bad_carac_horspool(motif):
2
    """
3
    motif - str, chaîne de caractères
4
    Sortie: dict - dictionnaire tel que :
5
                 - les clefs sont les caractères de motif
6
                 - les valeurs associées sont leur indice "le plus à droite" dans motif
7
            Le dernier caractère de motif n'est pas parcouru
8
9
    >>> motif = 'CAAGT'
10
    >>> bad_carac_horspool(motif)
11
    {'C': 0, 'A': 2, 'G': 3}
12
    """
13
1
>>> bad_carac_horspool(motif1)
2
{'w': 0, 'i': 1, 't': 2, 'c': 3}
3
4
>>> bad_carac_horspool(motif2)
5
{'s': 0, 'c': 1, 'r': 2, 'i': 3, 'b': 4}
6
7
>>> bad_carac_horspool(motif3)
8
{'m': 0, 'e': 1, 'n': 2}
9
Indice
Il faut donc créer un nouveau dictionnaire pour pouvoir le renvoyer.
Indice
On peut parcourir le motif et utiliser le dernier indice trouvé pour le caractère. Le cours sur les dictionnaires peut vous être utile !
Question
Question A.2 :
À partir du dictionnaire précédent, le décalage à réaliser en cas de non correspondance entre les caractères motif[j] et texte[i+j] est calculé de la manière suivante :
  • Si texte[i+j] est dans le motif (mais pas le dernier), on note k le plus grand indice de texte[i+j] dans le motif.
    • soit k < j et on décale la fenêtre de j–k pour « aligner » texte[i+j] ;
    • soit k ⩾ j et on décale la fenêtre de 1 comme pour l’algorithme naïf.
  • Sinon, on déplace la fenêtre à « droite » de ce caractère : la valeur du décalage est j+1.
Complétez la définition de la fonction decalage_horspool() qui prend en paramètres deux chaînes de caractères (le motif et le texte), deux entiers strictement positifs (les indices i et j) et un dictionnaire des mauvais caractères. Cette fonction renvoie le décalage entier à appliquer à la fenêtre en cas de non correspondance entre texte[i+j] et motif[j].
Bonus : peut-être avez-vous remarqué que la fonction se simplifie en simplement 2 return ?
1
def decalage_horspool(motif, texte, i, j, bad_carac):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    i - int, position de la fenêtre telle que 0 <= i < len(texte)
6
    j - int, entier tel que 0 <= j < len(motif)
7
    bad_carac - dict, dictionnaire des mauvais caractères (Horspool)
8
    Sortie: int - décalage à appliquer à la fenêtre en cas de non correspondance
9
                    entre texte[i+j] et motif[j]
10
11
    >>> motif = 'CAAGT'
12
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
13
    >>> bad_carac = {'C': 0, 'A': 2, 'G': 3, 'T': 4}
14
    >>> decalage_horspool(motif, texte, 7, 2, bad_carac)
15
    1
16
    >>> decalage_horspool(motif, texte, 13, 4, bad_carac)
17
    4
18
    """
19
1
>>> bad_carac = bad_carac_horspool(motif1)
2
>>> decalage_horspool(motif1, texte1, 0, 4, bad_carac)
3
2
4
>>> decalage_horspool(motif1, texte1, 2, 4, bad_carac)
5
5
6
>>> decalage_horspool(motif1, texte1, 7, 4, bad_carac)
7
1
8
>>> decalage_horspool(motif1, texte1, 5, 3, bad_carac)
9
3
10
Indice
Pas de grosses difficultés, il suffit de lire la question avec attention.
Indice
Pour comparer le caractère texte[i+j], on peut utiliser le dictionnaire des mauvais caractères, mais uniquement sur les clés ; cela exclut de fait le dernier caractère.
Indice
Le code a compléter peut être le suivant :
1
def decalage_horspool(motif, texte, i, j, bad_carac):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    i - int, position de la fenêtre telle que 0 <= i < len(texte)
6
    j - int, entier tel que 0 <= j < len(motif)
7
    bad_carac - dict, dictionnaire des mauvais caractères (Horspool)
8
    Sortie: int - décalage à appliquer à la fenêtre en cas de non correspondance
9
                    entre texte[i+j] et motif[j]
10
    
11
    >>> motif = 'CAAGT'
12
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
13
    >>> bad_carac = {'C': 0, 'A': 2, 'G': 3, 'T': 4}
14
    >>> decalage_horspool(motif, texte, 7, 2, bad_carac)
15
    1
16
    >>> decalage_horspool(motif, texte, 13, 4, bad_carac)
17
    4
18
    """
19
    if texte[i+j] in ...:  		#on parcourt les clés du dico (de fait, on exclut le dernier)
20
        k = ...
21
        if k >= j:
22
            return ...
23
        else:
24
            return ...
25
    else:
26
        return ...
Indice
Pour le bonus, la fonction max() peut être utilisée.
Solution
Solution de simplification avec la fonction max
1
        if k >= j:
2
            return 1
3
        else:
4
            return j-k
5
    else:
6
        return j+1
Le code précédent se simplifie en
1
        decalage = max(1, j-k)
2
    else:
3
        decalage = j+1
4
    return decalage
Partie B - Détecter la présence du motif
Sans utiliser l'opérateur in, on vous demande dans cette partie de programmer l'algorithme simplifié de Horspool.
Il ne s'agit pas d'un simple copier / coller de l'algorithme naïf puisqu'il ne faut pas oublier d'appliquer le premier principe développé par Horspool, principe développé en introduction de ce travail pratique. On aura donc besoin d'utiliser les 2 fonctions précédentes...
Question
Question B.1 :
Complétez la définition de la fonction est_present_horspool() qui prend en paramètres deux chaînes de caractères motif et texte. Cette fonction renvoie True si la chaîne motif est présente dans la chaîne texte, elle renvoie False sinon.
1
def est_present_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: bool - True si motif est dans texte, False sinon
6
            Recherche selon les principes de Horspool
7
8
    >>> motif = 'CAAGT'
9
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
10
    >>> est_present_horspool(motif, texte)
11
    True
12
    """
13
1
>>> est_present_horspool(motif1, texte1)
2
True
3
4
>>> est_present_horspool(motif2, texte2)
5
False
6
7
>>> est_present_horspool(motif3, texte3)
8
True
9
Indice
1
j étant notre indice sur le motif, on pourrait disposer du pseudo-code suivant pour nous aider avec les optimisations d'Horspool.
2
3
j est fixé à la longueur du motif - 1
4
tant que j est supérieur ou égal à 0
5
	s'il n'y pas correspondance
6
		on se décale du décalage prévu
7
		on sort de la boucle tant que
8
	sinon
9
		je me décale de -1
10
si j est égal à -1
11
	j'ai parcouru tout le motif et il est présent \o/
12
sinon
13
	je décale i de décalage
14
Indice
1
def est_present_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: bool - True si motif est dans texte, False sinon
6
            Recherche selon les principes de Horspool
7
    
8
    >>> motif = 'CAAGT'
9
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
10
    >>> est_present_horspool(motif, texte)
11
    True
12
    """
13
    p = len(motif)
14
    n = len(texte)
15
    bad_carac = bad_carac_horspool(...)
16
    i = 0
17
    while i <= n-p:
18
        j = p-1
19
        while j >= 0:
20
            if motif[j] ... texte[i+j]:
21
                decalage = ...
22
                j = -2
23
            else:
24
                j = j-1
25
        
26
        if j == -1:     # On a parcouru tout le motif : il est présent dans texte
27
            return True
28
        else:
29
            i += ...
30
    return False
Partie C - Positions et nombre d'occurrences
Comme dans l'algorithme naïf, on s'intéresse à présent aux positions et au nombre d’occurrences du motif.
Attention, à bien prendre en compte le fait que si l'on cherche 'toto' dans le texte 'totototototototo', il ne faut pas trop se décaler...
Question
Question C.1 :
Copiez/collez et modifiez le code réalisé dans la partie précédente pour programmer le corps de la fonction nb_occurrences_horspool() qui prend en paramètres deux chaînes de caractères motif et texte. Cette fonction renvoie le nombre d'occurrences de la chaîne motif dans la chaîne texte, elle renvoie 0 si motif n'est pas présent dans texte.
1
def nb_occurrences_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: int - Nombre d'occurrences de motif dans texte
6
            Recherche selon les principes de Horspool
7
8
    >>> motif = 'CAAGT'
9
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
10
    >>> nb_occurrences_horspool(motif, texte)
11
    4
12
    """
13
1
>>> nb_occurrences_horspool(motif1, texte1)
2
2
3
4
>>> nb_occurrences_horspool(motif2, texte2)
5
0
6
7
>>> nb_occurrences_horspool(motif3, texte3)
8
3
9
Indice
Ne pas s'arrêter au premier motif trouvé, il faut continuer à chercher en utilisant decalage...
Indice
1
def nb_occurrences_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: int - Nombre d'occurrences de motif dans texte
6
            Recherche selon les principes de Horspool
7
    
8
    >>> motif = 'CAAGT'
9
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
10
    >>> nb_occurrences_horspool(motif, texte)
11
    4
12
    """
13
    p = len(motif)
14
    n = len(texte)
15
    bad_carac = bad_carac_horspool(motif)
16
    i = 0
17
    ...
18
    while i <= n-p:
19
        j = p-1
20
        while j >= 0:
21
            if motif[j] != texte[i+j]:
22
                decalage = ...
23
                j = -2
24
            else:
25
                j = j-1
26
        
27
        if j == -1:     # On a parcouru tout le motif : il est présent dans texte
28
            ...
29
            decalage = 1
30
        i += decalage
31
    return ...
Question
Question C.2 :
Copiez / collez et modifiez le code réalisé dans la fonction précédente pour programmer le corps de la fonction positions_horspool() qui prend en paramètres deux chaînes de caractères motif et texte. Cette fonction renvoie le tableau (éventuellement vide) des positions de la chaîne motif dans la chaîne texte.
1
def positions_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: list - Tableau des positions où trouver motif dans texte
6
7
    >>> motif = 'CAAGT'
8
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
9
    >>> positions_horspool(motif, texte)
10
    [2, 8, 20, 30]
11
    """
12
1
>>> positions_horspool(motif1, texte1)
2
[2, 15]
3
4
>>> positions_horspool(motif2, texte2)
5
[]
6
7
>>> positions_horspool(motif3, texte3)
8
[21, 54, 1015]
9
Indice
1
def positions_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: list - Tableau des positions où trouver motif dans texte
6
    
7
    >>> motif = 'CAAGT'
8
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
9
    >>> positions_horspool(motif, texte)
10
    [2, 8, 20, 30]
11
    """
12
    p = len(motif)
13
    n = len(texte)
14
    bad_carac = ...
15
    i = 0
16
    ...
17
    while i <= n-p:
18
        j = p-1
19
        while j >= 0:
20
            if motif[j] ... texte[i+j]:
21
                decalage = ...
22
                j = -2
23
            else:
24
                j = j-1
25
        
26
        if j == -1:     # On a parcouru tout le motif : il est présent dans texte
27
            ...
28
            decalage = 1
29
        i += ...
30
    return ...
Partie D - Nombre de comparaisons
À priori, avec les optimisations d'Horspool, on s'attend à que le nombre de comparaisons soit en baisse. Vérifions cela !
Question
Question D.1 :
Complétez la définition de la fonction nb_comparaisons_horspool() qui prend en paramètres deux chaînes de caractères motif et texte.
Cette fonction renvoie le nombre de comparaisons effectuées pour déterminer (par exemple) les positions de la chaîne motif dans la chaîne texte en appliquant l'algorithme simplifié de Horspool de recherche textuelle.
1
def nb_comparaisons_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: int - Nombre de comparaisons nécessaires pour
6
            déterminer les positions où trouver motif dans texte
7
            selon l'algorithme de recherche textuelle simplifié de Horspool
8
9
    >>> motif = 'CAAGT'
10
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
11
    >>> nb_comparaisons_horspool(motif, texte)
12
    32
13
    """
14
1
>>> len(motif1)
2
5
3
>>> len(texte1)
4
20
5
>>> nb_comparaisons_horspool(motif1, texte1)
6
17
7
8
>>> len(motif2)
9
6
10
>>> len(texte2)
11
1145
12
>>> nb_comparaisons_horspool(motif2, texte2)
13
238
14
15
>>> len(motif3)
16
4
17
>>> len(texte3)
18
1035
19
>>> nb_comparaisons_horspool(motif3, texte3)
20
334
21
Indice
1
def nb_comparaisons_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: int - Nombre de comparaisons nécessaires pour
6
            déterminer les positions où trouver motif dans texte
7
            selon l'algorithme de recherche textuelle simplifié de Horspool
8
    
9
    >>> motif = 'CAAGT'
10
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
11
    >>> nb_comparaisons_horspool(motif, texte)
12
    32
13
    """
14
    p = len(motif)
15
    n = len(texte)
16
    bad_carac = ...
17
    i = 0
18
    ...
19
    while i <= n-p:
20
        j = p-1
21
        while j >= 0:
22
            ...
23
            if motif[j] ... texte[i+j]:
24
                decalage = ...
25
                j = -2
26
            else:
27
                j = j-1
28
        if j == -1:
29
            decalage = 1
30
        i += ...
31
    return ...
Question
Question D.2 :
Comparez ces résultats avec ceux obtenus dans le TP précédent.
Cette optimisation semble-t-elle efficace ? Conjecturez un ordre de grandeur du coût en fonction de n et p, où n est la longueur du texte et p est la longueur du motif.
Vous pouvez répondre directement dans votre fichier Python, sous forme de commentaire ou ailleurs.
Question
Question D.3 :
Complétez la définition de la fonction affichage_horspool() qui prend en paramètres deux chaînes de caractères motif et texte.
Cette fonction affiche dans la console la recherche des positions de la chaîne motif dans la chaîne texte en appliquant l'algorithme simplifié de Horspool de recherche textuelle.
1
def affichage_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: None - Affichage des alignements obtenus
6
            selon l'algorithme de recherche textuelle simplifié de Horspool
7
8
    >>> motif = 'CAAGT'
9
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
10
    >>> affichage_horspool(motif, texte)
11
    ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT
12
    CAAGT
13
      CAAGT
14
       CAAGT
15
           CAAGT
16
            CAAGT
17
             CAAGT
18
                 CAAGT
19
                     CAAGT
20
                       CAAGT
21
                        CAAGT
22
                         CAAGT
23
                             CAAGT
24
                              CAAGT
25
                                  CAAGT
26
    """
27
1
>>> affichage_horspool(motif1, texte1)
2
A witch which switch
3
witch
4
  witch
5
   witch
6
        witch
7
         witch
8
              witch
9
               witch
Indice
Il suffit simplement de rajouter des espaces sous forme de chaîne de caractères...
Indice
1
def affichage_horspool(motif, texte):
2
    """
3
    motif - str, chaîne de caractères
4
    texte - str, chaîne de caractères
5
    Sortie: None - Affichage des alignements obtenus
6
            selon l'algorithme de recherche textuelle simplifié de Horspool
7
    
8
    >>> motif = 'CAAGT'
9
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
10
    >>> affichage_horspool(motif, texte)
11
    ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT
12
    CAAGT
13
      CAAGT
14
       CAAGT
15
           CAAGT
16
            CAAGT
17
             CAAGT
18
                 CAAGT
19
                     CAAGT
20
                       CAAGT
21
                        CAAGT
22
                         CAAGT
23
                             CAAGT
24
                              CAAGT
25
                                  CAAGT
26
    """
27
    print(texte)
28
    print(motif)
29
    p = len(motif)
30
    n = len(texte)
31
    bad_carac = ...
32
    i = 0
33
    nb_comparaisons = 0
34
    while i <= n-p:
35
        j = p-1
36
        while j >= 0:
37
            nb_comparaisons += 1
38
            if motif[j] ... texte[i+j]:
39
                decalage = ...
40
                j = -2
41
            else:
42
                j = j-1
43
        if j == -1:
44
            decalage = 1
45
        i += decalage
46
        if i <= ...:
47
            print(... + motif)
Temps de recherche...
Reprendre les mesures effectuées sur le roman Les Misérables (mot court, phrase du roman et mot qui n'existe pas), mais cette fois avec l'algorithme optimisé de Horspool. Que remarquez-vous ?