Algo Recherche Textuelle

Identification

Infoforall

29 - Recherche textuelle


Vous avez souvenir d'une anecodote sympa sur Turing et vous voudriez la retrouver. Le problème est qu'elle est quelque part dans une série de 23 tomes de 600 pages sur l'histoire de l'informatique...

Vous n'avez pas envi de les relire un par un.

Et si nous cherchions un moyen efficace de faire une telle recherche !

Evaluation ✎ : -

Documents de cours : open document ou pdf

1 - Le principe de la recherche

La recherche dans une séquence dans un texte de grande taille est une opération très courante :

  • Recherche d'une séquence de mots dans des pages Web (exemple : c'est le principe de base d'une recherche sur les moteurs de recherche)
  • Recherche d'une séquence dans un pdf (exemple : trouver l'endroit où on parle de "Turing")
  • Recherche d'une séquence ADN (pour trouver une séquence précise dans l'ADN de quelqu'un)
  • Recherche d'une séquence dans un script Python (exemple : pour changer tous les variables nommées points_de_vie en pdv.

Python intègre un mot clé et des méthodes permettant de faire cela automatiquement bien entendu.

Le plus simple : le mot-clé in qui va nous permettre de créer une expression booléenne et ainsi répondre au problème (décidable) suivant : une séquence ou un motif m est-il présent dans un texte t :

>>> t = "En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché" >>> m = "tat" >>> m in t True

C'est le même in que celui qui permet de créer des boucles bien entendu.

  • Boucle bornée sur un ensemble d'entiers :
  • for x in range(3):

  • Boucle bornée sur les éléments d'un contenu itérable :
  • for note in notes:

Principe de la fonction rechercher

Nous voudrions réaliser une fonction rechercher(motif, texte).

Cette fonction doit renvoyer un tableau contenant l'indice de départ des motifs qu'on pourrait trouver dans le texte.

Exemples :

diz. 0000000000111111111122222222223333333333444444444455555555556666666666 unité i 0123456789012345678901234567890123456789012345678901234567890123456789 >>> t = "En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché" >>> m = "tat" >>> rechercher(m, t) [51]
diz. 0000000000111111111122222222223333333333444444444455555555556666666666 unité i 0123456789012345678901234567890123456789012345678901234567890123456789 >>> t = "En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché" >>> m = "ta" >>> rechercher(m, t) [13, 29, 51, 53]
diz. 0000000000111111111122222222223333333333444444444455555555556666666666 unité i 0123456789012345678901234567890123456789012345678901234567890123456789 >>> t = "En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché" >>> m = "nsi" >>> rechercher(m, t) []

Commençons par voir comment nous pourrions faire une recherche naïve.

Notons :

  • k le nombre de caractères dans le motif m recherché
  • n le nombre de caractères dans le texte t
  • On cherche si le premier caractère t[0])du texte correspond bien au premier caractère m[0] du motif.
  • On utilise un pointeur p pour connaître la lettre recherchée dans le motif. Ici p vaut 0 car on cherche le premier caractère du motif.


    p m t
    012 tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché
  • Comme t[0] vaut E, cela ne correspond pas au première caractère du motif, m. De manière naïve, on va donc décaler d'une case.

  • p m t
    012 tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché
  • Comme t[1] vaut n, cela ne correspond pas au première caractère m[0]) du motif, m. On décale d'une case.

  • p m t
    -▹012 -▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché
  • Comme t[2] vaut  , cela ne correspond pas au première caractère du motif, m. On décale d'une case.

  • p m t
    --▹012 --▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché

On voit bien qu'on va avoir un nombre de comparaisons à faire de l'ordre du nombre de caractères n de la chaîne t.

Pour l'instant, nous ne sommes tombés que sur des séquences où le premier caractère n'était déjà pas le bon. Mais, on peut tomber sur des séquences où le premier caractère est le bon, le deuxième aussi mais pas le troisième :

p m t
------------▹012 ------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché
p m t
------------▹012 ------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché
p m t
------------▹012 ------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché

Si un bout du texte t ressemble au motif et que la seule différence est sur le dernier caractère, il va donc falloir faire un nombre de comparaisons correspondant au nombre de caractères k dans le motif m.

Avec cette recherche naïve, on va donc avoir une complexité de l'ordre de 𝞗(k*n) dans le pire des cas. Par exemple :

p m t
01234567 aaaaaaah aaaaaaaaaaaaaaaaaaaaaaa

On passerait ensuite au caractère suivant :

p m t
01234567 aaaaaaah aaaaaaaaaaaaaaaaaaaaaaa

Puis au caractère suivant :

p m t
01234567 aaaaaaah aaaaaaaaaaaaaaaaaaaaaaa

On voit donc qu'il faut 8 comparaisons (la longueur du motif) pour savoir si le motif est possiblement présent dès la position 0.

p m t
01234567 aaaaaaah aaaaaaaaaaaaaaaaaaaaaaa

C'est un cas extrême bien entendu puisqu'il s'agit... du pire des cas.

On peut faire un peu mieux. A partir du moment où on dépasse un décalage de n-k inutile de continuer puisque les caractères restants ne sont plus assez nombreux pour correspondre avec le motif. On obtient 𝞗(k*(n-k))

On voit ainsi sur cet exemple qu'il est inutile de lancer la recherche puisque le dernier caractère ne pourra pas correspondre de toutes manières :

p m t
---------------▹01234567 ---------------▹aaaaaaah aaaaaaaaaaaaaaaaaaaaaaa

Si la longueur k du motif est bien plus petite que la longueur n du texte, on peut considérer que (n-k) est presque identifique à n et ... on retrouve 𝞗(k*n) !.

Et dans le meilleur des cas ?

C'est quand la sous-séquence apparaît immédiatement. On a alors une lecture linéaire sur le nombre de caractères k du motif.

p m t
01234567 aaaaaaah aaaaaaahaaaaaaaaaaaaaaa

Si on résume :

  • Meilleur des cas avec un motif présent dès le départ : Linéaire en k donc 𝞗(k).
  • Meilleur des cas avec un motif inconnu : Linéaire en n-k donc 𝞗(n-k). Cela donne un coût linéaire en 𝞗(n) si le texte est beaucoup plus long que le motif.
  • Pire des cas : Linéaire en n*k donc 𝞗(n*k).
  • Pour un cas quelconque, on peut donc juste écrire 𝞞(n*k).

2 - Algorithme de Boyer-Moore

Il existe de nombreux algorithmes permettant de réaliser une recherche moins naïve d'un motif dans un texte.

Nous allons voir l'algorithme de Boyer-Moore qui va nous permettre de gagner beaucoup de comparaisons la plupart du temps.

Nous ne verrons qu'une version simplifiée de cet algorithme, la version Boyer-Moore-Horspool.

Premier principe : commencer par la fin du motif

Le premier principe général qui va nous permettre de gagner du temps est de chercher d'abord une correspondance avec le dernier caractère du motif.

On crée une variable p (comme pointeur) mémorisant la case du motif qui nous intéresse. On départ p pointe donc sur la dernière case du motif. Si on note k le nombre de caractères du motif, on a donc p = k-1.
Au départ, nous obtenons donc p = 2.

p m i
012 --⇩ tat 01234567890123456789012345678901234567890123456789

On crée une variable d (comme décalage) mémorisant le nombre de cases dont on décale le motif sur le texte.
Au départ, d = 0.

d p m t i
0 012 --⇩ tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On regarde le caractère t[d+p]. Or t[2] est un espace. On voit que cela ne correspond pas : on cherche le t du motif. Que faire alors ?

Deuxième principe : l'analyse du motif

Le deuxième principe est d'analyser au préalable le motif m pour savoir quels sont les caractères qui le composent. Pourquoi ?

Nous allons voir qu'en fonction de la lettre que nous sommes en train de pointer dans le texte, on peut savoir de combien de lettres il faut décaler le motif.

Nous allons créer une table regroupant la correspondance entre lettre lue et décalage nécessaire.

Création de la table de décalage

Remplir et créer cette table est simple :

Soit k le nombre de caractères du motif.

  • Pour un caractère qui n'apparaît pas dans le motif : on décale de k positions : la longueur du motif
  • d p m t i
    0 012 --⇩ tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

    Comme l'espace n'apparaît pas dans le motif, on sait qu'il faut placer le premier caractère du motif à sa droite si on veut tenter de le trouver quelque part. Le motif fait 3 lettres, on décale de trois positions : d = d + 3 = 0 + 3 = 3.

    d p m t i
    3 ...012tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789
  • Pour chaque caractère du motif (sauf le dernier) positionné à l'indice i dans le motif, on doit décaler de k-i-1 positions.
  • Attention : on ne traite pas le dernier caractère du motif. C'est un cas particulier.

Il faut donc lire le motif de la gauche vers la droite et créer la table étape par étape.

Si un caractère est présent plusieurs fois dans le motif, la dernière position trouvée écrase les autres (sauf s'il s'agit du dernier dernier caractère : on ne le traite pas).

On notera que le pretraitement a un coût linéaire par rapport à k. On peut même écrire 𝞗(n).

Créons notre table de prétraitement avec un motif tat.

  • Sa longueur est du motif k = 3.
  • Lorsqu'on rencontre un caractère, on considère par défaut qu'il faut décaler de 3 positions.
  • Puisque t[0] = 't', on en déduit qu'il faut décaler de 3-0-1 = 2 positions lorsqu'on rencontre un t.
  • Puisque t[1] = 'a', on en déduit qu'il faut décaler de 3-1-1 = 1 position lorsqu'on rencontre un a.
  • On ne gère pas le dernier caractère, même s'il s'agit d'un t déjà traité.

Nous obtenons donc le tableau suivant :

  • On pointe un t dans le texte : décalage de 2 positions.
  • On pointe un a dans le texte : décalage de 1 position.
  • Sinon : décalage de 3 positions.

Le principe est donc de perdre du temps pour créer ce tableau de façon à en gagner ensuite.

On voit bien que dans la méthode brute ou naïve, on décale à chaque fois de 1 position, alors qu'ici on décalera plutôt que 3 positions, à moins de tomber sur un a.

Utilisation de la table

Etape 1 : nous avions donc cette situation :

t[d+p] = t[0+2] = t[2]

d p m t i
0 012 tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[2] =   et on doit donc décaler de 3 caractères supplémentaires.

Etape 2 : La variable d est modifiée :

d = d + 3 = 0 + 3 = 3
On reprend en décalant le motif de d = 3 caractères au total.

t[d+p] = t[3+2] = t[5]

d p m t i
3 012 --▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[5] = e et on doit donc décaler de 3 positions supplémentaires.

Etape 3 : La variable d est modifiée à nouveau :

d = d + 3 = 3 + 3 = 6
On reprend en décalant le motif de d = 6 caractères au total.

t[d+p] = t[6+2] = t[8]

d p m t i
6 012 -----▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[8] = h et on doit donc décaler de 3 positions supplémentaires.

Etape 4 : la variable d est modifiée à nouveau :

d = d + 3 = 6 + 3 = 9
On reprend en décalant le motif de d = 9 caractères au total.

t[d+p] = t[9+2] = t[11]

d p m t i
9 012 --------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[11] = t. Cette fois, c'est différent : il y a correspondance.

Que faire maintenant ? Faire pointer sur t[10] et comparer avec l'avant-dernier caractère du motif. Et c'est très simple : il suffit de diminuer la valeur du pointeur p de 1. De 2, il passe donc à 1.

Etape 4-2 : la variable p est modifiée :

p = p - 1 = 2 + 1 = 1
On laisse le décalage du motif mais on observe l'avant-dernier caractère cette fois.

t[d+p] = t[9+1] = t[10]

d p m t i
9 012 --------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[10] = n et ca ne correspond pas.

Nous allons donc stopper la sous-recherche et revenir à p = 2 pour recommencer à chercher le dernier caractère du motif.

t[d+p] = t[9+2] = t[11]
On lit t[11] = t. On lit dans la table qu'il faut décaler de 2 cases supplémentaires dans ce cas.

Etape 5 : La variable d est modifiée à nouveau :

d = d + 2 = 9 + 2 = 11
On reprend en décalant le motif de d = 11 caractères au total.

t[d+p] = t[11+2] = t[13]

d p m t i
11 012 ----------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[13] = t et on pouvoir lancer une sous-recherche.

Etape 5-2 : la variable p est modifiée :

p = p - 1 = 2 + 1 = 1
On laisse le décalage du motif mais on observe l'avant-dernier caractère cette fois.

t[d+p] = t[11+1] = t[12]

d p m t i
11 012 ----------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[12] =   et ca ne correspond pas.

Nous allons donc stopper la sous-recherche et revenir à p = 2 pour recommencer à chercher le dernier caractère du motif.

t[d+p] = t[11+2] = t[13]
On lit t[13] = t et la table nous dit d'avancer de 2 cases supplémentaires.

Etape 6 : La variable d est modifiée à nouveau :

d = d + 2 = 11 + 2 = 13
On reprend en décalant le motif de d = 13 caractères au total.

t[d+p] = t[13+2] = t[15]

d p m t i
13 012 ------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[15] = r et on doit donc décaler de 3 positions supplémentaires.

Etape 7 : La variable d est modifiée à nouveau :

d = d + 3 = 13 + 3 = 16
On reprend en décalant le motif de d = 16 caractères au total.

t[d+p] = t[16+2] = t[18]

d p m t i
16 012 ---------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[18] = d et on doit donc décaler de 3 positions supplémentaires.

Etape 8 : La variable d est modifiée à nouveau :

d = d + 3 = 16 + 3 = 19
On reprend en décalant le motif de d = 19 caractères au total.

t[d+p] = t[19+2] = t[21]

d p m t i
19 012 ------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[21] = s et on doit donc décaler de 3 positions supplémentaires.

Etape 9 : La variable d est modifiée à nouveau :

d = d + 3 = 19 + 3 = 22
On reprend en décalant le motif de d = 22 caractères au total.

t[d+p] = t[22+2] = t[24]

d p m t i
22 012 ---------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[24] = e et on doit donc décaler de 3 positions supplémentaires.

Etape 10 : La variable d est modifiée à nouveau :

d = d + 3 = 22 + 3 = 25
On reprend en décalant le motif de d = 25 caractères au total.

t[d+p] = t[25+2] = t[27]

d p m t i
25 012 ------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[27] = d et on doit donc décaler de 3 positions supplémentaires.

Etape 11 : La variable d est modifiée à nouveau :

d = d + 3 = 25 + 3 = 28
On reprend en décalant le motif de d = 28 caractères au total.

t[d+p] = t[28+2] = t[30]

d p m t i
28 012 ---------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[30] = a et on doit donc décaler de 1 position uniquement.

Etape 12 : La variable d est modifiée à nouveau :

d = d + 1 = 28 + 1 = 29
On reprend en décalant le motif de d = 29 caractères au total.

t[d+p] = t[29+2] = t[31]

d p m t i
29 012 ----------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[31] = a et on doit donc décaler de 3 positions supplémentaires.

Etape 13 : La variable d est modifiée à nouveau :

d = d + 3 = 29 + 3 = 32
On reprend en décalant le motif de d = 32 caractères au total.

t[d+p] = t[32+2] = t[34]

d p m t i
32 012 -------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[34] = T et on doit donc décaler de 3 positions supplémentaires.

Etape 14 : La variable d est modifiée à nouveau :

d = d + 3 = 32 + 3 = 35
On reprend en décalant le motif de d = 35 caractères au total.

t[d+p] = t[35+2] = t[37]

d p m t i
35 012 ----------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[37] = o et on doit donc décaler de 3 positions supplémentaires.

Etape 15 : La variable d est modifiée à nouveau :

d = d + 3 = 35 + 3 = 38
On reprend en décalant le motif de d = 38 caractères au total.

t[d+p] = t[38+2] = t[40]

d p m t i
38 012 -------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[40] =   et on doit donc décaler de 3 positions supplémentaires.

Etape 16 : La variable d est modifiée à nouveau :

d = d + 3 = 38 + 3 = 41
On reprend en décalant le motif de d = 41 caractères au total.

t[d+p] = t[41+2] = t[43]

d p m t i
41 012 ----------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[43] = o et on doit donc décaler de 3 positions supplémentaires.

Etape 17 : La variable d est modifiée à nouveau :

d = d + 3 = 41 + 3 = 44
On reprend en décalant le motif de d = 44 caractères au total.

t[d+p] = t[44+2] = t[46]

d p m t i
44 012 -------------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[46] = é et on doit donc décaler de 3 positions supplémentaires.

Etape 18 : La variable d est modifiée à nouveau :

d = d + 3 = 44 + 3 = 47
On reprend en décalant le motif de d = 47 caractères au total.

t[d+p] = t[47+2] = t[49]

d p m t i
47 012 ----------------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 01234567890123456789012345678901234567890123456789

On lit t[49] = a et on doit donc décaler de 1 position supplémentaire.

Etape 19 : La variable d est modifiée à nouveau :

d = d + 1 = 47 + 1 = 48
On reprend en décalant le motif de d = 48 caractères au total.

t[d+p] = t[48+2] = t[50]

d p m t i
48 012 -----------------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 012345678901234567890123456789012345678901234567890123456789

On lit t[50] =   et on doit donc décaler de 3 positions supplémentaires.

Etape 20 : La variable d est modifiée à nouveau :

d = d + 3 = 48 + 1 = 51
On reprend en décalant le motif de d = 51 caractères au total.

t[d+p] = t[51+2] = t[53]

d p m t i
51 012 --------------------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 012345678901234567890123456789012345678901234567890123456789

On lit t[53] = t : on trouve une concordance et on va pouvoir vérifier la suite en décalant p de 1.

Etape 20' : La variable p diminue pour vérifier l'avant dernier caractère :

p = p - 1 = 2 - 1 = 1
On reprend la vérification avec d = 51 caractères au total.

t[d+p] = t[51+1] = t[52]

d p m t i
51 012 --------------------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 012345678901234567890123456789012345678901234567890123456789

On lit t[52] = a : on trouve encore une concordance et on va pouvoir vérifier la suite en décalant p de 1.

Etape 20'' : La variable p diminue pour vérifier le caractère précédent :

p = p - 1 = 1 - 1 = 0
On reprend la vérification avec d = 51 caractères au total.

t[d+p] = t[51+0] = t[51]

d p m t i
51 012 --------------------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 012345678901234567890123456789012345678901234567890123456789

On lit t[51] = t : on trouve encore une concordance et on va pouvoir vérifier la suite en décalant p de 1.

EtapeEtape 20""" : La variable p diminue pour vérifier le caractère précédent :

p = p - 1 = 0 - 1 = -1
On vient de finir le motif. Il faudra donc stocker cette valeur de d dans le tableau de réponse.

On peut reprendre l'exploration à partir de la valeur suivante : t[d+p] = t[51+2] = t[53]

Comme c'est un t, la table nous indique de décaler encore de 2 cases.

Etape 21 : La variable d est modifiée à nouveau :

d = d + 3 = 51 + 2 = 53
On reprend en décalant le motif de d = 53 caractères au total.

t[d+p] = t[53+2] = t[55]

d p m t i
53 012 ----------------------------------------------------▹tat En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché 012345678901234567890123456789012345678901234567890123456789

On lit t[55] =   : la table indique de décaler de 3 cases....

Nous n'allons plus continuer mais l'algorithme lui ira jusqu'au bout.

Et ça veut dire quoi "jusqu'au bout".

En réflechissant, on peut se rendre compte qu'il est inutile de continuer à partir du moment où le décalage dépasse la longueur du texte moins la longueur du motif :
n - k.

On remarquera également que le décalage est d'autant plus important que le motif est grand. Sauf que plus le motif comporte de caractères plus le décalage est grand... Mais bon, globalement on peut dire que chercher un motif de grande taille ne comportant pas de caractères "communs" près de la fin est relativement rentable.

3 - Exercice

Ce problème est très courant lors des recherches ADN : est-ce qu'une sous-séquence ADN est présente dans une plus grande séquence ADN.

ADN
Illustration ADN en provenance de www.police-scientifique.com

01° Faire le prétraitement de la sous-séquence suivante :

Sous-séquence : ACAT

02° Déterminer à l'aide de l'algorithme les positions intiales de la sous-séquence proposée dans la séquence (en gras puisqu'on le faut à la main pour l'instant) :

Sous-séquence : ACAT

Séquence : TACAGTGTGCCACATCCGGTTGTTAGAGATTCCCGATCAGTAGAAACCCATGGCCCACGGTGTACTTGCCATATATTCTACACTATGGACGCATAGGATAGCCTATGTAACCAAGGTTACGCCTGACATACGAACCAGGTTTAGTTCGTCACCAGATTTGGGGCCCAGTGCTATGGTAACTTTACGCACATTTCGCGAGC

4 - Coût

Alors, a-t-on vraiment fait mieux ? A priori oui puisqu'on obtient un système capable de décaler de plus d'une case à chaque fois.

Mais nous allons voir que les outils dont nous disposons cette anéée ne sont pas suffisant pour démontrer à quel point cet algorithme est vraiment meilleur que la recherche naïve.

Si on regarde bien :

  • Meilleur des cas : c'est lorsqu'aucune lettre sur lesquelles on tombe ne corresponde au motif. Puisqu'on décale de k à chaque fois, on a une complexité du type 𝞗((n-k)/k) et donc 𝞗(n/k) si le texte est vraiment plus long que le motif.
  • Pire des cas : c'est lorsque la lettre testée est toujours la dernière du motif et qu'on est obligé de remonter une bonne partie du motif : seule la dernière lettre est différente. On obtient alors un résultat identique à l'algorithme linéaire : linéaire en n*k donc 𝞗(n*k)
  • p m t
    ⇣⇣⇣⇣⇣⇣⇣ aaaaaaaa haaaaaaaaaaaaaaaaaaaaaa

    Le motif fait ici 8 caractères (k = 8).

    L'avant dernier a est à la position 6.

    Le décalage sur un a est donc de 8 - 6 - 1 = 1. Pas terrible...

  • Pour un cas quelconque, on peut donc juste écrire 𝞞(n*k) comme avec le cas naïf finalement...

En réalité, on sent bien néanmoins qu'il est plus performant que l'algorithme naïf. Mais, il l'est surtout sur le cas moyen. Et pour définit ce cas moyen, il va falloir associer les statistiques, le dénombrement et l'algorithmique.

5 - Implémentation Python

Nous allons voir comment implémenter cela en Python.

Si on veut vraiment réaliser une implémentation rapide, on peut passer par un tableau par le prétraitement. On peut utiliser la valeur UNICODE comme valeur d'indice.

Mais un dictionnaire va nous simplifier la vie.

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
DEBUG = True def pretraitement(m:str) -> dict: """Renvoie un dictionnaire comportant les valeurs de décalage :: exemple :: >>> pretraitement("Bonjour") {'B': 6, 'o': 2, 'n': 4, 'j': 3, 'u': 1} """ dd = {} # dictionnaire de décalage k = len(m) for i in range(0, len(m)-1): dd[m[i]] = k - i - 1 return dd def decalage(c:str, dd:dict, m:str) -> int: """Renvoie le décalage à effectuer pour le caractère c à partir de dd""" if c in dd.keys(): return dd[c] else: return len(m) def recherche(m:str, t:str) -> list: """Renvoie un tableau contient les indices de début de m dans t""" # 1 - Initialisation rep = [] k = len(m) # longueur du motif n = len(t) # longueur du texte dd = pretraitement(m) # dictionnaire de décalage du prétraitement d = 0 # on commence la recherche à gauche # 2 - Lancement de la recherche while d <= n - k: p = k - 1 # on se place sur la fin du motif if DEBUG : print(f"Test en {d}, Lecture en {d+p} donnant {t[d + p]}") while p >= 0 and m[p] == t[d + p]: p = p - 1 if p < 0: # c'est qu'on a trouvé un motif rep.append(d) print(f"Le motif a été trouvé en {d}") p = k - 1 # on se replace sur la fin du motif d = d + decalage(t[d + p], dd, m) # 3 - Renvoie de la réponse return rep if __name__ == '__main__': t_test = "En cherchant tard dans les datas, Toto a trouvé sa tata au supermarché" m_test = "tat" positions = recherche(m_test, t_test) print(positions)

03° Tester le programme pour vérifier qu'il fonctionne. Tester avec votre propre texte et votre propre recherche :

04° Reprendre l'exercice de l'ADN et regarder si la sous-séquence apparaît à d'autres endroits.

05° Télécharger une oeuvre et créer un programme capable de lire le fichier et de faire des recherches de motif sur ce fichier.

6 - FAQ

Rien pour le moment

Activité publiée le 29 05 2021
Dernière modification : 29 05 2021
Auteur : ows. h.