GoupillWiki

Outils pour utilisateurs

Outils du site

Piste :
nsi:terminales:boyer_moore

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

Prochaine révision		Révision précédente
nsi:terminales:boyer_moore [2021/09/11 19:59] – créée goupillwikinsi:terminales:boyer_moore [2023/05/08 21:26] (Version actuelle) – [Fonctions intermédiaires] goupillwiki
Ligne 47: Ligne 47:
 </code> </code>
  
-Ici , ''foin'' a 78 caractères et ''aiguille'' en a 6. **Combien faut-il de tests dans le pire des cas ?**+Ici , ''foin'' a 78 caractères et ''aiguille'' en a 6.
  
-<WRAP tip>Le pire des cas est le cas où ''aiguille'' n'est pas contenu dans ''foin'' et qu'il faut donc aller jusqu'au bout.</WRAP>+<WRAP box>**À faire :** 
 +  - Combien faut-il de tests dans le pire des cas ?\\ //Le pire des cas est le cas où ''aiguille'' n'est pas contenu dans ''foin'' et qu'il faut donc aller jusqu'au bout.// 
 +  - Implémenter cette recherche naïve dans une fonction ''recherche_naive(foin:str, aiguille:str) -> int'' qui renvoie la position de la première apparition de ''aiguille'' dans ''foin'' si elle existe et ''-1'' sinon. 
 +</WRAP>
  
 ===== Amélioration 1 ===== ===== Amélioration 1 =====
Ligne 86: Ligne 89:
 Voyons la nouvelle position : Maintenant, le T final de ''aiguille'' est en face d'un A. Ça ne convient toujours pas. De plus, cette fois, on sait que A n'est pas dans ''aiguille''. On peut donc décaler complètement ''aiguille'' de 6 positions d'un coup, car toutes les positions intermédiaires ne conviennent pas (voir ci-dessous) Voyons la nouvelle position : Maintenant, le T final de ''aiguille'' est en face d'un A. Ça ne convient toujours pas. De plus, cette fois, on sait que A n'est pas dans ''aiguille''. On peut donc décaler complètement ''aiguille'' de 6 positions d'un coup, car toutes les positions intermédiaires ne conviennent pas (voir ci-dessous)
  
-</code lang-none>+<code lang-none>
 CAAGCGCACA[A]GACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT CAAGCGCACA[A]GACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT
      GTCTC[T] -> position de départ. T face à A, mais A pas dans aiguille      GTCTC[T] -> position de départ. T face à A, mais A pas dans aiguille
Ligne 98: Ligne 101:
 Il faut produire une variable qui donne la première position de tous les caractères de ''aiguille''. Il faut produire une variable qui donne la première position de tous les caractères de ''aiguille''.
  
-<WRAP box>**À faire :** Faites l'implémentation en Python d'une fonction ''rangs(aiguille)'' et renvoyant un résultat indiquant la première position en partant de la droite pour chaque lettre de ''aiguille''.</WRAP>+<WRAP box>**À faire :** 
 +  - Écrivez une fonction ''bons(foin:str, aiguille:str, shift:int) -> int'' qui pour un décalage (//shift//) donné, renvoie le nombre de caractères corrects comptés à partir de la droite.<code python> 
 +>>> bons("ACTGCGTACGCCATAA", "GAGTAC", 3) 
 +4 
 +>>> bons("ACTGCGTACGCCATAA", "GAGTAA", 3) 
 +0 
 +>>> bons("ACTGCGTACGCCATAA", "GCGTAC", 6) 
 +1 
 +</code> 
 +  - Faites l'implémentation en Python d'une fonction ''rangs(aiguille:str)'' et renvoyant un résultat indiquant la première position en partant de la droite pour chaque lettre de ''aiguille'' sous forme d'un dictionnaire.<code python> 
 +>>> rangs("GAGTAG") 
 +{"A":1, "T": 2, "G":0} 
 +</code>//''%%"C"%%'' étant absent de ''%%"GAGTAG"%%'' il n'apparaît pas dans la réponse, il faudra en tenir compte.// 
 +</WRAP> 
 + 
 +==== Algorithme avec l'amélioration ====
  
 Je résume l'idée sous forme d'un algorithme : Je résume l'idée sous forme d'un algorithme :
  
 <code lang-none> <code lang-none>
 +Soit L la longueur de l'aiguille
 Analyser aiguille selon fonction précédente -> rangs Analyser aiguille selon fonction précédente -> rangs
 régler le décalage à 0 régler le décalage à 0
 A = dernier caractère de aiguille A = dernier caractère de aiguille
 TANT QUE le décalage n'est pas trop grand FAIRE TANT QUE le décalage n'est pas trop grand FAIRE
-    B = caractère de foin en vis à vis du dernier de aiguille +    avec la fonction bons, compter n le nombre de bonnes lettres pour ce décalage 
-    SI A == B ALORS +    SI n == taille de aiguille ALORS 
-        POUR CHAQUE caractère de aiguille +        RENVOYER le décalage, c'est fini ! 
-            le comparer avec son vis à vis dans foin +    SINON SI n == 0 ALORS 
-            SI différents ALORS +        # C'est le cadre de l'amélioration 1 
-                augmenter décalage de 1 +        B = caractère de foin en vis à vis du dernier de aiguille 
-                interrompre la boucle +        SI B DANS les clés de rangs ALORS 
-            FIN +            augmenter le décalage de la valeur de rangs[B]
-            RENVOYER la valeur de décalage # fini et trouvé ! +
-        FIN +
-    SINON +
-        # c'est dans ce cas qu'agit l'amélioration 1 +
-        SI B est dans aiguille: +
-            augmenter décalage de la valeur de rangs correspondant à B+
         SINON         SINON
-            augmenter décalage de la longueur de l'aiguille+            augmenter le décalage de L
         FIN         FIN
 +    SINON 
 +        # nous améliorerons ce cas plus tard
 +        augmenter le décalage de 1
     FIN     FIN
 FIN FIN
 # fini et pas trouvé... # fini et pas trouvé...
-RENVOYER -1 # par exemple, ou False, ou None...+RENVOYER -1
 </code> </code>
  
-<WRAP box>**À faire :** appliquez cette méthode au cas déjà rencontré et évaluez le nombre de tests nécessaires pour aboutir au résultat. +<WRAP box>**À faire :** 
- +  - Appliquez cette méthode au cas déjà rencontré et évaluez le nombre de tests nécessaires pour aboutir au résultat.\\ //Pour faciliter le travail, vous pouvez faire un copier-coller dans un bon éditeur comme Sublime Text ou Notepad++.//<code lang-none>
-//Pour faciliter le travail, vous pouvez faire un copier-coller dans un bon éditeur comme Sublime Text ou Notepad++.// +
- +
-<code lang-none>+
 CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT
 GTCTCT GTCTCT
 </code> </code>
 +  - Faites une implémentation en Python.
 </WRAP> </WRAP>
  
-<WRAP box>Faites une implémentation en Python.</WRAP> +<WRAP tip> 
- +Pour la séquence 
-==== Faire un peu mieux ==== +<code lang-none> 
- +SI B DANS les clés de rangs ALORS 
-Dans l'algorithme, on doit tester souvent "si B est dans aiguille", ce qui va prendre du temps. On pourrait mieux faire en faisant en sorte que ''rangs'' tienne compte de toutes les lettres possibles, même celles non présentes dans ''aiguille'', en associant la valeur ''len(aiguille)'' aux lettres non présentes dans ''aiguille''. +    augmenter le décalage de la valeur de rangs[B] 
- +SINON 
-Il faudrait alors convenir dès le début d'un alphabet représentant les les lettres possibles. Dans le cas de l'ADN, l'alphabet se réduit à "AGTC" +    augmenter le décalage de L 
- +FIN 
-Une autre possibilité serait d'utiliser un dictionnaires pour le retour de ''rangs'' et d'utiliser la fonction ''get'' du dictionnaire :+</code> 
 +On peut grandement simplifier en utilisant la méthode ''get'' des ''dict''. La méthode ''get'' permet d'obtenir la valeur associée à une clé dans un dictionnaire et une valeur par défaut si la clé est absente. Le code suivant fait donc exactement ce que l'on veut. 
 +<code python> 
 +rangs.get(B, L) 
 +</code>
  
 <code python> <code python>
-r = rangs(aiguille) +>>> r = {"A":1, "T": 2, "G":0} 
-n = len(aiguille) +>>> r["A"] 
-... +1 
-k = r.get(B) +>>> r["C"] 
-if k == None: # B pas présent dans r +KeyError 'C' 
-    r[B] = n  # on l'ajoute pour la prochaine fois +>>> r.get("A", 6) 
-    k = n+1 
 +>>> r.get("C", 6) 
 +6
 </code> </code>
 +</WRAP>
  
 ===== Amélioration 2 ===== ===== Amélioration 2 =====
  
-L'amélioration ci-dessus permet de sauter des positions fausses et donc de gagner du temps, mais on peut mieux faire dans le cas où une concordance est trouvée.+L'amélioration ci-dessus n'accélère la recherche que si la première lettre (à droite) de l'aiguille ne coïncide pas. On voudrait pouvoir faire la même chose même dans les cas où on a trouvé quelques lettres coïncidentes.
  
 Prenons le cas suivant : Prenons le cas suivant :
Ligne 168: Ligne 189:
 <code lang-none> <code lang-none>
 abrrtsdfdfsggtbdu[bra]yuioabrauioikjd abrrtsdfdfsggtbdu[bra]yuioabrauioikjd
-    abracadobrada[bra] -> Les 3 premiers coïncident mais pas le 4e+    abracadobrada[bra] -> Les 3 premières coïncident mais pas la 4e
 </code> </code>
  
Ligne 227: Ligne 248:
 Ce faisant on définit une relation : ''1 -> 3, 2 -> 15, 3 -> 5'', etc. Ce faisant on définit une relation : ''1 -> 3, 2 -> 15, 3 -> 5'', etc.
  
-On peut le noter dans un tableau ''[0, 3, 15, 5, 12, 12, ..., 12]'' signifiant par exemple que pour une concordance de 3 caractères (mais pas 4), on peut décaler de 5.+On peut le noter dans un tableau ''T = [0, 3, 15, 5, 12, 12, ..., 12]'' signifiant par exemple que pour une concordance de 3 caractères (mais pas 4), on peut décaler de 5.
  
-=== Remarques ===+<WRAP tip> 
 +Le premier ''0'' du tableau n'est pas utilisé. On ne le met que pour éviter d'être ennuyé avec des calculs d'indices. Grâce à ce ''0'' on a bien ''T[1] == 3'', ''T[2] == 15''... Si on ne trouve aucune correspondance, on tombe dans la situation de l'amélioration 1. Si toutes les lettres correspondent, alors c'est fini car on a trouvé une occurrence de ''aiguille''. 
 +</WRAP>
  
-  * Le premier nombre sera toujours ''0''. Il n'est pas utile. +==== Fonctions intermédiaires ====
-  * Si aucune concordance n'est trouvée, la valeur par défaut est ''len(aiguille)''+
  
-==== Fonction intermédiaire ====+=== Calcul de décalage ===
  
-On souhaite implémenter une fonction ''k_to_shift(aiguille, k)'' qui construit le tableau précédent. Ce travail n'est pas simple et nous allons procéder par étape.+On souhaite implémenter une fonction ''%%k_to_shift(aiguille:str, k:int) -> int%%'' qui renvoie le décalage possible, selon la règle précédente, quand on a trouvé ''k'' caractères coïncidents.
  
-Considérant un mot ''aiguille'', et ''1 <= k < len(aiguille)''+Considérant un mot ''aiguille'', et ''%%1 <= k < len(aiguille)%%''
  
-Soit ''suffixe'' représentant les derniers caractères de ''aiguille'' et ''c'' le caractère juste avant ''suffixe'' dans ''aiguille''. Nous souhaitons trouver la première apparition (partant de la fin) de ''suffixe'' dans ''aiguille'', **non précédée** de ''c''.+Soit ''suffixe'' représentant les ''k'' derniers caractères de ''aiguille'' et ''c'' le caractère juste avant ''suffixe'' dans ''aiguille''. Nous souhaitons trouver la première apparition (partant de la fin) de ''suffixe'' dans ''aiguille'', **non précédée** de ''c''.
  
 <code lang-none> <code lang-none>
Ligne 260: Ligne 282:
 <code lang-none> <code lang-none>
 # on présuppose que 1 <= k < len(aiguille) # on présuppose que 1 <= k < len(aiguille)
-n = len(aiguille)+L = len(aiguille)
 d = 1 # décalage vers la gauche qu'il faut donner à suffixe d = 1 # décalage vers la gauche qu'il faut donner à suffixe
       # pour trouver une concordance       # pour trouver une concordance
 suffixe = k dernières lettres de aiguille suffixe = k dernières lettres de aiguille
 c = caractère avant suffixe c = caractère avant suffixe
-TANT QUE d < n: # d = n est cas pire si pas concordance FAIRE+TANT QUE d < L FAIRE
     m = rang du caractère face au début du suffixe     m = rang du caractère face au début du suffixe
 +        en tenant compte du décalage d vers la gauche
     SI m > 0 ALORS     SI m > 0 ALORS
         caractère en vis à vis de c = caractère aiguille en m - 1         caractère en vis à vis de c = caractère aiguille en m - 1
Ligne 279: Ligne 302:
     FIN     FIN
 FIN FIN
-RENVOYER d+RENVOYER L
 </code> </code>
  
-<WRAP box>**À faire :** Faites l'implémentation de cette fonction ''k_to_shift(aiguille, k)''</WRAP>+<WRAP box>**À faire :** Faites l'implémentation de cette fonction ''%%k_to_shift(aiguille:str, k:int)->int%%''</WRAP>
  
-==== Constitution d'un tableau ====+=== Constitution d'un tableau ===
  
-Le plus difficile est fait. On veut maintenant une fonction ''shifts(aiguille)'' qui produit le tableau mentionné précédemment. Notons ''s'' ce tableau.+Le plus difficile est fait. On veut maintenant une fonction ''%%get_shifts_list(aiguille:str) -> list%%'' qui produit le tableau mentionné précédemment. Notons ''shifts'' ce tableau.
  
-  * ''len(s) == len(aiguille)'' +  * ''len(shifts) == len(aiguille)'' 
-  * ''s[0] = 0'' +  * ''shifts[0] = 0'' 
-  * ''s[k] = k_to_shift(aiguille, k)'' pour ''1 <= k < len(aiguille)''+  * ''%%shifts[k] = k_to_shift(aiguille, k)%%'' pour ''%%1 <= k < len(aiguille)%%''
  
-<WRAP box>**À faire :** Faites l'implémentation de cette fonction ''shifts(aiguille)''</WRAP>+<WRAP box>**À faire :** Faites l'implémentation de cette fonction ''%%get_shifts_list(aiguille:str) -> list%%''</WRAP>
  
  
Ligne 298: Ligne 321:
  
 <code python> <code python>
-shifts('ELLE EST BELLE TA POUBELLE') == [0, 3, 25, 25, 22, 12, 22, ..., 22] +>>> get_shifts_list('ELLE EST BELLE TA POUBELLE') 
-shifts('GTCTCT') == [0, 4, 6, 2, 6, 6, 6]+[0, 3, 25, 25, 22, 12, 22, ..., 22] 
 +>>> get_shifts_list('GTCTCT') 
 +[0, 4, 6, 2, 6, 6, 6]
 </code> </code>
  
Ligne 305: Ligne 330:
  
 <code lang-none> <code lang-none>
 +soit L la longueur de l'aiguille
 Analyser aiguille selon fonction précédente -> rangs et shifts Analyser aiguille selon fonction précédente -> rangs et shifts
 régler le décalage à 0 régler le décalage à 0
 A = dernier caractère de aiguille A = dernier caractère de aiguille
 TANT QUE le décalage n'est pas trop grand FAIRE TANT QUE le décalage n'est pas trop grand FAIRE
-    B = caractère de foin en vis à vis du dernier de aiguille +    avec la fonction bons, compter n le nombre de bonnes lettres pour ce décalage 
-    SI A == B ALORS +    SI n == taille de aiguille ALORS 
-        # C'est ici que ça se passe +        RENVOYER le décalage, c'est fini ! 
-        corrects = 1 # caractères validés +    SINON SI n == 0 ALORS 
-        TANT QUE corrects < n FAIRE +        # C'est le cadre de l'amélioration 1 
-            comparaison du caractère du caractère suivant avec son vis à vis +        B = caractère de foin en vis à vis du dernier de aiguille 
-            SI identiques ALORS +        SI B DANS les clés de rangs ALORS 
-                corrects augmente de 1 +            augmenter le décalage de la valeur de rangs[B]
-            SINON +
-                interrompre boucle TANT QUE +
-            FIN +
-        FIN +
-        SI corrects == n ALORS +
-            renvoyer la valeur de décalage # (fini et trouvé !) +
-        FIN +
-        décalage augmente de shifts[corrects] +
-    SINON +
-        # c'est dans ce cas qu'agit l'amélioration 1 +
-        SI B est dans aiguille ALORS +
-            augmenter décalage de la valeur de rangs correspondant à B+
         SINON         SINON
-            augmenter décalage de la longueur de l'aiguille+            augmenter le décalage de L
         FIN         FIN
 +    SINON 
 +        # voici l'amélioration 2
 +        augmenter le décalage de shifts[n]
     FIN     FIN
 FIN FIN
-# pas trouvé... +# fini et pas trouvé... 
-renvoyer -1 # par exemple, ou False, ou None...+RENVOYER -1
 </code> </code>
  
 <WRAP box>**À faire :** Réalisez l'implémentation en Python.</WRAP> <WRAP box>**À faire :** Réalisez l'implémentation en Python.</WRAP>
nsi/terminales/boyer_moore.1631383143.txt.gz · Dernière modification : de goupillwiki