Aller au contenu

Exercices d'entraînement☘

Ces exercices doivent être utilisés pour vous entraîner à programmer. Ils sont généralement accompagnés d'aide et de leur solution pour vous permettre de progresser.

Avant de vous précipiter sur ces solutions dès la première difficulté, n'oubliez pas les conseils suivants :

  • Avez-vous bien fait un schéma au brouillon pour visualiser le problème posé ?
  • Avez-vous essayé de rédiger un algorithme en français, avec vos propres mots, avant de vous lancer dans la programmation sur machine ?
  • Avez-vous utilisé des affichages intermédiaires, des print(), pour visualiser au fur et à mesure le contenu des variables ?
  • Avez-vous testé le programme avec les propositions de tests donnés dans l'exercice ?
  • Avez-vous testé le programme avec de nouveaux tests, différents de ceux proposés ?
Rappels
  • Chaque programme Python doit être sauvegardé sous forme de fichier texte avec l'extension .py.
    Enregistrez ce fichier dans le dossier [E05-Recherche_Textuelle] avec le nom donné à l'exercice : ProgE05.51.py, ProgE05.52.py, etc...
  • Pour exécuter ce programme, il suffit de le sauvegarder puis d'appuyer sur la touche [F5].
  • Le programme principal doit contenir un appel au module doctest : 
    ##----- Programme principal et tests -----##
if __name__ == '__main__':
    import doctest
    doctest.testmod()

ProgE05.51 - Tableau de dictionnaires des mauvais caractères☘

Dans cet exercice, on choisit d'optimiser le calcul du décalage en construisant un tableau de taille p (longueur du motif) contenant les p dictionnaires respectifs des mauvais caractères de la chaîne motif[0..j]. Chaque dictionnaire associe à chaque caractère de motif[0..j] son indice « le plus à droite » (dernier indice de la chaîne exclus).

  1. Copiez, collez et complétez la définition de la fonction bad_carac_tab_horspool() qui prend en paramètre une chaîne de caractère motif et qui renvoie un tableau des mauvais caractères de motif[0..j] pour chaque indice j, avec 0 ≤ j < len(motif), obtenus selon le principe énoncé plus haut.

    Rappel

    motif[0..j] est la chaîne constituée des caractères de motif de l'indice 0 (inclus) à l'indice j (exclus).

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
    def bad_carac_tab_horspool(motif):
    """
    motif - str, chaîne de caractères
    Sortie: list - tableau des dictionnaires tel que, pour chaque indice j :
                    - les clefs sont les caractères de motif[0..j]
                    - les valeurs associées sont leur indice "le plus à droite" dans motif[0..j]

    >>> motif = 'CAAGT'
    >>> bad_carac_tab_horspool(motif)
    [{}, {'C': 0}, {'C': 0, 'A': 1}, {'C': 0, 'A': 2}, {'C': 0, 'A': 2, 'G': 3}]
    """
    Exemples de tests
    >>> bad_carac_tab_horspool('witch')
[{},
 {'w': 0},
 {'w': 0, 'i': 1},
 {'w': 0, 'i': 1, 't': 2},
 {'w': 0, 'i': 1, 't': 2, 'c': 3}]

>>> bad_carac_tab_horspool('Horspool')
[{},
 {'H': 0},
 {'H': 0, 'o': 1},
 {'H': 0, 'o': 1, 'r': 2},
 {'H': 0, 'o': 1, 'r': 2, 's': 3},
 {'H': 0, 'o': 1, 'r': 2, 's': 3, 'p': 4},
 {'H': 0, 'o': 5, 'r': 2, 's': 3, 'p': 4},
 {'H': 0, 'o': 6, 'r': 2, 's': 3, 'p': 4}]

>>> bad_carac_tab_horspool('Boyer-Moore')
[{},
 {'B': 0},
 {'B': 0, 'o': 1},
 {'B': 0, 'o': 1, 'y': 2},
 {'B': 0, 'o': 1, 'y': 2, 'e': 3},
 {'B': 0, 'o': 1, 'y': 2, 'e': 3, 'r': 4},
 {'B': 0, 'o': 1, 'y': 2, 'e': 3, 'r': 4, '-': 5},
 {'B': 0, 'o': 1, 'y': 2, 'e': 3, 'r': 4, '-': 5, 'M': 6},
 {'B': 0, 'o': 7, 'y': 2, 'e': 3, 'r': 4, '-': 5, 'M': 6},
 {'B': 0, 'o': 8, 'y': 2, 'e': 3, 'r': 4, '-': 5, 'M': 6},
 {'B': 0, 'o': 8, 'y': 2, 'e': 3, 'r': 9, '-': 5, 'M': 6}]
    Une solution
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
    def bad_carac_tab_horspool(motif):
    """
    motif - str, chaîne de caractères
    Sortie: list - tableau des dictionnaires tel que, pour chaque indice j :
                    - les clefs sont les caractères de motif[0..j]
                    - les valeurs associées sont leur indice "le plus à droite" dans motif[0..j]

    >>> motif = 'CAAGT'
    >>> bad_carac_tab_horspool(motif)
    [{}, {'C': 0}, {'C': 0, 'A': 1}, {'C': 0, 'A': 2}, {'C': 0, 'A': 2, 'G': 3}]
    """
    tab = []
    for j in range(len(motif)):
        dico = {}
        for i in range(j):
            dico[motif[i]] = i
        tab.append(dico)
    return tab

  2. Justifiez qu'il n'est pas nécessaire de réaliser un dictionnaire des mauvais caractères pour le dernier caractère du motif si celui-ci n'est pas présent à un autre endroit du motif.

    Une solution

    Soit k l'indice du dernier caractère du motif.

    • Ou bien le caractère texte[i+k] correspond au dernier caractère du motif et il est inutile de faire appel au dictionnaire des mauvais caractères ;

    • Ou bien texte[i+k] ne correspond pas au dernier caractère.
      Alors on va chercher dans le dictionnaire des mauvais caractères la valeur associée à un autre caractère que motif[k].

    Dans les deux cas, il n'est pas utile de prendre en compte la position du caractère motif[k] dans le dictionnaire des mauvais caractères correspondant.

  3. Copiez, collez et complétez la définition de la fonction nb_occurrences_tab_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 en utilisant le tableau de dictionnaires renvoyé par la fonction bad_carac_tab_horspool() définie dans la question 1.

     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
    def nb_occurrences_tab_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_tab_horspool(motif, texte)
    4
    """
    Exemples de tests
    >>> motif1 = 'witch'
>>> texte1 = 'A witch which switch'
>>> nb_occurrences_tab_horspool(motif1, texte1)
2

>>> motif2 = 'CAACT'
>>> texte2 = 'TACCTCCAACTAGTCAACTAGACT'
>>> nb_occurrences_tab_horspool(motif2, texte2)
2
    Une piste

    Il ne faut pas hésiter à réutiliser la fonction decalage_horspool() définie dans le TP n°2.

    Une solution
     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
27
28
29
30
31
    def nb_occurrences_tab_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_tab_horspool(motif, texte)
    4
    """
    p = len(motif)
    n = len(texte)
    tab_bad_carac = bad_carac_tab_horspool(motif)
    i = 0
    compteur = 0
    while i <= n-p:
        j = p-1
        while j >= 0:
            if motif[j] != texte[i+j]:
                decalage = decalage_horspool(motif, texte, i, j, tab_bad_carac[j])
                j = -2
            else:
                j = j-1
        # On a parcouru tout le motif : il est présent dans texte
        if j == -1:
            compteur += 1
            decalage = p
        i += decalage
    return compteur

  4. Le but de cette question est de vérifier si l'utilisation d'un tableau de dictionnaires des mauvais caractères optimise la recherche réalisé par la version « simplifiée » de Horspool.

    1. Copiez, collez et complétez la définition de la fonction nb_comparaisons_tab_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 appliquer la recherche textuelle en utilisant le tableau de dictionnaires renvoyé par la fonction bad_carac_tab_horspool().

       1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
      def nb_comparaisons_tab_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_tab_horspool(motif, texte)
    27
    """

      Exemples de tests

      >>> motif1 = 'witch'
>>> texte1 = 'A witch which switch'
>>> nb_comparaisons_tab_horspool(motif1, texte1)
17

>>> motif2 = 'CAACT'
>>> texte2 = 'TACCTCCAACTAGTCAACTAGACT'
>>> nb_comparaisons_tab_horspool(motif2, texte2)
22
      Une solution

      Il est possible de recopier le code de la fonction nb_occurrences_tab_horspool() en insérant un compteur pour les comparaisons.

      La version proposée ci-dessous « expurge » le nombre d'occurrences et se concentre sur le nombre de comparaisons : 

       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
27
28
29
30
31
      def nb_comparaisons_tab_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_tab_horspool(motif, texte)
    27
    """
    p = len(motif)
    n = len(texte)
    tab_bad_carac = bad_carac_tab_horspool(motif)
    i = 0
    nb_comparaisons = 0
    while i <= n-p:
        j = p-1
        while j >= 0:
            nb_comparaisons += 1
            if motif[j] != texte[i+j]:
                decalage = decalage_horspool(motif, texte, i, j, tab_bad_carac[j])
                j = -2
            else:
                j = j-1
        if j == -1:
            decalage = p
        i += decalage
    return nb_comparaisons

    2. Comparez avec les résultats renvoyés par la fonction nb_comparaisons_horspool() définie dans le TP n°2.

      Une réponse

      L'application de la fonction nb_comparaisons_horspool() sur les tests précédents ne semble pas optimiser grand chose : 

      >>> motif1 = 'witch'
>>> texte1 = 'A witch which switch'
>>> nb_comparaisons_horspool(motif1, texte1)
17

>>> motif2 = 'CAACT'
>>> texte2 = 'TACCTCCAACTAGTCAACTAGACT'
>>> nb_comparaisons_horspool(motif2, texte2)
23

      Il faut un test mieux choisi pour gagner en efficacité. Par exemple (gain de 20%) : 

      >>> motif3 = 'TAACT'
>>> texte3 = 'TACCTCTAACTAGTTAACTAGACT'

>>> nb_comparaisons_horspool(motif3, texte3)
25

>>> nb_comparaisons_tab_horspool(motif2, texte2)
21

ProgE05.52 - Mauvais caractères par Boyer-Moore☘

Dans cet exercice, on établit le dictionnaire des mauvais caractères à partir de leur plus courte distance d à la fin du motif, cette distance étant strictement positive. Un caractère non présent dans le dictionnaire sera associé à la longueur du motif.
Le décalage est alors le maximum entre 1 et d+j+1–p, où p = len(motif).

Source : Wikipédia

Reprendre le déroulement du TP n°2 en mettant en place ce nouveau principe d'élaboration du dictionnaire des mauvais caractères. En d'autres termes :

  1. Définir la fonction bad_carac_boyer_moore() 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 petite distance (strictement positive) au dernier caractère du motif.

    Exemples de tests
    >>> bad_carac_boyer_moore('CAAGT')
{'C': 4, 'A': 2, 'G': 1}

>>> bad_carac_boyer_moore('witch')
{'w': 4, 'i': 3, 't': 2, 'c': 1}

>>> bad_carac_boyer_moore('Horspool')
{'H': 7, 'o': 1, 'r': 5, 's': 4, 'p': 3}

>>> bad_carac_boyer_moore('Boyer-Moore')
{'B': 10, 'o': 2, 'y': 8, 'e': 7, 'r': 1, '-': 5, 'M': 4}

  2. Définir la fonction decalage_boyer_moore() 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].

    Exemples de tests
    >>> motif = 'CAAGT'
>>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
>>> bad_carac = {'C': 4, 'A': 2, 'G': 1}
>>> decalage_boyer_moore(motif, texte, 5, 2, bad_carac)
3
>>> decalage_boyer_moore(motif, texte, 12, 4, bad_carac)
5

  3. Définir la fonction nb_occurrences_boyer_moore() 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 en appliquant la règle des mauvais caractères de Boyer-Moore.

    Exemples de tests
    >>> motif1 = 'witch'
>>> texte1 = 'A witch which switch'
>>> nb_occurrences_boyer_moore(motif1, texte1)
2

>>> motif2 = 'CAACT'
>>> texte2 = 'TACCTCCAACTAGTCAACTAGACT'
>>> nb_occurrences_boyer_moore(motif2, texte2)
2

  4. Définir la fonction nb_comparaisons_boyer_moore() 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 la règle des mauvais caractères de Boyer-Moore.

    Exemples de tests
    >>> motif1 = 'witch'
>>> texte1 = 'A witch which switch'
>>> nb_comparaisons_boyer_moore(motif1, texte1)
17

>>> motif2 = 'CAACT'
>>> texte2 = 'TACCTCCAACTAGTCAACTAGACT'
>>> nb_comparaisons_boyer_moore(motif2, texte2)
27

  5. Définir la fonction affichage_boyer_moore() 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 la règle des mauvais caractères de Boyer-Moore.

    Exemples de tests
    >>> motif1 = 'witch'
>>> texte1 = 'A witch which switch'
>>> affichage_boyer_moore(motif1, texte1)
A witch which switch
witch
  witch
   witch
        witch
         witch
              witch
               witch

>>> motif2 = 'CAACT'
>>> texte2 = 'TACCTCCAACTAGTCAACTAGACT'
>>> affichage_boyer_moore(motif2, texte2)
TACCTCCAACTAGTCAACTAGACT
CAACT
 CAACT
  CAACT
   CAACT
     CAACT
      CAACT
       CAACT
         CAACT
             CAACT
              CAACT
               CAACT
                 CAACT
                   CAACT

  6. Que peut-on déduire de ce qui précède ?

    Une réponse

    Il semble qu'utiliser le critère des mauvais caractères de Horspool et celui des mauvais caractères de Boyer-Moore revienne au même.
    Il reste à le prouver...

Solution - Le programme complet
  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
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
def bad_carac_boyer_moore(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 distance strictement positive
                    à la fin de motif

    >>> motif = 'CAAGT'
    >>> bad_carac_boyer_moore(motif)
    {'C': 4, 'A': 2, 'G': 1}
    """
    dico = {}
    for i in range(len(motif)-1):
        dico[motif[i]] = len(motif)-1-i
    return dico


def decalage_boyer_moore(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 (Boyer-Moore)
    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': 4, 'A': 2, 'G': 1}
    >>> decalage_boyer_moore(motif, texte, 5, 2, bad_carac)
    3
    >>> decalage_boyer_moore(motif, texte, 12, 4, bad_carac)
    5
    """
    p = len(motif)
    if texte[i+j] in bad_carac.keys():
        k = bad_carac[texte[i+j]]
    else:
        k = p
    decalage = max(1, k+j+1-p)
    return decalage



def nb_occurrences_boyer_moore(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 Boyer-Moore

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> nb_occurrences_boyer_moore(motif, texte)
    4
    """
    p = len(motif)
    n = len(texte)
    bad_carac = bad_carac_boyer_moore(motif)
    i = 0
    compteur = 0
    while i <= n-p:
        j = p-1
        while j >= 0:
            if motif[j] != texte[i+j]:
                decalage = decalage_boyer_moore(motif, texte, i, j, bad_carac)
                j = -2
            else:
                j = j-1

        if j == -1:     # On a parcouru tout le motif : il est présent dans texte
            compteur += 1
            decalage = 1
        i += decalage
    return compteur





def nb_comparaisons_boyer_moore(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
            en appliquant la règle des mauvais caractères de Boyer-Moore

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> nb_comparaisons_boyer_moore(motif, texte)
    32
    """
    p = len(motif)
    n = len(texte)
    bad_carac = bad_carac_boyer_moore(motif)
    i = 0
    nb_comparaisons = 0
    while i <= n-p:
        j = p-1
        while j >= 0:
            nb_comparaisons += 1
            if motif[j] != texte[i+j]:
                decalage = decalage_boyer_moore(motif, texte, i, j, bad_carac)
                j = -2
            else:
                j = j-1
        if j == -1:
            decalage = 1
        i += decalage
    return nb_comparaisons




def affichage_boyer_moore(motif, texte):
    """
    motif - str, chaîne de caractères
    texte - str, chaîne de caractères
    Sortie: None - Affichage des alignements obtenus
                en appliquant la règle des mauvais caractères de Boyer-Moore

    >>> motif = 'CAAGT'
    >>> texte = 'ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT'
    >>> affichage_boyer_moore(motif, texte)
    ATCAAGTTCAAGTCAGTCCCCAAGTTGATGCAAGT
    CAAGT
      CAAGT
       CAAGT
           CAAGT
            CAAGT
             CAAGT
                 CAAGT
                     CAAGT
                       CAAGT
                        CAAGT
                         CAAGT
                             CAAGT
                              CAAGT
                                  CAAGT
    """
    print(texte)
    print(motif)
    p = len(motif)
    n = len(texte)
    bad_carac = bad_carac_boyer_moore(motif)
    i = 0
    nb_comparaisons = 0
    while i <= n-p:
        j = p-1
        while j >= 0:
            nb_comparaisons += 1
            if motif[j] != texte[i+j]:
                decalage = decalage_boyer_moore(motif, texte, i, j, bad_carac)
                j = -2
            else:
                j = j-1
        if j == -1:
            decalage = 1
        i += decalage
        if i <= n-p:
            print(" "*i + motif)


if __name__ == '__main__':
    import doctest
    doctest.testmod()