repl.it
@fduffaud/

Boyer-Moore-animation2

Python

No description

fork
loading
Files
  • main.py
main.py
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
#            ALGORITHMES DE RECHERCHE TEXTUELLE

# *************************************************************
# Animations avec les différentes méthodes
# 1. Naives
# 2. Boyer-More Horspool amélioré (avec plusieurs tables des sauts)
# 3. Boyer-More Horspool (avec 1 table  des sauts)
# *************************************************************

import replit # replit.clear() pour vider l'écran


Texte="les optimistes pensent que nous vivons dans le meilleur des mondes, les pessimistes en sont convaincus"
Mot='optimistes'


def RechNaive(texte,motif):
    '''t=0 #pour marquer la position dans le texte
    a=0 #pour marquer le caractère du mot recherché'''    
    
    size = len(texte)
    taille = len(motif)
    
    #Création d'une liste pour récupérer les positions des motifs trouvés dans le texte
    occurences = []
    
    #Si la taille du motif est inférieur ou égale à celle du texte
    if(taille<=size):
        
        
        i=0
        compteur=0
        trouve=False
        
        #tant que l'indice i est inférieur à la taille du texte moins celle du motif
        while(i<=size-taille):
            #On efface l'écran
            print("\x1b[2J")
            replit.clear()
            print("\x1b[31;1mRecherche Naïve\x1b[39;21m")
            #On affiche le texte avec les caractères qui vont être testés encadré en rouge
            print(texte[0:i],"\x1b[41m",texte[i:taille+i],"\x1b[49m",texte[taille+i:])
            #On positionne le motif en dessous de la portion de texte testée
            for pas in range(0,i):
                print(" ",end='')
            print(" \x1b[42m",motif,"\x1b[49m")
            
            #On teste en partant de la droit la correspondance des caractères du motif avec ceux du texte
            for j in range(taille-1,-1,-1):
                compteur=compteur+1
                trouve=True
                #Si les caractères ne correspondent pas
                if(texte[i+j]!=motif[j]):
                    #Si le caractère testé dans le texte est dans le reste du motif
                    i+=1
                    trouve=False
                    break 
            
            #Si tous les caractères correspondent
            if(trouve):
                #On ajoute la position de la portion du texte
                occurences.append(i)
                #On efface l'écran et on cadre le texte trouvé en vert
                print("\x1b[2J")
                replit.clear()
                print("\x1b[31;1mRecherche Naïve\x1b[39;21m")
                print(texte[0:i],"\x1b[42m",texte[i:taille+i],"\x1b[49m",texte[taille+i:])
                for pas in range(0,i):
                    print(" ",end='')
                print(" \x1b[42m",motif,"\x1b[49m")
                #On décale de 1
                i=i+1
                trouve=False
            
            print("###############################################################")
            
            #On affiche toutes les positions trouvées
            for occ in occurences:
                  print("Trouvé à la position :",occ)
            input()
                  
        print(size," ", compteur)

#******************************************************************************
# Boyer-Moore-Horspool avec plusieurs tables de sauts (amélioration de Horspool)
#******************************************************************************
        
def horspool(texte, motif):       
    # On récupère la taille de chaque chaine, on évite de refaire le calcul à chaque besoin
    size = len(texte)
    taille = len(motif)
    
    #Création d'une liste pour récupérer les positions des motifs trouvés dans le texte
    occurences = []
    
    #Si la taille du motif est inférieur ou égale à celle du texte
    if(taille<=size):
        
        #Création d'une liste de dictionnaire
        tab = []
        
        #*******Tables Sauts*******
        #Remplissage de la liste: création de la table des sauts 
        # tab va contenir toutes le stables de sauts sous forme de dictionnaires
        for j in range(taille):
            decalage = {}
            for i in range(taille-1-j):
                decalage[motif[i]]=taille-1-j-i
            decalage[0]=taille-j
            tab.append(decalage)
        #***************************
        i=0
        compteur=0
        trouve=False
        
        #tant que l'indice i est inférieur à la taille du texte moins celle du motif
        while(i<=size-taille):
            #On efface l'écran
            print("\x1b[2J")
            replit.clear()
            print("\x1b[31;1mRecherche Boyer-Moore-Horspool (multi-tables de sauts)\x1b[39;21m")
            #On affiche la table des sauts
            for t in range(len(tab)):
                print(tab[t])
            
            #On affiche le texte avec les caractères qui vont être testés encadré en rouge
            print(texte[0:i],"\x1b[41m",texte[i:taille+i],"\x1b[49m",texte[taille+i:])
            #On positionne le motif en dessous de la portion de texte testée
            for pas in range(0,i):
                print(" ",end='')
            print(" \x1b[42m",motif,"\x1b[49m")
            
            #On teste en partant de la droit la correspondance des caractères du motif avec ceux du texte
            for j in range(taille-1,-1,-1):
                compteur=compteur+1
                trouve=True
                #Si les caractères ne correspondent pas
                if(texte[i+j]!=motif[j]):
                    #Si le caractère testé dans le texte est dans le reste du motif
                    if(texte[i+j] in tab[taille-j-1]):
                        i=i+tab[taille-j-1][texte[i+j]]
                    else:
                        i=i+tab[taille-j-1][0]
                    trouve=False
                    break 
            
            #Si tous les caractères correspondent
            if(trouve):
                #On ajoute la position de la portion du texte
                occurences.append(i)
                #On efface l'écran et on cadre le texte trouvé en vert
                print("\x1b[2J")
                replit.clear()
                print("\x1b[31;1mRecherche Boyer-Moore-Horspool (multi-tables de sauts)\x1b[39;21m")
                for t in range(len(tab)):
                    print(tab[t])
                print(texte[0:i],"\x1b[42m",texte[i:taille+i],"\x1b[49m",texte[taille+i:])
                for pas in range(0,i):
                    print(" ",end='')
                print(" \x1b[42m",motif,"\x1b[49m")
                #On décale de 1
                i=i+1
                trouve=False
            
            print("###############################################################")
            
            #On affiche toutes les positions trouvées
            for occ in occurences:
                  print("Trouvé à la position :",occ)
            input()
                  
        print(size," ", compteur)
    return occurences


#**************************************************************
# Boyer-Moore-Horspool avec 1 table de sauts
#**************************************************************

def table_sauts(motif):
    global T
    T={}
    i=0
    for lettre in motif[:-1]:
        T[lettre]=len(motif)-i-1
        i=i+1
    T[0]=len(motif)
    return T


def bmh(texte, motif): # avec 1 table de sauts
    # On récupère la taille de chaque chaine
    size = len(texte)
    taille = len(motif)
    positions = []
    if(taille<=size):       
        decalage = table_sauts(motif)
        i=0
        compteur=0
        trouve=False
        
        while(i<=size-taille):
            #On efface l'écran
            print("\x1b[2J")
            replit.clear()
            print("\x1b[31;1mRecherche Boyer-Moore-Horspool (1 table de sauts)\x1b[39;21m")
            #On affiche la table des sauts
            print(decalage)
            
            #On affiche le texte avec les caractères qui vont être testés encadré en rouge
            print(texte[0:i],"\x1b[41m",texte[i:taille+i],"\x1b[49m",texte[taille+i:])
            #On positionne le motif en dessous de la portion de texte testée
            for pas in range(0,i):
                print(" ",end='')
            print(" \x1b[42m",motif,"\x1b[49m")
            for j in range (taille-1,-1,-1):
                compteur=compteur+1
                trouve=True
                if(texte[i+j]!=motif[j]):
                    if(texte[i+j] in decalage and decalage[texte[i+j]]<=j):
                            i+=decalage[texte[i+j]]
                    else:
                        #Décalage du reste du motif
                        i+=j+1
                    trouve=False
                    break
            #Si tous les caractères correspondent
            if(trouve):
                #On efface l'écran et on cadre le texte trouvé en vert
                print("\x1b[2J")
                replit.clear()
                print("\x1b[31;1mRecherche Boyer-Moore-Horspool (1 table de sauts)\x1b[39;21m")
                print(decalage)
                print(texte[0:i],"\x1b[42m",texte[i:taille+i],"\x1b[49m",texte[taille+i:])
                for pas in range(0,i):
                    print(" ",end='')
                print(" \x1b[42m",motif,"\x1b[49m")
                #On ajoute la position de la portion du texte
                positions.append(i)
                #On décale de 1
                i=i+1
                trouve=False
            #On affiche toutes les positions trouvées
            for occ in positions:
                  print("Trouvé à la position :",occ)
            input()
            
            #On affiche toutes les positions trouvées            
                  
        print(size," ", compteur)
    return positions


RechNaive(Texte,Mot)
occ=horspool(Texte,Mot)
bmh(Texte,Mot)
'''for i in occ:
    print("trouvé à: ",i)'''

Fetching token
?