Document sous licence CC BY-NC-SA 4.0
alphabet = ['G','T','C','A'] motif = 'GATTACA'
On crée un texte aléatoire texte
contenant le motif et un autre texte2
qui ne le contient pas, à fin de tester nos fonctions.
import random as rd
N = 10000
# on tire au hasard un texte sur l'alphabet, jusqu'à trouver un texte contenant le motif
for _ in range(10000):
texte = ''
for i in range(N):
texte += rd.choice(alphabet)
if texte.find(motif) != -1: break
for _ in range(1000):
texte2 = ''
for i in range(N):
texte2 += rd.choice(alphabet)
if texte2.find(motif) == -1: break
texte.find(motif),texte2.find(motif)
(4264, -1)
texte[4094:4104] + '...'
'AATACGGGCT...'
fichier = open('LeRougeEtLeNoir.txt','r')
stendhal = fichier.read()
fichier.close()
stendhal.find('Julien tremblait')
161411
stendhal[161411:161500] + '...'
'Julien tremblait que sa demande ne fût accordée son rôle de séducteur lui pesait si horri...'
def nbOccurences(texte,motif):
r,i = 0,0
while True:
k = texte[i:].find(motif)
if k == -1: return r
else:
r += 1
i += k + 1
nbOccurences(stendhal,'Julien tremblait'),nbOccurences(stendhal,'amour'),\
nbOccurences(stendhal,'haine'),nbOccurences(stendhal,'mort'),\
nbOccurences(stendhal,'Julien')
(1, 225, 36, 178, 1908)
Recherche naïve : à chaque échec on décale d'une unité la fenêtre vers la droite. On teste chaque fenêtre de droite à gauche.
Le décalage de la fenêtre se fait en ligne 12.
def cherche(texte,motif):
n = len(texte)
p = len(motif)
if p > n: return -1
debut = 0
while debut <= n-p:
j = p-1
while j >= 0:
if texte[debut+j] != motif[j]: break
j -= 1
if j<0: return debut
debut += 1
return -1
cherche(texte,motif),cherche(texte2,motif)
(4264, -1)
cherche(stendhal,'Julien tremblait')
161411
def calculeDecalages(motif):
d = {}
p = len(motif)
for c in motif: d[c] = -1
for i in range(p):
d[motif[i]] = i
return d
def decale(c,decalages):
try:
return decalages[c]
except KeyError:
return -1
d = calculeDecalages('aababab')
decale('a',d),decale('b',d),decale('w',d)
(5, 6, -1)
def BM(texte, motif):
n = len(texte)
p = len(motif)
if p > n: return -1
decalages = calculeDecalages(motif)
debut = 0
while debut <= n-p:
j = p-1
while j >= 0:
if texte[debut+j] != motif[j]: break
j -= 1
if j < 0: return debut
k = j - decale(texte[debut+j],decalages)
if k < 1: k = 1
debut += k
return -1
BM('aabbbababacaabbabaabababaab','aabba')
11
BM(texte,motif),BM(texte2,motif)
(4264, -1)
BM(stendhal,'Julien tremblait')
161411
def nbOccurencesBM(texte,motif):
r,i = 0,0
while True:
k = BM(texte[i:],motif)
if k == -1: return r
else:
r += 1
i += k + 1
nbOccurencesBM(stendhal,'Julien'),nbOccurencesBM(stendhal,'amour'),\
nbOccurencesBM(stendhal,'Napoléon'),nbOccurencesBM(stendhal,'Bonaparte'),nbOccurencesBM(stendhal,'Waterloo')
(1908, 225, 33, 17, 1)
Références :
Remarque : le Beauquier-Berstel-Chrétienne est en français, il décrit de plus l'algorithme plus avancé de Boyer et Moore, non repris par Sedgewick ni présenté dans ce document. Sa lecture est sans doute plus difficile que celle de l'excellent Sedgewick, mais il est en revanche disponible gratuitement en ligne !