====== Recherche textuelle ====== [[https://fr.wikipedia.org/wiki/Algorithme_de_Boyer-Moore|Algorithme de Boyer - Moore sur Wikipedia]] Il s'agit d'un algorithme de recherche de sous-chaîne dans une chaîne de texte, développé en 1977 par Robert S. Boyer et Strother Moore. ===== Exemple d'utilisation ===== {{ :nsi:terminales:adn.png?direct&400 |}} L'ADN d'un individu peut être représentée par une longue suite de lettres A, G, T et C correspondant aux nucléotides formant le brin d'ADN. Il s'agit donc d'une très longue suite : CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGTTCCGAGAGATAGTGAAAGATGGCTGGGCTGTGAAGGGAAGGAGTCGTGAAAGCGCGAACACGAGTGTGCGCAAGCGCAGCGCCTTAGTATGCTCCAGTGTAGAAGCTCCGGCGTCCCGTCTAACCGTACGCTGTCCCCGGTACATGGAGCTAATAGGCTTTACTGCCCAATATGACCCCGCGCCGCGACAAAACAATAACAGTTTGCTGTATGTTCCATGGTGGCCAATCCGTCTCTTTTCGACAGCACGGCCAATTCTCCTAGGAAGCCAGCTCAATTTCAACGAAGTCGGCTGTTGAACAGCGAGGTATGGCGTCGGTGGCTCTATTAGTGGTGAGCGAATTGAAATTCGGTGGCCTTACTTGTACCACAGCGATCCCTTCCCACCATTCTTATGCGTCGTCTGTTACCTGGCTTGGCAT... Dans la cellule, cette chaîne est une sorte de programme indiquant quelles protéines la cellule doit fabriquer. Les protéines fabriquées conduisent ensuite au fonctionnement de la cellule et de l'organisme. On ne va pas entrer dans des détails de fonctionnement. Il est intéressant de remarquer qu'il y a 22 protéines pouvant être fabriquées, que le code ADN est comme un code de base 4 -- 4 symboles -- et qu'en base 4, avec 2 symboles on peut aller de 0 à 15 et avec 3 symboles on peut aller de 0 à 63. Il faut donc 3 symboles ADN pour représenter une protéine, avec 3 symboles on a même de la marge -- 64 valeurs possibles pour 22 protéines -- ce qui donne de la place pour une sorte de codage d'erreur ! C'est bien ce que l'on observe, les codons ADN sont des blocs de 3 lettres du code ADN. Ce qui nous intéresse ici, ce sera de trouver une occurrence d'une sous-chaîne. Par exemple, où trouver ''GTCTCT'' dans la chaîne précédente ? ===== Approche naïve ===== foin = "CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT" aiguille = "GTCTCT" La première idée est d'aligner les deux chaînes et de comparer. Si ça ne fonctionne pas, on décale l'aiguille. CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT GTCTCT -> non CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT GTCTCT -> non CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT GTCTCT -> non ... CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT GTCTCT -> oui Ici , ''foin'' a 78 caractères et ''aiguille'' en a 6. **À 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. ===== Amélioration 1 ===== L'idée de Boyer et Moore est de commencer à tester la position de ''aiguille'' en commençant par la droite et en évitant certaines positions dont on sait qu'elles ne fonctionneront pas. //Dans la suite, je mettrai parfois des ''[ ]'' pour indiquer quel caractère on observe.// CAAGC[G]CACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT GTCTC[T] Ci-dessus, la dernière lettre de ''aiguille'', T, n'est pas raccord avec le ''G''. Cette position de ''aiguille'' ne convient donc pas et il faut décaler ''aiguille'' d'au moins 1 position à droite. Mais on peut faire mieux. En ayant étudié ''aiguille'' au préalable, on sait que si on décale ''aiguille'' de 1 position, c'est un C qui se trouvera face au G quand on aura décalé de 1 (voir ci-dessous) CAAGC[G]CACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT GTCT[C]T -> décalage de 1. Le C se retrouve face au G. GTC[T]CT -> décalage de 2. GT[C]TCT -> décalage de 3. G[T]CTCT -> décalage de 4. aucun de ces décalages ne convient car il fallait aligner un G face au G ! Il est donc inutile de tester cette position. Si on a bien étudié ''aiguille'' au préalable, on sait même que la première occurrence de G dans ''aiguille'' -- en lisant par la droite -- se trouve en position 5. On sait donc que l'on peut directement décaler ''aiguille'' de 5 cases. CAAGC[G]CACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT [G]TCTCT -> décalage de 5 pour mettre les 2 G en face On a ainsi évité de tester 4 positions qui ne pouvaient pas fonctionner. 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) CAAGCGCACA[A]GACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT GTCTC[T] -> position de départ. T face à A, mais A pas dans aiguille GTCT[C]T -> décalage de 1 met un C face à A, on savait que ça n'irait pas GTC[T]CT -> décalage de 2 met un T face à A, idem GT[C]TCT -> décalage de 3 met un C face à A, idem G[T]CTCT -> décalage de 4 met un T face à A, idem [G]TCTCT -> décalage de 5 met un G face à A, idem Il faut produire une variable qui donne la première position de tous les caractères de ''aiguille''. **À 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. >>> bons("ACTGCGTACGCCATAA", "GAGTAC", 3) 4 >>> bons("ACTGCGTACGCCATAA", "GAGTAA", 3) 0 >>> bons("ACTGCGTACGCCATAA", "GCGTAC", 6) 1 - 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. >>> rangs("GAGTAG") {"A":1, "T": 2, "G":0} //''%%"C"%%'' étant absent de ''%%"GAGTAG"%%'' il n'apparaît pas dans la réponse, il faudra en tenir compte.// ==== Algorithme avec l'amélioration ==== Je résume l'idée sous forme d'un algorithme : Soit L la longueur de l'aiguille Analyser aiguille selon fonction précédente -> rangs régler le décalage à 0 A = dernier caractère de aiguille TANT QUE le décalage n'est pas trop grand FAIRE avec la fonction bons, compter n le nombre de bonnes lettres pour ce décalage SI n == taille de aiguille ALORS RENVOYER le décalage, c'est fini ! SINON SI n == 0 ALORS # C'est le cadre de l'amélioration 1 B = caractère de foin en vis à vis du dernier de aiguille SI B DANS les clés de rangs ALORS augmenter le décalage de la valeur de rangs[B] SINON augmenter le décalage de L FIN SINON # nous améliorerons ce cas plus tard augmenter le décalage de 1 FIN FIN # fini et pas trouvé... RENVOYER -1 **À 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++.// CAAGCGCACAAGACGCGGCAGACCTTCGTTATAGGCGATGATTTCGAACCTACTAGTGGGTCTCTTAGGCCGAGCGGT GTCTCT - Faites une implémentation en Python. Pour la séquence SI B DANS les clés de rangs ALORS augmenter le décalage de la valeur de rangs[B] SINON augmenter le décalage de L FIN 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. rangs.get(B, L) >>> r = {"A":1, "T": 2, "G":0} >>> r["A"] 1 >>> r["C"] KeyError 'C' >>> r.get("A", 6) 1 >>> r.get("C", 6) 6 ===== Amélioration 2 ===== 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 : abrrtsdfdfsggtbdu[bra]yuioabrauioikjd abracadobrada[bra] -> Les 3 premières coïncident mais pas la 4e On est arrivé à une position, on a trouvé un début de concordance -- toujours en lisant par la droite -- mais au 4e caractère, il y a une différence. Si on s'en tient à ce qui a été dit avant, on devrait dans ce cas abandonner cette position et décaler de 1. abrrtsdfdfsggtbd[u]brayuioabrauioikjd abracadobrad[a]bra -> à cause de cette différence, échec -> décalage de 1 abracadobra d abra Mais on aurait dû savoir que cette nouvelle position ne pouvait pas convenir car dans la position originale, on avait déjà constater la coïncidence de ''bra'' et on sait que la séquence ''bra'' revient plus loin dans ''aiguille'' : ''abracado[bra]da[bra]''. Au lieu de décaler de 1, on aurait pu décaler de 5 pour amener le second ''bra'' en face du vis-à-vis dans ''foin''. abrrtsdfdfsggtbdu[bra]yuioabrauioikjd abracadobrada[bra] -> échec à cause 4e lettre, mais [bra] déjà validé abracado[bra]dabra -> On peut sauter immédiatement à un décalage de 5 Dans l'étude préalable de ''aiguille'' on va donc pouvoir ajouter une analyse de ces situations. Exemple : ''aiguille = abracadabradobra''. J'ai positionné ''aiguille'' à une certaine position relativement à ''foin'' et j'ai trouvé, en partant de la droite, quelques lettres qui coïncident. Mais la coïncidence échoue à partir d'un caractère. Il faudra donc décaler ''aiguille'' pour essayer une autre position : ???????????????????????????x[a]??????????????????????? abracadobradabr[a] -> 1 identique abracadobrad[a]bra -> décalage de 3 pourrait convenir Le cas suivant est plus délicat : On a trouvé une concordance sur ''ra'' mais pas ''bra''. On souhaite donc trouver une autre occurrence de ''ra'' dans aiguille, mais sans ''b'' devant : ??????????????????????????x[ra]??????????????????????? abracadobradab[ra] -> 2 identiques abracadob[ra]dabra -> non ! ab[ra]cadobradabra -> non plus ! [ a]bracadobradabra -> là ça irait, 15 ?????????????????????????x[bra]??????????????????????? abracadobrada[bra] -> 3 identiques abracado[bra]dabra -> convient, décalage de 5 ????????????????????????x[abra]??????????????????????? abracadobrad[abra] -> 4 identiques [abra]cadobradabra -> 12 ???????????????????????x[dabra]??????????????????????? abracadobra[dabra] -> 5 identiques [ abra]cadobradabra -> 12 idem pour les autres. Ce faisant on définit une relation : ''1 -> 3, 2 -> 15, 3 -> 5'', etc. 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. 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''. ==== Fonctions intermédiaires ==== === Calcul de décalage === 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)%%'' 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''. exemple k = 5 ELLE EST BELLE TA POUBELLE -> suffixe = BELLE ; c = U BELLE -> suffixe sans c devant trouvé à 12 **Attention :** On accepte que ''suffixe'' déborde à gauche exemple k = 7 ELLE EST BELLE TA POUBELLE -> suffixe = OUBELLE ; c = P OUBELLE -> accepté -> 22 (déborde de 3 à gauche) === Algorithme suggéré === # on présuppose que 1 <= k < len(aiguille) L = len(aiguille) d = 1 # décalage vers la gauche qu'il faut donner à suffixe # pour trouver une concordance suffixe = k dernières lettres de aiguille c = caractère avant suffixe TANT QUE d < L FAIRE 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 caractère en vis à vis de c = caractère aiguille en m - 1 SINON caractère en vis à vis de c = rien FIN SI partie d'aiguille en vis à vis de suffixe égale à suffixe et caractère vis à vis de c différent de c ALORS renvoyer d # fini ! SINON d augmente de 1 FIN FIN RENVOYER L **À faire :** Faites l'implémentation de cette fonction ''%%k_to_shift(aiguille:str, k:int)->int%%'' === Constitution d'un 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(shifts) == len(aiguille)'' * ''shifts[0] = 0'' * ''%%shifts[k] = k_to_shift(aiguille, k)%%'' pour ''%%1 <= k < len(aiguille)%%'' **À faire :** Faites l'implémentation de cette fonction ''%%get_shifts_list(aiguille:str) -> list%%'' Vous pourrez vérifier que : >>> get_shifts_list('ELLE EST BELLE TA POUBELLE') [0, 3, 25, 25, 22, 12, 22, ..., 22] >>> get_shifts_list('GTCTCT') [0, 4, 6, 2, 6, 6, 6] ==== Amélioration du programme antérieur ==== soit L la longueur de l'aiguille Analyser aiguille selon fonction précédente -> rangs et shifts régler le décalage à 0 A = dernier caractère de aiguille TANT QUE le décalage n'est pas trop grand FAIRE avec la fonction bons, compter n le nombre de bonnes lettres pour ce décalage SI n == taille de aiguille ALORS RENVOYER le décalage, c'est fini ! SINON SI n == 0 ALORS # C'est le cadre de l'amélioration 1 B = caractère de foin en vis à vis du dernier de aiguille SI B DANS les clés de rangs ALORS augmenter le décalage de la valeur de rangs[B] SINON augmenter le décalage de L FIN SINON # voici l'amélioration 2 augmenter le décalage de shifts[n] FIN FIN # fini et pas trouvé... RENVOYER -1 **À faire :** Réalisez l'implémentation en Python.