Table des matières

Recherche textuelle

Recherche textuelle

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

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.