[Diaporama] TNSI - Recherche textuelle

Recherche textuelle =================== *Ce document a été créé en collaboration avec ChatGPT (version 3.5), qui a été utilisé pour transposer le cours correspondant (accessible [ici](recherche-textuelle)) en un diaporama.* *Pour voir la conversation avec ChatGPT : [cliquer ici](https://chat.openai.com/share/0b2e8af5-7d02-46fd-a886-d6e526cbc050)* --- # Introduction ---- ## Introduction - En *algorithmique du texte*, l'un des grands problèmes est la **recherche de motif dans un texte**. - Rechercher le motif M dans un texte T = rechercher toutes les occurrences de M dans T. - **Exemple** : Si M = GCAG et T = GGCAGCCGAACCGCAGCAGCAC alors M apparaît 3 fois dans T, aux positions 1, 12 et 15 : GGCAGCCGAACCGCAGCAGCAC ---- ## Introduction - **Applications fréquentes** : - Recherche d'un mot dans un document (le célèbre CTRL+F) - Recherche d'un mot sur le Web par les moteurs de recherche - Recherche d'une sous-séquence d'intérêt dans une séquence biologique <img class="centre image-responsive" alt="i love ctrl+f" src="data/ctrl-f.jpg" width="180"> Crédits : <a href="https://flic.kr/p/7Qb6aM">Ahora estoy</a>, <a href="https://creativecommons.org/licenses/by-sa/2.0/">CC BY-SA 2.0</a>, Flickr ---- ## Introduction - **Notations et préconditions** : - m : taille du motif M - n : taille du texte T - On suppose que le motif est de "petite" taille par rapport à celle du texte : m est négligeable devant n. - La taille du texte peut être (très) grande ! Donc il faut trouver des algorithmes efficaces ! ---- ## Introduction - **Exemples** : - chercher M = algorithme dans le programme de NSI de Terminale : - n = 201 097 - m = 10 - on trouve 9 occurrences - chercher M = TTGACA (promoteur de gène) dans le chromosome 1 de l'humain : - n = 249 250 621 - m = 6 - on trouve plus de 1000 occurrences ---- ## Introduction - On verra : - que tous les algorithmes sont basés sur un recherche par **fenêtre glissante** - un **algorithme de recherche naïf** pour comprendre le principe - un algorithme plus efficace appelé **algorithme de Boyer-Moore-Horspool** (c'est une version simplifiée de Boyer-Moore publiée par Nigel Horspool) --- # Recherche par fenêtre glissante ---- ## Recherche par fenêtre glissante - Recherche par **fenêtre glissante** = technique utilisée par tous les algorithmes de recherche exacte de motif - Idée : - Positionner le motif M à différentes positions de T - Tester si M apparaît dans T pour chaque position i choisie - Décaler M et recommencer <pre style="font-size: 1.6rem;"> i 0 1 2 3 4 5 6 7 8 9 ... T = G G C A G C C G A A C C G C A G C A G C A C ✔️ ❌ ✔️ M G C A G --> G C A G --> G C A G --> ... </pre> ---- ## Recherche par fenêtre glissante - On notera : - `i` : la position dans `T` - `j` : la position dans `M` - Pour une position `i` donnée, on est dans la situation : ![schéma comparaison en position i](data/compa_pos_i.png) - `M` se trouve en position `i` dans `T` si : `M[0..m-1] = T[i..i+m-1]` - la dernière position à tester est `i = n - m` ---- ## Recherche par fenêtre glissante - Ce qui change d'un algo à l'autre : - la façon de décaler le motif - la façon de comparer `M[0..m-1]` et `T[i..i+m-1]` --- # Algorithme de recherche naïve ---- ## Algorithme de recherche naïve - Idée : tester si M apparaît dans T pour **chaque position** i de T - Recherche naïve : - Décalage : un cran à chaque fois - Comparaison : de la gauche vers la droite <pre style="font-size: 1.6rem;"> i 0 1 2 3 4 5 6 7 8 9 ... T G G C A G C C G A A C C G C A G C A G C A C M G C A G G C A G G C A G etc. </pre> ---- ## Méthode de comparaison ![schéma comparaison en position i](data/compa_pos_i.png) - Comparaison de M[0..m-1] et T[i..i+m-1] - On fait varier j de 0 à m-1 - On s'arrête dès qu'il n'y a pas de correspondance ---- ## Exemple <iframe width="800" height="260" frameborder="0" src="https://germainbecker.github.io/recherche-textuelle/iframe-embed.html?t=GGCAGCCGAACCGCAGCAGCAC&m=GCAG"></iframe> **Bilan** - On trouve le motif aux positions 1, 12 et 15 - 35 comparaisons ont été nécessaires Outil pour les animations accessible ici : https://germainbecker.github.io/recherche-textuelle/ ---- ### ✍️ À faire Exercice 1 ---- ## Coût de l'algorithme naïf - On compte le nombre de comparaisons - Pire cas : - T = `AAA..AAA` et M = `AA..A` - car le motif est trouvé à chaque position et donc la comparaison va "jusqu'au bout" à chaque position - Coût (pire cas) : - Il y a $n-m$ positions à tester - Pour chacune d'elles, il y a $m$ comparaisons - Donc **le coût dans le pire cas** de l'algorithme de recherche naïve est de l'ordre de $(n-m)\times m$. --- # Peut-on accélérer la recherche ? ---- ## Peut-on accélérer la recherche ? - Oui ! - Parfois, il est possible de faire un saut plus important que 1. - Exemple : motif M = `rap` dans le texte T = `rattraper` <pre style="font-size: 1.5rem"> i 0 1 2 3 4 5 6 7 8 9 ... T r a t t r a p e r M r a p </pre> - Le caractère fautif est le `t`, **qui *ne* se trouve *pas* dans le motif !** - Donc inutile de tester la position 1 et la position 2 - On peut passer directement à : <pre style="font-size: 1.5rem"> i 0 1 2 3 4 5 6 7 8 9 ... T r a t t r a p e r M r a p </pre> ---- ## Peut-on accélérer la recherche ? **Moralité** - Analyser au préalable le motif permet de faire des "sauts" plus importants - On parle de **prétraitement** du motif - Permet de mettre au point des algorithmes plus efficaces, comme l'algorithme de *Boyer-Moore* --- # Algorithme de Boyer-Moore-Horspool (BMH) --- ## Algorithme de BMH - L'algorithme de *Boyer-Moore* a été développé par Robert S. Boyer et J. Strother Moore en 1977. - C'est un algorithme souvent utilisé dans les éditeurs de texte, tel quel ou optimisé (le célèbre CTRL + F). >ℹ️ On ne présente ici que la version simplifiée de Boyer-Moore proposée par Nigel Horspool en 1980. ---- ## Algorithme de BMH #### Principe - La recherche se fait par fenêtre glissante : M "glisse" de gauche à droite le long de T - **mais** la comparaison M[0..m-1] vs T[i..i+m-1] se fait **de droite à gauche** - le décalage de M se fait de la façon suivante : - si le motif est trouvé, on décale le motif d'un cran - sinon, le décalage se calcule en fonction de ce qu'on appelle la **règle du mauvais caractère** ---- ## Règle du mauvais caractère - **si le premier caractère fautif de T *se trouve dans* le motif M** : - on l'aligne avec *son occurrence la plus à droite* dans la partie M[0..m-2] (on ne prend pas en compte le dernier caractère du motif) - sauf si celle-ci est déjà "passée", auquel cas on décale le motif d'un cran. - **si M ne contient pas le premier caractère fautif de T**, on décale le motif pour le positionner juste après la position fautive ---- ## Règle du mauvais caractère : exemples **1er cas** : le premier caractère fautif du texte *se trouve* dans le motif <pre style="font-size: 1.6rem;"> i 0 1 2 3 4 5 6 7 8 9 ... T A B G G R A T L M T G ... M T G T N A C j 0 1 2 3 4 5 --> T G T N A C (décalage : 3 crans) </pre> <pre style="font-size: 1.6rem;"> i 0 1 2 3 4 5 6 7 8 9 ... T A B G G A G C L M T G ... M T A G N A C L j 0 1 2 3 4 5 --> T A G N A C L (décalage : 4 - 2 = 2 crans) </pre> Alignement avec son occurrence la plus à droite ---- ## Règle du mauvais caractère : exemples **2ème cas** : le premier caractère fautif du texte *se trouve* dans le motif *mais* son occurrence la plus à droite est déjà "passée" <pre style="font-size: 1.6rem;"> i 0 1 2 3 4 5 6 7 8 9 ... T A B G G A G G L M T G ... M T A G N A G L j 0 1 2 3 4 5 --> T A G N A G L (décalage : 1 cran) </pre> Décalage d'un seul cran (on voit ici qu'on pourrait faire mieux mais ce n'est prévu par BMH) ---- ## Règle du mauvais caractère : exemples **3ème cas** : le premier caractère fautif du texte *ne se trouve pas* dans le motif <pre style="font-size: 1.6rem;"> i 0 1 2 3 4 5 6 7 8 9 ... T A B G G R A X L M T G ... M T G T N A C j 0 1 2 3 4 5 --> T G T N A C (décalage : len(M) = 6) </pre> <pre style="font-size: 1.6rem;"> i 0 1 2 3 4 5 6 7 8 9 ... T A B G G X A C L M T G ... M T G T N A C j 0 1 2 3 4 5 --> T G T N A C (décalage : len(M) - 2 = 4) </pre> ---- ## Exemple <iframe width="800" height="320" frameborder="0" src="https://germainbecker.github.io/recherche-textuelle/iframe-embed.html?r=bmh&t=GGCAGCCGAACCGCAGCAGCAC&m=GCAG"></iframe> **Bilan** - On trouve le motif aux positions 1, 12 et 15 - 25 comparaisons ont été nécessaires (contre 35 pour la recherche naïve) Outil pour les animations accessible ici : https://germainbecker.github.io/recherche-textuelle/ --- ## Prétraitement du motif M - Pour mettre en œuvre la règle du mauvais caractère : nécessaire de **prétraiter le motif**. - On construit un tableau associatif `MC` qui associe à chaque caractère `c` dans M[0..m-2], le nombre de positions à "remonter" dans M pour trouver `c` (inutile de s'occuper du dernier caractère) - Exemple : Pour M = GCAG, on obtient le tableau suivant : | `c` | A | C | G | | --- | --- | --- | --- | | `MC[c]` | 1 | 2 | 3 | ---- ## Prétraitement du motif M - En Python, `MC` pourra être implémenté par un dictionnaire : ```python {'A': 1, 'C': 2, 'G': 3} ``` - `MC` contient le **saut *maximal***, celui que l'on peut faire lorsque la comparaison échoue dès la première lettre. - Pour tout caractère absent dans M[0..m-2] : le décalage maximum est égal à la longueur du motif (4 dans cet exemple). - En pratique, pour calculer le décalage à appliquer, il ne faut pas oublier de retrancher le nombre de caractères qui ont "matchés" : $$\text{décalage} = \text{MC[c]} - \text{nb de caractères qui correspondent}$$ ---- ## Prétraitement du motif M ### Exemple Pour M = GCAG, on a : `MC = {'A': 1, 'C': 2, 'G': 3}` <pre style="font-size: 1.6rem;"> i 0 1 2 3 4 5 6 7 8 9 ... T G G C A G C C G A A C C G C A G C A G C A C M G C A G --> G C A G (décalage : 1) </pre> - Caractère fautif : `'C'` - Décalage maxi : `MC['C']` = 2 - Mais il y avait 1 correspondance (le `'G'` à droite) - Donc décalage à appliquer : 2 - 1 = 1 cran ---- ### ✍️ À faire Exercice 2 --- ## Performances de l'algorithme de BMH - L'étude du coût de l'algorithme de Boyer-Moore-Horspool n'est pas au programme. - Coût dans le pire cas : égal à celui de la recherche naïve (T = AAA..AAA et M = AA..A donc décalage de 1 à chaque fois) - Mais dans le cas moyen (et dans le meilleur cas), il se révèle très efficace car on peut obtenir de "plus grands" décalages assez souvent. - Le prétraitement du motif est coûteux (de quel ordre ?) mais rentable car cela permet ensuite de faire souvent des "grands" décalages. ---- ## Performances de l'algorithme de Boyer-Moore - L'algo de **Boyer-Moore** (tout court !) utilise une autre règle sur le *suffixe* du motif qui permet de faire des décalages plus intéressants encore (non abordé) - Comparaison des performances (réalisé par Ben Langmead (John Hopkins University, USA)) <img class="r-stretch centre image-responsive" src="data/compa_bm_naive.png" alt="comparaison efficacité Boyer-Moore vs recherche naïve"> --- # Bilan ---- ## Bilan - Les algorithmes de recherche textuelle sont très importants et souvent utilisés. - Ils utilisent la technique de **fenêtre glissante** pour tester la correspondance à diverses positions. - L'algorithme de **recherche naïve** teste la correspondance à **chaque** position en comparant les caractères de gauche à droite. - L'algorithme de **Boyer-Moore(-Horspool)** teste la correspondance **de droite à gauche** et est plus efficace *en moyenne* grâce à un **prétraitement du motif** qui permet de faire des sauts plus importants - Ce gain en temps est crucial pour les recherches dans de grands textes, comme en bio-informatique. --- ### Références - Document ressource de l'équipe éducative du DIU EIL de l'Université de Nantes, diffusé sous licence CC BY : [Recherche textuelle](data/diu2019_bloc5_séance4.pdf) (Bloc 5, Séance 4) - Livre *Spécialité Numérique et sciences informatiques : 24 leçons avec exercices corrigés - Terminale*, éditions Ellipses, T. Balabonski, S. Conchon, J.-C. Filliâtre, K. Nguyen. Site du livre : [http://www.nsi-terminale.fr/] --- Germain BECKER, Lycée Mounier, ANGERS Ressource éducative libre distribuée sous [Licence Creative Commons Attribution - Partage dans les Mêmes Conditions 4.0 International](http://creativecommons.org/licenses/by-sa/4.0/) ![Licence Creative Commons](https://i.creativecommons.org/l/by-sa/4.0/88x31.png)