Aller au contenu

TP - Algorithme simplifié de 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.

Rappel

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.

Téléchargez le fichier « à trous » TPE05.20.py (clic droit -> [Enregistrer la cible du lien sous]) et enregistrez-le dans le dossier [E05-Recherche_Textuelle].

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.

Exemple de tests
motif1 = 'witch'
texte1 = 'A witch which switch'

motif2 = 'scribe'
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…"""

motif3 = 'ment'
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."""

Enfin, pour vous aider à visulaiser la recherche, vous pouvez consulter ce site :
https://people.ok.ubc.ca/ylucet/DS/BoyerMoore.html.

Partie A - Pré-traitement du motif et décalage☘

  1. Dans l'optimisation de Horspool, le dictionnaire des « mauvais caractères » associe à chaque caractère du motif son indice « le plus à droite ».
    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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def bad_carac_horspool(motif):
    """
    motif - str, chaîne de caractères
    Sortie: dict - dictionnaire tel que :
                 - les clefs sont les caractères de motif
                 - les valeurs associées sont leur indice "le plus à droite" dans motif
            Le dernier caractère de motif n'est pas parcouru

    >>> motif = 'CAAGT'
    >>> bad_carac_horspool(motif)
    {'C': 0, 'A': 2, 'G': 3}
    """

    Exemple de tests

    >>> bad_carac_horspool(motif1)
{'w': 0, 'i': 1, 't': 2, 'c': 3}

>>> bad_carac_horspool(motif2)
{'s': 0, 'c': 1, 'r': 2, 'i': 3, 'b': 4}

>>> bad_carac_horspool(motif3)
{'m': 0, 'e': 1, 'n': 2}

  2. A 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 :

    • Ou bien texte[i+j] n’est pas dans le motif, alors on déplace la fenêtre à « droite » de ce caractère : la valeur du décalage est j+1.

    • Sinon, 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 \geqslant j et on décale la fenêtre de 1 comme pour l’algorithme naïf.

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].

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def decalage_horspool(motif, texte, i, j, bad_carac):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    i - int, position de la fenêtre telle que 0 <= i < len(texte)
    j - int, entier tel que 0 <= j < len(motif)
    bad_carac - dict, dictionnaire des mauvais caractères (Horspool)
    Sortie: int - décalage à appliquer à la fenêtre en cas de non correspondance
                    entre texte[i+j] et motif[j]

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> bad_carac = {'C': 0, 'A': 2, 'G': 3, 'T': 4}
    >>> decalage_horspool(motif, texte, 7, 2, bad_carac)
    1
    >>> decalage_horspool(motif, texte, 13, 4, bad_carac)
    4
    """

Exemple de tests

>>> bad_carac = bad_carac_horspool(motif1)
>>> decalage_horspool(motif1, texte1, 0, 4, bad_carac)
2
>>> decalage_horspool(motif1, texte1, 2, 4, bad_carac)
5
>>> decalage_horspool(motif1, texte1, 7, 4, bad_carac)
1
>>> decalage_horspool(motif1, texte1, 5, 3, bad_carac)
3

Partie B - Détecter la présence du motif☘

Sans utiliser l'opérateur in, et en programmant l'algorithme simplifié de Horspool, 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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
def est_present_horspool(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: bool - True si motif est dans texte, False sinon
            Recherche selon les principes de Horspool

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> est_present_horspool(motif, texte)
    True
    """

Exemple de tests

>>> est_present_horspool(motif1, texte1)
True

>>> est_present_horspool(motif2, texte2)
False

>>> est_present_horspool(motif3, texte3)
True
Une piste

J'espère que vous n'avez pas fait un simplie copier/coller du code de l'algorithme naïf. En effet, il ne faut pas oublier d'appliquer le premier principe développé par Horspool (cf. introduction de ce TP)...

Partie C - Positions et nombre d'occurrences☘

  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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def nb_occurrences_horspool(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: int - Nombre d'occurrences de motif dans texte
            Recherche selon les principes de Horspool

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> nb_occurrences_horspool(motif, texte)
    4
    """

    Exemple de tests

    >>> nb_occurrences_horspool(motif1, texte1)
2

>>> nb_occurrences_horspool(motif2, texte2)
0

>>> nb_occurrences_horspool(motif3, texte3)
3

  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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def positions_horspool(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: list - Tableau des positions où trouver motif dans texte

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> positions_horspool(motif, texte)
    [2, 8, 20, 30]
    """

    Exemple de tests

    >>> positions_horspool(motif1, texte1)
[2, 15]

>>> positions_horspool(motif2, texte2)
[]

>>> positions_horspool(motif3, texte3)
[21, 54, 1015]

Partie D - Nombre de comparaisons☘

  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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
    def nb_comparaisons_horspool(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: int - Nombre de comparaisons nécessaires pour
            déterminer les positions où trouver motif dans texte
            selon l'algorithme de recherche textuelle simplifié de Horspool

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> nb_comparaisons_horspool(motif, texte)
    32
    """

    Exemple de tests

    >>> len(motif1)
5
>>> len(texte1)
20
>>> nb_comparaisons_horspool(motif1, texte1)
17

>>> len(motif2)
6
>>> len(texte2)
1145
>>> nb_comparaisons_horspool(motif2, texte2)
238

>>> len(motif3)
4
>>> len(texte3)
1035
>>> nb_comparaisons_horspool(motif3, texte3)
334

  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.

  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
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
    def affichage_horspool(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: None - Affichage des alignements obtenus
            selon l'algorithme de recherche textuelle simplifié de Horspool

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> affichage_horspool(motif, texte)
    ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT
    CAAGT
      CAAGT
       CAAGT
           CAAGT
            CAAGT
             CAAGT
                 CAAGT
                     CAAGT
                       CAAGT
                        CAAGT
                         CAAGT
                             CAAGT
                              CAAGT
                                  CAAGT
    """

    Exemple de tests

    >>> affichage_horspool(motif1, texte1)
A witch which switch
witch
  witch
   witch
        witch
         witch
              witch
               witch