*******
Dans cette séquence, on s'intéresse au problème de la recherche des occurrences d'une chaîne de caractères, que l'on appellera motif, dans une autre chaîne de caractères, que l'on appellera texte.
Par exemple, il y a deux occurrences du motif \"bra\" dans le texte \"abracadabra\".
Plus précisément, on va chercher à quelles positions dans le texte le motif apparaît.
En numérotant les positions à partir de 0, on a donc une occurrence de \"bra\" à la
position 1 (le deuxième caractère du texte) et une autre à la position 8 (le
neuvième caractère du texte).
Notre objectif dans cette séquence est d'écrire une fonction recherche qui affiche les positions de toutes les occurrences d'un motif dans un texte.
Ainsi, l'appel à
recherche(\"bra\", \"abracadabra\")
devra afficher ceci:
occurrence à la position 1
occurrence à la position 8
On commence par quelques rappels sur les chaînes de caractères de Python.
Une chaîne de caractères peut être écrite au choix entre apostrophes (caractère ') ou entre guillemets (caractère \").
Ainsi, on peut écrire indifféremment 'abracadabra' ou \"abracadabra\".
Nous utiliserons la seconde forme, plus répandue dans les autres langages de programmation.
La longueur d'une chaîne s est obtenue avec len(s).
Les caractères sont numérotés à partir de 0.
Le (i + 1)-ième caractère est obtenu avec s[i] pour 0 ≤ i < len(s).
La sous-chaîne de s contenant les caractères i inclus à j exclu est obtenue avec s[i:j]. Il s'agit d'une nouvelle chaîne de caractères, la chaîne s n'étant pas modifiée.
D'une manière plus générale, les chaînes
de caractères sont immuables.
Les caractères et les chaînes peuvent être comparés avec l'opérateur ==.
Dans tout cette séquence, on note m le motif que l'on recherche et t le texte dans lequel on le recherche.
On note M la longueur du motif et N la
longueur du texte.
Une première remarque évidente est qu'il ne peut y avoir une occurrence de< m dans t que si M≤N.
Plus précisément, une occurrence de m dans t à la position i est contrainte par l'inégalité 0 ≤ i < N - M. En particulier, la chaîne vide \"\", qui à une longueur N = 0, apparaît à toutes les positions dans le texte t, pour N + 1 occurrences au total.
Il est utile de se représenter une occurrence de m dans t à la position i
comme ceci:
![](\"https://sciencesappliquees.com/images/nsi/textu1.png\")
Au dessus, on a représenté les indices des caractères du texte, qui vont de 0
inclus à N exclu.
En dessous, on a représenté les indices des caractères du motif, qui vont de 0 inclus à M exclu.
S'ii y a une occurrence à la position i, alors les caractères t[i],...,t[i + M - 1] du texte coïncident avec les caractères m[0],...,m[M — 1] du motif.
Mettre le résultat ici (code et figure).
Commençons par une première version de notre fonction recherche, la plus simple possible.
Il suffit de considérer successivement toutes les positions possibles pour une occurrence, c'est-à-dire tous les entiers entre 0 et N—M, et de tester pour chacun si la sous-chaîne de t à cette position est égale au motif m.
On peut le faire en trois lignes de code:
def recherche(m, t):
for i in range(0, len(t) - len(m) + 1):
if t[i : i + len(m)] == m :
print (\"occurrence à la position\", i)
Tester la fonction recherche avec le code suivant:
recherche(\"bra\",\"abra-abracadabra\")
Ici, on a utilisé l'opération d'extraction de sous-chaîne de Python pour extraire la chaîne constituée des len(m) caractères situés à la position i dans t, pour la comparer ensuite à m.
Bien que très simple à écrire, cette fonction est assez naïve. En effet, on
va systématiquement construire la sous-chaîne, avec l'opération t[:], pour ensuite la comparer à m.
Or, l'extraction de la sous-chaîne a un coût, qui est proportionnel au nombre de caractères, ici M=len(m).
Comme on va répéter cette opération N — M + 1 fois, on a un coût total Mx(N - M +1).
Si par exemple on cherche un motif de 1000 caractères dans un texte de 2000 caractères, on va faire un peu plus d'un million d'opérations. Or, s'il s'avère que la comparaison échoue rapidement, on aura construit toutes ces sous-chaînes inutilement.
C'est le cas par exemple si on recherche un motif qui contient 1000 caractères a dans un texte qui contient 2000 caractères b.
La comparaison va échouer ystématiquement sur le tout premier caractère, mais on aura néanmoins construit 1001 fois une chaîne de longueur 1000.
Mettre le résultat ici (code et figure).
Pour y remédier, il suffit de comparer directement la chaîne m avec la sous-chaîne contenue dans t à la position i, caractère par caractère, sans utiliser l'opération t[i:i+len(m)].
On peut le faire avec une boucle qui parcourt les caractères de m et les compare aux caractères de t.
On l'écrit sous la forme d'une fonction occurrence(m, t, i) qui renvoie True si et seulement s'il y a une occurrence de m dans t à la position i.
Cette fonction est donnée dans le programme ci-dessous.
Programme — recherche textuelle simple
def occurrence(m, t, i):
\"\"\"indique s'il y a une occurrence de la chaîne m
dans la chaîne t à la position i\"\"\"
if i < 0 or i > len(t) - len(m):
return False
for j in range(len(m)):
if t[i + j] != m[j]:
return False
return True
def recherche1(m, t):
\"\"\"affiche toutes les occurrences de m dans t\"\"\"
for i in range(0, len(t) - len(m) + 1):
if occurrence(m, t, i):
print(\"occurrence à la position\", i)
Elle commence par exclure les cas absurdes où i ne désigne par une position légale dans le texte.
Dans notre cas, nous l'appellerons toujours avec une position légale, mais un code un peu défensif est une bonne pratique.
La fonction compare ensuite les caractères un par un, avec une boucle for, et renvoie False dès qu'il y a une différence.
C'est là tout l'intérêt par rapport à notre première solution.
Si enfin on sort de la boucle, c'est que tous les caractères sont identiques et la fonction renvoie True.
Il est facile d'en déduire une nouvelle fonction recherche, plus efficace.
Elle est donnée dans le programme ci-dessus.
C'est la même fonction que notre première version, où le test occurrence(m,t,i) remplace le test t[i:i+len(m)] == m.
On peut se persuader que cette deuxième version est plus efficace que la première en reprenant l'exemple de la recherche d'un motif contenant 1000 caractères a dans un texte contenant 2000 caractères b.
On a toujours une boucle testant les 1001 valeurs possibles pour i, mais chaque test est maintenant instantané car la fonction occurrence renvoie False dès sa première comparaison.
On a donc au total un millier d'opérations, au lieu d'un million précédemment.
Dans d'autres cas de figure, cependant, notre second programme n'est pas meilleur que le premier.
C'est le cas si tous les caractères doivent être comparés à chaque fois.
Ainsi, si on recherche un motif formé uniquement de caractères a dans un texte également formé uniquement de caractères a, alors on aura un nombre maximal de comparaisons, à savoir Mx(N — M +1).
Le même phénomène peut également se produire sans qu'il y ait pour autant d'occurrence.
Ainsi, si on ajoute un caractère b à la fin du motif, c'est-à-dire si l'on cherche le motif aa...ab dans un texte aa.....aa, alors on fera également Mx(N — M +1) comparaisons au total. En effet, seule la dernière comparaison effectuée par la fonction occurrence est négative.
On peut cependant faire mieux que cet algorithme simple, et c'est ce que nous allons voir maintenant.
Tester la fonction recherche avec le code suivant:
recherche(\"bra\",\"abra-abracadabra\")
Mettre le résultat ici (code et figure).
Le programme précédent effectue une comparaison entre le motif cherché et
chacune des sous-chaînes de longueur M du texte.
Cette comparaison elle-même est accélérée, dans le sens où elle s'interrompt à la première différence trouvée, mais elle doit bien être faite pour tous les indices i de départ jusqu'à la valeur maximale plausible N — M.
Accélérer en sautant certaines sous-chaînes
Une deuxième idée consiste à ne pas appliquer la comparaison à toutes les sous-chaînes, en ignorant certains indices à pour lesquels on a des raisons
d'être certain que le résultat ne peut pas être positif.
Pour l'illustrer, considérons la recherche du motif
m = \"bra\"
dans le texte t = \"bricabrac\".
Lorsque l'on compare le troisième caractère du motif “bra\" avec le caractère correspondant de la sous-chaîne \"bri\" commençant à l'indice i = 0, on apprend certes que cette première sous-chaîne n'est pas une occurrence du motif, mais on remarque également au passage que
le caractère à l'indice 2 est un 'i'. Or, notre motif ne contient aucune occurrence de ce caractère!
Ainsi, aucune sous-chaîne du texte contenant ce caractère \"i\" ne peut être une occurrence du motif.
Il est donc inutile de considérer les sous chaîne \"ri\" et\"Ica\" commençant aux indices i = 1 et i = 2, et l'on peut directement passer à la sous-chaîne \"cab\" commençant à l'indice i = 3.
Considérons maintenant la recherche du motif
m = \"adabrica\"
dans le texte
t = “abracadabracadabricadabra\",
et en particulier la comparaison avec la sous-chaîne \"adabraca\" commençant à l'indice i = 5.
La comparaison du sixième caractère (à l'indice j = 5) nous apprend que cette sous-chaîne n'est pas une occurrence du motif, mais aussi que le caractère à l'indice i + j = 10 dans le texte est un \"a\".
![](\"https://sciencesappliquees.com/images/nsi/textu2.png\")
Ainsi, on sait qu'à moins de dépasser complètement cette partie du texte, seuls les indices i faisant en sorte que ce 'a' du texte corresponde à l'un des 'a' du motif sont intéressants. Faisons l'inventaire des occurrences du caractère 'a' dans le motif : nous en avons trois, aux indices j=0, j=2 et j=7.
Ces trois occurrences sont en correspondance avec le caractère 'a' à
l'indice i + j = 10 dans le texte pour les valeurs respectives 10, 8 et 3 de i.
À l'inverse, on déduit qu'il est inutile de considérer les valeurs 4,5,6,7 et 9 de t, car elles placeraient des caractères différents de 'a' en correspondance avec le 'a' situé à l'indice i + j = 10 du texte.
Parmi les trois valeurs 3, 8 et 10, laquelle choisir comme indice de début de la prochaine sous-chaîne à prendre en compte?
- L'indice i = 3, correspondant à l'occurrence de ‘a' à l'indice j=7 dans le motif, est hors jeu:
notre exploration était déjà arrivée i = 5 et ne fait que progresser. - L'indice i = 10, correspondant à l'occurrence de 'a' à l'indice j = 0 dans le motif, serait tentant car c'est lui qui fait progresser le plus vite dans la lecture du texte. Il risquerait cependant d'aller trop vite et de nous faire manquer une occurrence intermédiaire du motif.
L'indice i = 8, correspondant à l'occurrence de 'a' à l\"indice j = 2 dans
le motif, est le seul candidat possible.
Notez que cette occurrence peut être caractérisée comme «la dernière occurrence de 'a' avant l'indice j=5 du
motif».
En synthétisant les deux exemples précédents, on peut proposer la stratégie suivante:
- Si la sous-chaîne commençant à l'indice i est égale au motif cherché, indiquer une occurrence et reprendre à l'indice i+1.
- Sinon, si l'on a observé une différence entre le caractère à l'indice j du motif et le caractère à l'indice i + j = k du texte, incrémenter i jusqu'à ce que:
- soit i dépasse k,
- soit le caractère à l'indice k-i du motif soit égal au caractère à l'indice i du texte.
Puis reprendre avec le i ainsi obtenu.
Mettre le résultat ici (code et figure).
Accélérer en précalculant les sauts
La stratégie que nous venons d'énoncer semble gagner en efficacité par rapport à celle d'origine, puisqu'elle permet de sauter certaines valeurs de i.
Ces sauts ne sont cependant pas complètement gratuits:
chacun revient à parcourir une partie du motif, à la recherche de la dernière occurrence passée du caractère observé.
Or, si l'on recherche le même motif m dans plusieurs textes différents, ou dans un texte très grand, les mêmes recherches de dernière occurrence d'un certain caractère risquent d'être faites un grand nombre de fois.
Il peut alors être avantageux d'effectuer un pré-traitement du motif afin de pré-calculer tous les sauts dont on pourra avoir besoin et les enregistrer dans une structure de données adaptée.
Dans ce cas, au moment où viendra une opportunité de sauter certains indices i, il suffira de consulter cette structure de données pour savoir directement le nombre d'indices qui peuvent être sautés.
Avec un tel pré-traitement, on sacrifie un peu de temps avant de commencer la recherche, pour ensuite accélérer la recherche elle-même.
Une telle opération a de bonnes chances d'être gagnante si les opérations accélérées arrivent souvent.
L'algorithme de Boyer-Moore que nous allons voir maintenant réalise cette stratégie avec prétraitement, en y ajoutant une dernière optimisation peut-être un peu plus surprenante.
Mettre le résultat ici (code et figure).
L'algorithme de Boyer-Moore utilise un pré-traitement du motif m à chercher dans un texte t pour accélérer cette recherche.
Son principe est le suivant:
- On va tester l'occurrence du motif m dans le texte t à des positions i de plus en plus grandes, en partant de i=0. Cela n'est pas différent pour l'instant de ce que nous avons fait dans les sections précédentes.
- Pour une position i donnée, on va comparer les caractères de m et de t de la droite vers la gauche, c'est-à-dire en comparant d'abord m[M-1]
et t[i+ M — 1], puis m[M — 2] et t[i + M — 2], etc. Il s'agit là du sens inverse de celui utilisé au début de cette séquence. Le changement peut paraître anecdotique, mais en pratique il permet d'avancer plus vite dans certains cas (dont nous discuterons plus loin). - Si tous les caractères coïncident, on à trouvé une occurrence. Sinon, soit j l'indice de la première différence, c'est-à-dire le plus grand entier tel que 0 ≤ j < M et m[j] ≠ t[i+j].
Appelons c le caractère t[i+j].![](\"https://sciencesappliquees.com/images/nsi/textu3.png\")
L'idée de l'algorithme de Boyer-Moore consiste à augmenter alors la valeur de i de:
- la grandeur j — k où k est le plus grand entier tel que 0 ≤ k < j et m[k] = c, si un tel k existe (de manière à amener un caractère c de m sous le caractère t[i+ j]),
- la grandeur j + 1 sinon.
Plutôt que de rechercher un tel k à chaque fois, on peut pré-calculer
une table de décalages contenant, à la case indexée par l'entier j et le caractère c, le plus grand entier k tel que 0 ≤ k < j et m[k] = c s'il existe, et rien sinon.
Mettre le résultat ici (code et figure).
Exemple
Supposons que l'on recherche le motif m = \"abracadabra\".
On est en train de tester l'occurrence de ce motif à une certaine position i dans le texte.
Comme indiqué précédemment, on procède de droite à gauche, en commençant par la fin du motif.
Supposons que les cinq premières comparaisons de caractères ont été positives, c'est-à-dire que les cinq dernières lettres du motif (dabra) coïncident avec les caractères «en face» dans le texte.
Supposons enfin que le caractère suivant
dans le texte ne coïncide pas, car il
s'agit du caractère b alors que le motif a un caractère 'a' à cette position.
La situation s'illustre donc ainsi:
![](\"https://sciencesappliquees.com/images/nsi/textu4.png\")
On consulte alors la table de décalages, pour l'indice j = 5 (la position dans
le motif) et pour le caractère b (le caractère du texte).
La table indique la valeur 4, ce qui veut dire qu'il faut décaler le motif de quatre positions vers la droite.
Cela a pour effet d'amener le caractère b en deuxième position dans le motif sous le caractère b du texte.
Si en revanche le caractère du texte avait été z, alors la table n'aurait pas contenu d'entrée pour ce caractère, car il n'y a pas d'occurrence de z dans les cinq premiers caractères du motif.
On aurait alors décalé le motif de j + 1 = 6 positions vers la droite.
Mettre le résultat ici (code et figure).
Représenter la table de décalages
La table de décalages est une table à deux clés:
d'une part l'indice j du caractère du motif qui diffère et d'autre part le caractère c du texte.
Pour la première clé, c'est-à-dire l'indice j, on peut utiliser un tableau de taille M.
![](\"https://sciencesappliquees.com/images/nsi/textu5.png\")
Pour la seconde clé, c'est-à-dire le caractère c, on ne va en revanche pas utiliser un tableau, car les caractères possibles sont trop nombreux et la table occuperait trop de place en mémoire.
En effet, seuls les caractères apparaissant effectivement dans le motif sont pertinents comme entrées dans cette table, car il s'agit de décalages amenant un caractère du motif sous celui du texte.
Ainsi, pour le motif m = \"abracadabra\", seuls cinq caractères sont significatifs, à savoir a, b, r, c et d.
D'autre part, certaines entrées de la table sont vides, quand il n'y à pas de décalage possible.
D'où l'idée d'utiliser un dictionnaire associant à certains caractères un décalage, et ne mentionnant pas les autres caractères.
On à représenté ci-contre la table de décalages pour le motif m=\"abracadabra\".
Il s'agit d'un tableau de taille M = 11, où chaque élément, c'est-à-dire chaque ligne ici, est un dictionnaire dont les clés constituent un sous-ensemble de {a,b,r,c,d}.
Dans cette table, on retrouve par exemple l'entrée pour j = 5 et c = b prise en exemple plus haut, avec la valeur 1.
Cette valeur est l'indice de l'occurrence du caractère b le plus à droite dans le motif avant l'indice j = 5.
Le décalage s'en déduit comme j — 1 = 5 — 1 = 4.
On prendra le temps de bien comprendre cette table.
Mettre le résultat ici (code et figure).
Utilisation de la table de décalages
Avant d'expliquer comment construire cette table, montrons comment l'utiliser.
Notre objectif est toujours d'écrire une fonction recherche recevant m et t en arguments.
On commence par construire la table de décalages, avec une fonction table_bm que nous détaillerons plns loin.
def recherche(m, t):
d = table_bm(m)
Il s'agit ensuite de tester des positions successives du motif dans le texte.
Comme on ne va pas tester toutes les positions, on utilise une boucle while
plutôt qu'une boucle for.
On démarre avec la position i = 0.
i = 0\n while i <= len(t) - len(m):
On va maintenant comparer les caractères un par un, en partant de la droite.
On retient dans une variable k le décalage trouvé, le cas échéant.
k = 0\n for j in range(len(m) - 1, -1, -1):\n
Dès qu'il y a une différence entre le motif ct le texte, on calcule le décalage
avec une fonction decalage, détaillée plus loin, qui reçoit en arguments la table de décalages d, l'indice j et le caractère du texte.
if t[i + j] != m[j]:\n k = decalage(d, j, t[i + j])\n break
Une fois sorti de la boucle, il y à deux cas de figure.
Soit une différence a été trouvée entre le motif et le texte, et alors la valeur de k est différente de 0. (On verra plus loin que la fonction decalage a toujours un résultat au moins égal à 1.)
Soit k vaut toujours 0, ce qui signifie qu'on a trouvé une occurrence.
On affiche alors l'occurrence et on donne à k la valeur 1, de manière à avancer dans le texte.
if k == 0:\n print(\"occurrence à la position\", i)\n k = 1\n
Enfin, on passe à la position suivante en ajoutant à i la valeur de k, ce qui est correct dans les deux cas de figure.
i += k
Le code de cette nouvelle fonction recherche est donné dans le programme ci-dessous.
Ce programme contient également le code de la fonction decalage.
Cette fonction consulte la table d pour l'indice j et le caractère c, en prenant soin de tester si l'entrée existe ou non.
Pour cela, elle teste si c est une clé du dictionnaire d[j], avec le booléen c in d[j]. Le cas échéant, elle renvoie le décalage, c'est-à-dire la différence j - d[j][c].
Dans le cas contraire, cela signifie que le caractère c n'apparaît pas dans m[0:j] et le décalage renvoyé est donc j+1.
Programme — L'algorithme de Boyer-Moore
def table_bm(m):
\"\"\"construit la table de décalages de Boyer-Moore :
d[j][c] est le plus grand k < j tel que m[k] == c,
s'il existe, et n'est pas défini sinon\"\"\"
d = [{} for _ in range(len(m))]
for j in range(len(m)):
for k in range(j):
d[j][m[k]] = k
return d
def decalage(d, j, c):
\"\"\"utilise la table d lorsque le caractère j est c
au lieu du caractère attendu\"\"\"
if c in d[j]:
# c apparaît en d[j][c] et on décale de la différence
return j - d[j][c]
else:
# c n'apparaît pas du tout dans m[0..j-1]
return j + 1
def recherche2(m, t):
\"\"\"affiche toutes les occurrences de m dans t
avec l'algorithme de Boyer-Moore\"\"\"
d = table_bm(m)
i = 0
while i <= len(t) - len(m):
k = 0
for j in range(len(m) - 1, -1, -1):
if t[i + j] != m[j]:
k = decalage(d, j, t[i + j])
break
if k == 0:
print(\"occurrence à la position\", i)
k = 1
i += k
Tester la fonction recherche2 avec le code suivant:
recherche2(\"bra\",\"abra-abracadabra\")
Mettre le résultat ici (code et figure).
Construction de la table de décaiages
Il reste à expliquer comment construire la table de décalages, ce qui correspond à la fonction table_bm.
Cette fonction reçoit le motif m en argument.
def table_bm(m):
Elle commence par construire un tableau de taille len(m), où chaque élément est un dictionnaire vide.
d = [{} for _ in range(len(m))]Comme pour une matrice, on prend bien soin de ne pas écrire [{}] * m.
On remplit alors tous ces dictionnaires, avec une double boucle sur tous les indices j et sur tous les indices k < j.
for j in range(len(m)):\n for k in range(j):\n
Pour chaque paire d'indices j et k, il suffit de renseigner la clé m[k] du dictionnaire d[j] avec la valeur k.
d[j][m[k]] = k
Comme on parcourt les indices k du plus petit au plus grand, plusieurs occurrences d'un même caractère vont donner plusieurs affectations dans le dictionnaire, chacune écrasant la précédente.
Ainsi, on aura bien au final dans d[j][c] le plus grand k tel que k < j et m[k] = c.
On termine en renvoyant la table.
return d
Le code de cette fonction table_bm est également donné dans le programme précédent.
Mettre le résultat ici (code et figure).
Efficacité
Quelle est l'efficacité de l'algorithme de Boyer-Moore?
Commençons par rappeler que le coût de l'appel à la fonction decalage est constant. En effet, on y fait d'abord un accès dans un tableau, avec d[j], puis une recherche dans un dictionnaire, avec c in d[j] et d[j][c].
Toutes ces opérations sont de temps constant en Python.
Dans le pire des cas, la comparaison entre le motif et le texte se fait systématiquement jusqu'au bout du motif, c'est-à-dire jusqu'à j = 0.
C'est le cas par exemple si on recherche le mot abbb...btb dans le texte bbbb.. bb (aucune occurrence) ou le mot bbb...bb dans ce même texte bbbb...bb (une occurrence à chaque position}.
Dans les deux cas, le nombre total de comparaisons de caractères est Mx(N — M +1), ce qui n'est pas meilleur qu'avec
la recherche simple du programme recherche.
C'est même pire dans le premier cas.
Dans le meilleur des cas, en revanche, la comparaison peut être négative immédiatement, dès Le premier caractère testé, c'est-à-dire pour j = M —1, et le décalage être aussi grand que M.
C'est le cas par exemple si on recherche
le mot aaa...aa dans le texte bbb...bb.
Le nombre total de comparaisons sera alors N/M, car on ne compare plus qu'un caractère sur M.
Ainsi, si on cherche les occurrences d'un motif contenant 1000 caractères a dans un
texte contenant 2000 caractères b, on ne fora que deux comparaisons!
Cet exemple extrême illustre notamment l'intérêt d'avoir procédé de la droite vers la gauche.
Entre ces deux cas de figure, on trouve une multitude de situations intermédiaires, où le coût de la recherche varie beaucoup avec le motif et avec le texte.
Mettre le résultat ici (code et figure).
Plus efficace encore
La table de décalages de l'algorithme de Boyer-Moore peut être encore améliorée.
Reprenons l'exemple donné plus haut où, après avoir comparé avec succès les cinq derniers caractères du motif “abracadabra\", on tombe sur le caractère b dans le texte:
Telle qu'elle est construite actuellement, notre table indique un décalage de 4 caractères (pour amener le b en seconde position du motif sous le b
du texte).
Cependant, cela aura pour effet de placer les caractères racad sous les caractères déjà reconnus dabra.
Comme ils ne coïncident pas, on voit qu'on aurait pu proposer un décalage encore plus grand.
En l'occurrence, on aurait pu décaler de 7 caractères, pour amener ici le abra du début du motif sous le abra contenu dans le texte.
Comme de tels décalages ne font intervenir que des caractères du motif, ils peuvent également être pré-calculés.
Mais cela dépasse largement le programme
de terminale.
Mettre le résultat ici (code et figure).
La recherche textuelle consiste à rechercher la première occurrence, ou toutes les occurrences, d'une chaîne de caractères dans une autre.
Une recherche naïve peut avoir un coût prohibitif.
Ainsi, chercher un motif de mille caractères dans un texte de quelques milliers de caractères peut demander des millions d'opérations.
Il existe cependant des algorithmes plus efficaces, tels que l'algorithme de Boyer-Moore.
Ce dernier effectue un pré-traitement du motif, afin d'accélérer sa recherche dans un texte très grand où dans plusieurs textes.
","title":"Conclusion","tagtitle":"h1"},{"edit":"Mettre le résultat ici (code et figure).
def occurrence(m, t, i):
\"\"\"indique s'il y a une occurrence de la chaîne m
dans la chaîne t à la position i\"\"\"
if i < 0 or i > len(t) - len(m):
return False
for j in range(len(m)):
if t[i + j] != m[j]:
return False
return True
def recherche1(m, t):
\"\"\"affiche toutes les occurrences de m dans t\"\"\"
for i in range(0, len(t) - len(m) + 1):
if occurrence(m, t, i):
print(\"occurrence à la position\", i)
Avec le programme ci-dessous, combien de comparaisons de caractères sont effectuées pendant le calcul de
recherche1(\"chercher\",\" chercher, rechercher et chercher encore\")
Indice : Vous pouvez ajouter un compteur dans la fonction.
Mettre le résultat ici (code et figure).
Il y a 65 comparaisons au total, certaines positives, d’autres négatives.
"}],[{"text":"Écrire une fonction
premiere_occurrence(m, t)
qui renvoie la position de la première occurrence de m dans t, s'il y en a une, et None sinon.
On pourra se resservir de la fonction occurrence du programme recherche1.
def occurrence(m, t, i):
\"\"\"indique s'il y a une occurrence de la chaîne m
dans la chaîne t à la position i\"\"\"
if i < 0 or i > len(t) - len(m):
return False
for j in range(len(m)):
if t[i + j] != m[j]:
return False
return True
Tester avec:
print(premiere_occurrence(\"chercher\",\" chercher, rechercher et chercher encore\"))
print(premiere_occurrence(\"trouver\",\" chercher, rechercher et chercher encore\"))
Résultat:
1
None
Mettre le résultat ici (code et figure).
def premiere_occurrence(m, t):
\"\"\"renvoie la première occurrence de m dans t,
Le cas échéant, et None sinon\"\"\"
for i in range(0, len(t) - len(m) + 1):
if occurrence(m, t, i):
return i
return None
Construire (à la main) la table de décalages de l'algorithme de Boyer-Moore pour le motif \"banane\".
Mettre le résultat ici (code et figure).
![](\"https://sciencesappliquees.com/images/nsi/textu6.png\")
On note que le caractère e n’apparaissant qu’en dernière position, on a une colonne entièrement vide.
Construire (à la main) la table de décalages de l'algorithme de Boyer-Moore pour le motif \"chercher\".
Mettre le résultat ici (code et figure).
Exercice 132
En utilisant le résultat de l'exercice précédent, dérouler manuellement l'exécution du programme recherche2 pendant le calcul de
recherche2(\"chercher\", \"chercher, rechercher et chercher encore\")
en donnant notamment les valeurs successives de la variable i.
Indiquer le nombre total de comparaisons de caractères.
Comparer avec le résultat du programme recherche 1.
Mettre le résultat ici (code et figure).
La variable i prend successivement les valeurs :
- 0 (occurrence, qui donne le décalage 1)
- 1 (qui donne le décalage 8),
- 9 (décalage 3),
- 12 (occurrence, décalage 1),
- 13 (décalage 8),
- 21 (décalage 3),
- 24 (occurrence, décalage 1),
- 25 (décalage 8).
La dernière valeur prise par i est 33 et on sort alors de la boucle car cette valeur dépasse len(t) — len(m) = 39 - 8 = 31.
Il y a 29 comparaisons au total (certaines positives, d’autres négatives).
def recherche(m, t):
for i in range(0, len(t) - len(m) + 1):
if t[i : i + len(m)] == m :
print (\"occurrence à la position\", i)
Écrire une fonction mesure_rec1 qui renvoie le temps de recherche de toutes les occurrences d’un motif dans un texte avec l’algorithme naif.
Testez-la avec le texte suivant :
\"Apprendre à coder, c'est comme apprendre la musique : il faut connaître ses gammes pour devenir un Mozart ou un Beethoven de l'informatique.\"
et le motif : \"Mozart\"
Modifier le programme recherche pour ajouter un un compteur pour déterminer le nombre de comparaisons effectuées avec cet algorithme.
Tester avec:
texte = \"Apprendre à coder, c'est comme apprendre la musique : il faut connaître ses gammes pour devenir un Mozart ou un Beethoven de l'informatique.\"
motif = \"Mozart\"
mesure_rec1(motif,texte)
Mettre le résultat ici (code et figure).
Temps:
def mesure_rec1(m,t):
start = time.time()
recherche(m ,t)
end = time.time() - start
print(\"algo naif\",end)
Compteur:
def recherche(m, t):
cpt = 0
for i in range(0, len(t) - len(m) + 1):
cpt+=1
if t[i : i + len(m)] == m :
print (\"occurrence à la position\", i)
print(\"Nb comparaisons : \",cpt)
def table_bm(m):
\"\"\"construit la table de décalages de Boyer-Moore :
d[j][c] est le plus grand k < j tel que m[k] == c,
s'il existe, et n'est pas défini sinon\"\"\"
d = [{} for _ in range(len(m))]
for j in range(len(m)):
for k in range(j):
d[j][m[k]] = k
return d
def decalage(d, j, c):
\"\"\"utilise la table d lorsque le caractère j est c
au lieu du caractère attendu\"\"\"
if c in d[j]:
# c apparaît en d[j][c] et on décale de la différence
return j - d[j][c]
else:
# c n'apparaît pas du tout dans m[0..j-1]
return j + 1
def recherche3(m, t):
\"\"\"affiche toutes les occurrences de m dans t
avec l'algorithme de Boyer-Moore\"\"\"
d = table_bm(m)
i = 0
while i <= len(t) - len(m):
k = 0
for j in range(len(m) - 1, -1, -1):
if t[i + j] != m[j]:
k = decalage(d, j, t[i + j])
break
if k == 0:
print(\"occurrence à la position\", i)
k = 1
i += k
Écrire une fonction qui renvoie le temps de recherche de toutes les occurrences d’un motif dans un texte avec l’algorithme Boyer-Moore-Horspool.
Testez-la avec le texte suivant :
\"Apprendre à coder, c'est comme apprendre la musique : il faut connaître ses gammes pour devenir un Mozart ou un Beethoven de l'informatique.\"
et le motif : \"Mozart\"
Modifier le programme recherche pour ajouter un un compteur pour déterminer le nombre de comparaisons effectuées avec cet algorithme.
Tester avec:
texte = \"Apprendre à coder, c'est comme apprendre la musique : il faut connaître ses gammes pour devenir un Mozart ou un Beethoven de l'informatique.\"
motif = \"Mozart\"
mesure_rec2(motif,texte)
Comparer les 2 algorithmes de recherches par rapport à vos résultats.
Mettre le résultat ici (code et figure).
Temps :
def mesure_rec2(m,t):
start = time.time()
recherche3(m ,t)
end = time.time() - start
print(\"algo Boyer-Moore\",end)
Compteur :
def recherche3(m, t):
\"\"\"affiche toutes les occurrences de m dans t
avec l'algorithme de Boyer-Moore\"\"\"
d = table_bm(m)
i = 0
cpt=0
while i <= len(t) - len(m):
k = 0
for j in range(len(m) - 1, -1, -1):
cpt+=1
if t[i + j] != m[j]:
k = decalage(d, j, t[i + j])
break
if k == 0:
print(\"occurrence à la position\", i)
k = 1
i += k
print(\"Nb comparaisons : \",cpt)
Maintenant vous allez comparer les deux algorithmes sur un texte plus long en faisant varier le motif.
1. Télécharger (ici) et importer le fichier texte livre.txt qui propose le roman «Le Rouge et le Noir» écrit en 1830 par l’écrivain Stendhal (1783-1842).
2. Testez vos fonctions de recherche sur ce texte avec quelques mots comme \"Mozart\", \"esprit\", \"est\", \"les\".
Puis avec la lettre \"e\",
Que remarquez-vous?
3. Mettez les résultats dans un tableau avec le nombre de comparaison.
Conclure.
","title":"Exercice"},{"edit":"Mettre le résultat ici (code et figure).
with open(\"livre.txt\",\"r\") as f:
texte = f.read()