medite.MediteAppli.utile

1 # -*- coding: iso-8859-1 -*- 2 # Copyright 20003 - 2008: Julien Bourdaillet (julien.bourdaillet@lip6.fr), Jean-Gabriel Ganascia (jean-gabriel.ganascia@lip6.fr) 3 # This file is part of MEDITE. 4 # 5 # MEDITE is free software; you can redistribute it and/or modify 6 # it under the terms of the GNU General Public License as published by 7 # the Free Software Foundation; either version 2 of the License, or 8 # (at your option) any later version. 9 # 10 # MEDITE is distributed in the hope that it will be useful, 11 # but WITHOUT ANY WARRANTY; without even the implied warranty of 12 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13 # GNU General Public License for more details. 14 # 15 # You should have received a copy of the GNU General Public License 16 # along with Foobar; if not, write to the Free Software 17 # Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 18 19 import os, sys, re, bisect 20

21 -class Utile(object):

22 # renvoie un nom de fichier, si celui-ci existe

23 - def nom_fichier(self, chaine) :

24 drapeau = 0 25 if os.name == 'mac': 26 dir_texte = 'textes:' 27 else: dir_texte = '/textes/' 28 while drapeau == 0 : 29 drapeau = 1 30 fic = raw_input(chaine) 31 nom = os.getcwd() + dir_texte + fic + '.txt' 32 if os.path.isfile(nom): 33 return fic 34 else: 35 ## print nom, " n'est pas un nom de fichier! Recommencez." 36 # L = os.listdir(os.getcwd() + dir_texte) 37 ## for D in L: 38 ## if os.path.isfile(os.getcwd() + dir_texte + D): 39 ## print " > ", D 40 drapeau = 0

41

42 - def ouvrir(self, fic, m):

43 # ouvre le fichier fic (nom relatif) en mode m 44 if os.name == 'mac' : 45 if m == "r": 46 dir_texte = 'textes:' 47 else: 48 dir_texte = 'sortie:' 49 else: 50 if m == "r": 51 dir_texte = '/textes/' 52 else: 53 dir_texte = '/sortie/' 54 abs_fic = os.getcwd() + dir_texte + fic + '.txt' 55 return open(abs_fic, m)

56

57 - def lire_fic(self, fic):

58 # lit le contenu du fichier et le renvoie sous forme d'une chaîne 59 # fic est le nom relatif du fichier (sans l'extension '.txt') 60 fichier_entree = self.ouvrir(fic, "r") 61 return fichier_entree.read()

62

63 - def creer_fic(self, fic):

64 if not 'sortie' in os.listdir(os.getcwd()): 65 os.mkdir('sortie') 66 return self.ouvrir(fic, "w")

67

68 - def ajout_fic(self, fic, T):

69 fichier_sortie = self.ouvrir(fic, "a") 70 fichier_sortie.write(T)

71

72 - def non_nul_keys(self, D) : # donne la liste des clefs non vides d'un dictionnaire D

73 L = [ ] 74 for Clef in D.keys() : 75 if D[Clef] != { } and D[Clef] != [] : 76 L.append(Clef) 77 #if D[Clef] == [] : 78 #print "Clef non nulle... '", Clef, "' dictionnaire: ", D 79 return L

80

81 - def non_nul_values(self, D) : # donne la liste des clefs non vides d'un dictionnaire D

82 L = [ ] 83 if D.values != {} : 84 for val in D.values() : 85 if val != { } or val != [] : 86 L.append(val) 87 return L 88 89

90 - def dif_intervalles(self, L, C) : # enlève un intervalle de valeurs dans une liste d'intervalles

91 # L est une liste d'intervalles, C, un intervalle 92 NL = [ ] 93 ncouple = [] 94 nncouple = [] 95 for couple in L : 96 if couple[0] < C[0] : 97 if couple[1] >= C[0] : 98 ncouple.append(couple[0]) 99 ncouple.append(C[0]) 100 if couple[1] > C[1] : 101 nncouple.append(C[1]) 102 nncouple.append(couple[1]) 103 elif couple[1] > C[1] and couple[0] <= C[1] : 104 ncouple.append(C[1]) 105 ncouple.append(couple[1]) 106 if ncouple != [] : 107 NL.append(ncouple) 108 ncouple = [] 109 if nncouple != [] : 110 NL.append(nncouple) 111 nncouple = [] 112 if couple[0] > C[1] or couple[1] < C[0] : 113 NL.append(couple) 114 return NL 115

116 - def soustr_l_intervalles(self, P, L):

117 # soustractrion de deux liste d'intervalles 118 L = L[:] # on copie L pour pouvoir modifier la vairable locale sans toucher celle de l'appel 119 while len(L) > 0: ##L <> []: 120 P = self.dif_intervalles(P, L.pop(0)) #L[0]) 121 #L = L[1:] #del L[0] #;L = L[1:] #L.pop(0) #L = L[1:] 122 return P

123

124 - def miroir(self, locc, debut, fin):

125 """Prends une liste d'intervalles définis sur l'intervalle [debut,fin] 126 et retourne la différence entre [début,fin] et tous les elements de cette liste 127 en temps linéaire(locc)""" 128 LRes = [] 129 pos = debut 130 for (d,f) in locc: 131 if pos < d : # intervalle non nul 132 LRes.append((pos,d)) 133 pos = f # passe à l'intervalle suivant 134 if pos < fin: LRes.append((pos,fin)) # dernier element eventuel 135 #if __debug__: 136 # longueur1 = longueur2 = 0 137 # for d,f in locc: longueur1 += f-d 138 # for d,f in LRes: longueur2 += f-d 139 #print longueur1,longueur2 140 #assert longueur2 == fin-debut-longueur1 #marche pas à cause des chevauchements 141 142 return LRes

143

144 - def ajout_intervalle(self, L, C) : # ajoute un intervalle de valeurs dans une liste d'intervalles

145 # L est une liste d'intervalles, C un intervalle 146 Q = [] 147 while L <> [] and L[-1][-1] >= C[0] : 148 if L[-1][0] > C[1]: 149 Q = [L[-1]] + Q 150 L.pop() #L = L[0:-1] 151 else: 152 C = [min(C[0], L[-1][0]), max(C[1], L[-1][-1])] 153 L.pop() #L = L[0:-1] 154 L.append(C) 155 return L+Q 156

157 - def addition_l_intervalle(self,L, LC):#ajout liste intervalles sans fusion

158 for x in LC: 159 #L = self.addition_intervalle(L, x) 160 bisect.insort_right(L, x) 161 return L 162

163 - def addition_intervalle(self, L, C) : # ajoute un intervalle de valeurs, sans

164 # fusionner les intervalles 165 #print "Appel addition intervalle L:", L, "; C:", C 166 bisect.insort_right(L, C) 167 return L 168 #i = 0 169 #l = len(L) 170 #if (L == [] or L[0][0] >= C[0]): 171 # return [C]+L 172 #while i < l: 173 # if L[i][0] >= C[0]: 174 # return L[0:i] + [C] + L[i:] 175 # else: i = i+1 176 #return L+[C] 177 178

179 - def inclusion(self, L1, L2) : # renvoie vrai si la liste L1 est incluse dans la liste L2

180 for elt in L1 : 181 if not elt in L2 : 182 return 0 183 return 1 184

185 - def difference(self, L1,L2):

186 # renvoie la difference entre L1 et L2 187 L=L1[:] 188 for X in L2: 189 if X in L: 190 L.remove(X) 191 return L

192

193 - def difference_sym(self, L1,L2):

194 # renvoie la difference symétrique entre L1 et L2 195 L=[] 196 for x in L1: 197 if x not in L2: L.append(x) 198 for x in L2: 199 if x not in L1 and x not in L: L.append(x) 200 return L

201

202 - def inclus(self, I, L): # renvoie vrai si l'intervalle I est inclus dans l'un des intervalles de L

203 for elt in L: 204 if (I[0]>= elt[0] and I[1] <= elt[1] ): 205 return 1 206 return 0 207

208 - def inclus_(self, I1, I2): # renvoie vrai si l'intervalle I1 est inclus dans I2

209 if (I1[0] >= I2[0] and I1[1] <= I2[1]): 210 return 1 211 return 0 212

213 - def int_inclus(self, I, L): # renvoie l'ensemble des intervalles de L inclus dans l'intervalle I`

214 LL = [] 215 while L <> []: 216 if self.inclus_(L[-1], I): 217 LL.append(L[-1]) 218 #L = L[:-1] 219 L.pop() 220 return LL 221

222 - def longueur(self, L): # longueur d'une liste d'intervalles, c'est-à-dire longueur de la chaîne couverte par la liste

223 n = 0 224 while L <> []: 225 n = n + L[0][1] - L[0][0] 226 #L = L[1:] 227 L.pop(0) 228 return n 229

230 - def union(self, L1, L2): # renvoie la réunion de deux listes d'intervalles

231 for I in L1: 232 L2 = self.ajout_intervalle(L2, I) 233 return L2 234

235 - def union2(self, L1, L2): # renvoie la réunion de deux listes d'intervalles

236 for I in L1: 237 L2 = self.addition_intervalle(L2, I) 238 return L2 239

240 - def nettoyer_dict(self, D):

241 ND = {} 242 for Clef,liste in D.iteritems(): 243 #if D[Clef] != []: 244 # ND[Clef] = D[Clef] 245 if len(liste) > 0: 246 ND[Clef] = liste 247 return ND

248 249 # Detection des remplacements 250 # Ecrit par Jean-Gabriel Ganascia le 16 fevrier 2003 251

252 - def rang_blocs(self, occs_blocs, occs_ts_blocs, occs_blocs_d):

253 #print "Appel rang blocs: ", occs_blocs 254 L = self.rang_blocs_(occs_blocs, occs_ts_blocs, occs_blocs_d, 0, [], [0, 0]) 255 #print "valeur rang blocs: ", L 256 return L

257

258 - def rang_blocs_(self, occs_blocs, occs_ts_blocs, occs_blocs_d, Rang, Acc, Der):

259 #print 'appel rang blocs_ avec occs_blocs=', occs_blocs, ' occs_ts=', occs_ts_blocs, ' rang=', Rang, ' acc=', Acc, ' der=', Der 260 while occs_blocs <> []: 261 if occs_blocs[0] <= Der: 262 occs_blocs = occs_blocs[1:] 263 elif occs_ts_blocs == []: 264 Acc.append([occs_blocs[0], Rang]) 265 occs_blocs = occs_blocs[1:] 266 elif ( occs_ts_blocs[0] in occs_blocs_d or 267 occs_ts_blocs[0] in occs_blocs ): 268 occs_ts_blocs = occs_ts_blocs[1:] 269 elif occs_blocs[0] < occs_ts_blocs[0]: 270 Acc.append([occs_blocs[0], Rang]) 271 occs_blocs = occs_blocs[1:] 272 else: 273 Der = occs_ts_blocs[0] 274 occs_ts_blocs = occs_ts_blocs[1:] 275 Rang = Rang + 1 276 #print "Acc partiel: ", Acc 277 #print "Valeur rang blocs: ", Acc 278 return Acc

279 280

281 - def fusion(self, L):

282 #print "Appel fusion: L= ", L 283 if L == []: 284 return L 285 else: 286 return self.fusion__(L[-1], L[:-1])

287

288 - def fusion__(self, E, L):

289 aux = [] 290 while L <> []: 291 if E[1] == L[-1][1]: 292 E = [[L[-1][0][0], E[0][1]], L[-1][1]] 293 L = L[:-1] 294 else: 295 aux = [E] + aux 296 E = L[-1] 297 L.pop() #L = L[:-1] 298 aux = [E] + aux 299 #print "Valeur fusion : ", aux 300 return aux

301 302

303 - def correspondance(self, L1, L2, T, ratio_min_remplacement):

304 aux0 = [] 305 aux1 = [] 306 while (L1 <> [] and L2 <> []): 307 if L1[-1][1] == L2[-1][1]: 308 if self.adequation_remplacement(L1[-1][0], L2[-1][0], T, ratio_min_remplacement): 309 aux0.append(L1[-1]) 310 aux1.append(L2[-1]) 311 L1.pop() #L1 = L1[:-1] 312 L2.pop() #L2 = L2[:-1] 313 elif L1[-1][1] > L2[-1][1]: 314 L1.pop() #L1 = L1[:-1] 315 else: 316 L2.pop() #L2 = L2[:-1] 317 aux0.reverse() 318 aux1.reverse() 319 return [aux0, aux1]

320 321

322 - def correspondance_(self, L1, L2, T, ratio_min_remplacement):

323 L = [] 324 while (L1 <> [] and L2 <> []): 325 if L1[-1][1] == L2[-1][1]: 326 if self.adequation_remplacement(L1[-1][0], L2[-1][0], T, ratio_min_remplacement): 327 L = self.addition_intervalle(L, L1[-1][0]) 328 L = self.addition_intervalle(L, L2[-1][0]) 329 L1.pop() #L1 = L1[:-1] 330 L2.pop() #L2 = L2[:-1] 331 elif L1[-1][1] > L2[-1][1]: 332 L1.pop() #L1 = L1[:-1] 333 else: 334 L2.pop() #L2 = L2[:-1] 335 return L

336

337 - def adequation_remplacement(self, texte1, texte2, ratio_min_remplacement):

338 if self.chaine_blanche(texte1) or self.chaine_blanche(texte2): 339 return 0 340 ratio = float(len(texte1))/float(len(texte2)) 341 #print "test: t1:", T[I1[0]:I1[1]], "; t2", T[I2[0]:I2[1]], "; ratio: ", ratio 342 if ratio > ratio_min_remplacement or ratio < 1/ratio_min_remplacement: 343 return 0 344 return 1

345

346 - def chaine_blanche(self, texte):

347 for c in texte: 348 if c not in ' \n\t\r': 349 return 0 350 return 1

351 352 #return self.chaine_blanche_(T[I[0]:I[-1]]) 353

354 - def chaine_blanche_(self, chaine):

355 """Renvoie vrai si la chaine ne contient que des séparateurs """ 356 while chaine <> '': 357 c = chaine[0] 358 if c <> ' ' and c <> '\n' and c <> '\t' and c <> '\r': 359 return 0 360 chaine = chaine[1:] 361 return 1

362

363 - def elimine_int_couverts(self, L, P):

364 # prend deux listes d'intervalles en entree 365 # renvoie la liste P dont on a enleve les intervalles 366 # couverts par des intervalles de la liste L 367 Q = [] 368 while L <> [] and P <> []: 369 # sys.stderr.write("Supp P[0]="+str(P[0])+" / Remp L[0]="+str(L[0])) 370 # sys.stderr.write("supp="+t[P[0][0]:P[0][1]]+" / remp="+t[L[0][0]:L[0][1]]) 371 if L[0][1] < P[0][0]: 372 L.pop(0) #L = L[1:] 373 # sys.stderr.write(" / 1 jette remp") 374 elif L[0][0] > P[0][1]: 375 Q = self.addition_intervalle(Q, P[0]) 376 P.pop(0) #P = P[1:] 377 # sys.stderr.write(" / 2 garde supp") 378 elif L[0][1] >= P[0][1]: 379 P.pop(0) #P = P[1:] 380 # sys.stderr.write(" / 3 jette supp") 381 else: 382 L.pop(0) #L = L[1:] 383 # sys.stderr.write(" / 4 jette remp 2") 384 # sys.stderr.write("\n") 385 # sys.stderr.write("Supp P="+str(P)+" / Remp L="+str(L)+"\n") 386 while P <> []: 387 Q = self.addition_intervalle(Q, P[0]) 388 P.pop(0) #P = P[1:] 389 return Q

390

391 - def elimine_int_couverts__(self, L, P):

392 # prend deux listes d'intervalles en entree 393 # renvoie la liste P dont on a enleve les intervalles 394 # couverts par des intervalles de la liste L 395 Q = [] 396 while L <> [] and P <> []: 397 # sys.stderr.write("Supp P[0]="+str(P[0])+" / Remp L[0]="+str(L[0])) 398 # sys.stderr.write("supp="+t[P[0][0]:P[0][1]]+" / remp="+t[L[0][0]:L[0][1]]) 399 if L[0][1] < P[0][0]: 400 L.pop(0) #L = L[1:] 401 # sys.stderr.write(" / 1 jette remp") 402 elif L[0][0] > P[0][1]: 403 Q = self.addition_intervalle(Q, P[0]) 404 P.pop(0) #P = P[1:] 405 # sys.stderr.write(" / 2 garde supp") 406 elif L[0][0]<=P[0][0] and L[0][1] >= P[0][1]: 407 P.pop(0) #P = P[1:] 408 # sys.stderr.write(" / 3 jette supp") 409 elif L[0][0]<=P[0][0] and L[0][1] <= P[0][1]: 410 NP = [L[0][1], P[0][1]] 411 L.pop(0) #L = L[1:] 412 P = [NP]+P[1:] 413 elif L[0][0]>P[0][0] and L[0][1] > P[0][1]: 414 Q = self.addition_intervalle(Q, [P[0][0],L[0][0]]) 415 P.pop(0) #P = P[1:] 416 417 # sys.stderr.write(" / 4 jette remp 2") 418 # sys.stderr.write("\n") 419 # sys.stderr.write("Supp P="+str(P)+" / Remp L="+str(L)+"\n") 420 while P <> []: 421 Q = self.addition_intervalle(Q, P[0]) 422 P.pop(0) #P = P[1:] 423 return Q

424

425 - def comp(self, x, y):

426 if x > y: 427 return -1 428 else: return +1

429

430 - def comp_longueur(self, x, y):

431 if len(x) > len(y): 432 return -1 433 else: 434 return +1

435

436 - def couverte(self, chaine, liste):

437 for chaines in liste: 438 if self.sous_motif(chaine, chaines): 439 return 1 440 return 0

441

442 - def sous_motif(self, motif, chaine):

443 try: 444 return re.search(motif, chaine) 445 except: 446 return 0

447

448 - def adjacent(self, I1, I2):

449 # Renvoie 1 si les deux intervalles I1 et I2 sont adjacents, 0 sinon 450 return (((I1[0] <= I2[0]) and (I1[1] >= I2[0])) or 451 ((I1[0] <= I2[1]) and (I1[1] >= I2[1])))

452

453 - def adjacent_(self, I, L):

454 # Renvoie 1 si I est adjacent à au moins un intervalle de L, 0 sinon 455 for II in L: 456 if self.adjacent(I, II): 457 return 1 458 elif II[0] > I[1]: 459 return 0 460 return 0

461 462 # Composition decalee 463 # Ecrit par Jean-Gabriel Ganascia le 30 juillet 2004 pour optimiser 464 # la construction de classes dequivalence

465 - def composition_decalee(self, L_occs_deb, L_occs_suite, dec):

466 #print "Longueur deb: ", len(L_occs_deb), "; suite: ", len(L_occs_suite) 467 L_deb = L_occs_deb 468 L_suite = L_occs_suite 469 res = [] 470 while L_deb and L_suite: 471 if L_deb[0]+dec < L_suite[0]: 472 L_deb.pop(0) #L_deb = L_deb[1:] 473 elif L_deb[0]+dec == L_suite[0]: 474 res.append(L_deb[0]) 475 L_deb.pop(0) #L_deb = L_deb[1:] 476 L_suite.pop(0) #L_suite = L_suite[1:] 477 else: 478 L_suite.pop(0) #L_suite = L_suite[1:] 479 return res

480 # renvoie la liste des chaines de taille 2dec (ou 2a) 481 # qui commencent dans L_occ_deb et dont la 2e moitié commence dans L_occs_suite

482 - def composition_decalee_(self, L_occs_deb, L_occs_suite, dec):

483 res=[] 484 for X in L_occs_deb: 485 if X+dec in L_occs_suite: 486 res.append(X) 487 return res

488 # même chose mais L_occs_suite n'est parcourue qu'une seule fois

489 - def composition_decalee_b(self, L_occs_deb, L_occs_suite, dec):

490 res=[] 491 j=0 492 l=len(L_occs_suite) 493 for X in L_occs_deb: 494 while L_occs_suite[j] < X+dec: 495 if j < l-1: 496 j = j+1 497 else: return res 498 if L_occs_suite[j] == X+dec: 499 res.append(X) 500 return res

501

502 - def composition_decalee_mot(self, L_occs_deb, L_occs_suite, dec,texteMot):

503 res=[] 504 for X in L_occs_deb: 505 if texteMot.posCarMot(X,dec) in L_occs_suite: 506 res.append(X) 507 return res

508

509 -class chaineMot:

510 """ classe représentant une chaine de caractères à laquelle on peut accéder mot par mot 511 ou caractère par caractère 512 le choix se fait à la création avec le param carOuMot 513 si processEnd alors on calcule toute la table de correspondance mot_car 514 sinon on évite ce calcul et il sera fait à la demande avec testMotCar """

515 - def __init__(self, texte, carOuMot, processEnd=False):

516 self.chaine = texte 517 self.carOuMot = carOuMot # mode caractère ou mode mot 518 self.lgCar = len(self.chaine)# longueur en caractères 519 520 if not self.carOuMot: # mode mot 521 self.mot_car = {} # dico indexé par le nième mot et donnant sa place dans la chaine 522 self.mot_car[0] = 0 523 self.car_mot = {} # dico indexé par caractère et retournant le mot auquel ce caractère appartient 524 self.car_mot[0] = 0 525 526 self.max_mot = 0 527 cur_mot = 0 528 cur_car = 1 529 if processEnd: end = self.lgCar 530 else: end = min(10,self.lgCar) 531 while cur_car < end: 532 if (self.chaine[cur_car-1]==' ' or self.chaine[cur_car-1]=='\r\n' or self.chaine[cur_car-1]=='\r' or self.chaine[cur_car-1]=='\n'): 533 cur_mot = cur_mot + 1 534 self.mot_car[cur_mot] = cur_car 535 self.max_mot = cur_mot 536 self.car_mot[cur_car] = cur_mot 537 cur_car = cur_car+1 538 self.lgMot = cur_mot+1 # longueur en mots

539

540 - def testeMotCar(self,pos):

541 # sys.stderr.write("testMotCar "+str(pos)+"\n") # x"+self.chaine+"x /" 542 if pos not in self.mot_car: 543 # for i in self.mot_car: 544 # sys.stderr.write(str(i)+", ") 545 # sys.stderr.write("\n") 546 cur_mot = self.max_mot 547 cur_car = self.mot_car[self.max_mot]+1 548 # sys.stderr.write("cur_mot = "+str(cur_mot)+" / cur_car = "+str(cur_car)+"\n") 549 while cur_mot != pos: 550 # sys.stderr.write("cur_car-1 "+str(cur_car-1)+"\n") 551 if (self.chaine[cur_car-1]==' ' or self.chaine[cur_car-1]=='\r\n' or self.chaine[cur_car-1]=='\r' or self.chaine[cur_car-1]=='\n'): 552 cur_mot+=1 553 self.mot_car[cur_mot] = cur_car 554 self.max_mot = cur_mot 555 self.car_mot[cur_car] = cur_mot 556 cur_car = cur_car+1 557 self.lgMot = cur_mot+1 # longueur en mots

558 # else: 559 # sys.stderr.write(str(pos)+" in str and is "+str(self.mot_car[pos])+"\n") 560 # sys.stderr.write("\n") 561

562 - def printTab(self):

563 for i in self.mot_car: 564 sys.stderr.write(str(i)+":"+str(self.mot_car[i])+" / ") 565 sys.stderr.write(" "+self.toStr()+"\n") 566 sys.stderr.flush()

567

568 - def toStr(self):

569 return self.chaine

570

571 - def slice(self,deb,fin):

572 # slice en caractères ou en mots suivant le mode 573 if (self.carOuMot): 574 return self.chaine[deb:fin] 575 else: 576 # self.testeMotCar(deb) 577 # self.testeMotCar(fin) 578 return self.chaine[self.mot_car[deb]:self.mot_car[fin]]

579

580 - def sliceCar(self,deb,fin) :

581 '''slice uniquement en caractères''' 582 return self.chaine[deb:fin]

583

584 - def sliceM(self, motDeb, carDeb, motFin, carFin):

585 """ si mode mot, slice en prenant le motDeb ième mot + carDeb caractères jusqu'au motFin ième mot + carFin caractères 586 sinon les 2 param mot sont considérés comme exprimés en caractères """ 587 if (self.carOuMot): 588 return self.chaine[motDeb+carDeb:motFin+carFin] 589 else: 590 #self.printTab() 591 # self.testeMotCar(motDeb) 592 #self.printTab() 593 # self.testeMotCar(motFin) 594 #self.printTab() 595 #sys.stderr.write("sliceM "+str(self.mot_car[motDeb]+carDeb)+":"+str(self.mot_car[motFin]+carFin)+"\n") 596 return self.chaine[self.mot_car[motDeb]+carDeb:self.mot_car[motFin]+carFin]

597

598 - def sliceC(self, carDeb, motDeb, carFin, motFin):

599 """ si mode mot, slice en prenant le mot qui correspond au carDeb ième caractère + motDeb mot 600 jusqu'au mot qui correspond au carFin ième caractère + motFin mot 601 sinon les 2 param mot sont considérés comme exprimés en caractères """ 602 if (self.carOuMot): 603 return self.chaine[carDeb+motDeb:carFin+motFin] 604 else: 605 # self.testeMotCar(self.car_mot[carDeb]+motDeb) 606 # self.testeMotCar(self.car_mot[carFin]+motFin) 607 # sys.stderr.write("lengthC = "+str(self.lengthC())+" / lengthM = "+str(self.lengthM())+"\n") 608 # sys.stderr.write("carDeb "+str(carDeb)+" / motDeb "+str(motDeb)+" / carFin "+str(carFin)+" / motFin "+str(motFin)+"\n") 609 # sys.stderr.write("self.car_mot[carDeb] "+str(self.car_mot[carDeb])+" / self.car_mot[carFin]"+str(self.car_mot[carFin])+"\n") 610 # sys.stderr.write("self.mot_car[self.car_mot[carDeb]+motDeb "+str(self.mot_car[self.car_mot[carDeb]+motDeb])+" / self.mot_car[self.car_mot[carFin]+motFin]"+str(self.mot_car[self.car_mot[carFin]+motFin])+"\n") 611 # sys.stderr.write("sliceC = "+self.chaine[self.mot_car[self.car_mot[carDeb]+motDeb]:self.mot_car[self.car_mot[carFin]+motFin]]) 612 return self.chaine[self.mot_car[self.car_mot[carDeb]+motDeb]:self.mot_car[self.car_mot[carFin]+motFin]]

613 614 # à vérifier

615 - def posCarMot(self, carDeb, motDeb):

616 """ renvoie une position en nb de caractères en convertissant carDeb carac + motDeb mots """ 617 if (self.carOuMot): 618 # si mode car les 2 variables sont en caractères 619 return carDeb+motDeb 620 else: 621 # self.testeMotCar(self.car_mot[carDeb]+motDeb) 622 if ((carDeb in self.car_mot) and (self.car_mot[carDeb]+motDeb in self.mot_car)): 623 return self.mot_car[self.car_mot[carDeb]+motDeb] 624 else: 625 return -1

626

627 - def posMotCar(self,motDeb, carDeb):

628 """ renvoie une position en nb de caractères en convertissant motDeb mots + carDeb carac """ 629 if (self.carOuMot): 630 # si mode car les 2 variables sont en caractères 631 return motDeb+carDeb 632 else: 633 # self.testeMotCar(motDeb) 634 return self.mot_car[motDeb]+carDeb

635

636 - def length(self):

637 if (self.carOuMot): return self.lgCar 638 else: return self.lgMot

639

640 - def lengthC(self):

641 """ retourne la longueur en caractères """ 642 return self.lgCar

643

644 - def lengthM(self):

645 if (self.carOuMot): return self.lgCar 646 else: return self.lgMot

647 648 649 650

651 -class dict_chaines:

652 """ remplace le dictionnaire initial: hachage des chaines de facon à ne stocker que 653 les l_hach premiers elements 654 en mode mot, on indexe sur le nb de mots (et plus sur le nombre de car) et 655 sur la chaine de maximum l_hach premiers cararctères (comme en mode normal) et 656 on stocke comme valeurs les occurences en carctères (et pas en mots) """

657 - def __init__(self, l_hachage, texteMot, lg_texte1, carOuMot):

658 self.texteMot = texteMot 659 self.lg_texte1 = lg_texte1 660 self.l_hachage = l_hachage 661 self.carOuMot = carOuMot 662 self.E = {} 663 self.initialise()

664 #print "Fin de l'initialisation du dictionnaire" 665

666 - def initialise(self):

667 self.E[1]={} 668 i=0 669 # parcours de tout le texte pout initialiser le dictionnaire 670 # avec toutes les chaines de longueur 1 671 while i < self.texteMot.length()-1: 672 self.ajout_occ(chaineMot(self.texteMot.slice(i,i+1),self.carOuMot, True), self.texteMot.posMotCar(i,0)) 673 i=i+1

674

675 - def ajout_occ(self, ch, i):

676 """ ajoute une occurence i de ch au dictionnaire 677 ch doit être de type chaineMot """ 678 #sys.stderr.write("ajout_occ de _"+ch.toStr()+"_"+str(ch.length())+"\n") 679 #sys.stderr.flush() 680 #ln = len(ch) 681 ln = ch.length() 682 # crée un nouveau dict comme valeur de E[ln] 683 if ln not in self.E: 684 self.E[ln] = {} 685 # crée un nouveau dict comme valeur de E[ln][ch[0:l_hachage]] 686 #if ch[0:self.l_hachage] not in self.E[ln]: 687 if ch.sliceCar(0,self.l_hachage) not in self.E[ln]: 688 #if ch.toStr() not in self.E[ln]: 689 #self.E[ln][ch[0:self.l_hachage]] = { } 690 self.E[ln][ch.sliceCar(0,self.l_hachage)] = {} 691 #self.E[ln][ch.toStr()] = { } 692 occ = self.occ_chaine(ch) 693 if occ == []: 694 #self.E[ln][ch[0:self.l_hachage]][i]=[i] 695 self.E[ln][ch.sliceCar(0,self.l_hachage)][i]=[i] 696 #self.E[ln][ch.toStr()][i]=[i] 697 else: 698 #self.E[ln][ch[0:self.l_hachage]][occ].append(i) 699 self.E[ln][ch.sliceCar(0,self.l_hachage)][occ].append(i)

700 #sys.stderr.write(str(occ)+"\n") 701 #self.E[ln][ch.toStr()][occ].append(i) 702

703 - def ajout_occs(self, ch, L_occs):

704 """ajoute une liste d'occurences à ch 705 ch doit être de type chaineMot """ 706 #sys.stderr.write("ajout_occ de _"+ch.toStr()+"_"+str(ch.length())+"\n") 707 #sys.stderr.flush() 708 #ln = len(ch) 709 ln = ch.length() 710 if ln not in self.E: 711 self.E[ln] = {} 712 #if ch[0:self.l_hachage] not in self.E[ln]: 713 # self.E[ln][ch[0:self.l_hachage]] = {} 714 if ch.sliceCar(0,self.l_hachage) not in self.E[ln]: 715 self.E[ln][ch.sliceCar(0,self.l_hachage)] = {} 716 occ = self.occ_chaine(ch) 717 if occ == []: 718 occ = L_occs[0] 719 #self.E[ln][ch[0:self.l_hachage]][occ] = [] 720 self.E[ln][ch.sliceCar(0,self.l_hachage)][occ] = [] 721 for i in L_occs: 722 #self.E[ln][ch[0:self.l_hachage]][occ].append(i) 723 self.E[ln][ch.sliceCar(0,self.l_hachage)][occ].append(i)

724

725 - def occ_chaine(self, ch):

726 """ ch doit être de type chaineMot 727 si la chaine ch se trouve dans le dictionnaire, renvoie sa première 728 occurrence associee qui est la clé pour accéder à sa liste d'occurences 729 sinon, renvoie [] """ 730 #ln = len(ch) 731 ln = ch.length() 732 G = self.E.get(ln) 733 if not G: 734 return [] 735 #H = G.get(ch[0:self.l_hachage]) 736 H = G.get(ch.sliceCar(0,self.l_hachage)) 737 if not H: 738 return [] 739 if (self.carOuMot and ln < self.l_hachage): 740 #if (ln < self.l_hachage): 741 return H.keys()[0] 742 else: 743 # recherche de ch parmi les chaines de taille ln indéxées avec ch[0:self.l_hachage] 744 for occ in H: 745 #if self.texte[occ:occ+ln] == ch: 746 if self.texteMot.sliceC(occ,0,occ,ln) == ch.toStr(): 747 return occ

748 749

750 - def occs_chaine(self, ch):

751 """ renvoie la liste des occurences de la chaine associée à la chaine ch """ 752 #k = len(ch) 753 k = ch.length() 754 #H = self.E.get(k).get(ch[0:self.l_hachage]) 755 H = self.E.get(k).get(ch.sliceCar(0,self.l_hachage)) 756 if not H: 757 return [] 758 if (self.carOuMot and k < self.l_hachage): 759 return H.values()[0] 760 else: 761 #return self.E.get(k).get(ch[0:self.l_hachage]).get(self.occ_chaine(ch)) 762 return self.E.get(k).get(ch.sliceCar(0,self.l_hachage)).get(self.occ_chaine(ch)) 763 return []

764

765 - def toutes_occ_chaines_it(self, k, radical):

766 """ Retourne la liste des occurences de la chaine de longueur k d'index radical 767 dans le texte. L'index a une taille inférieur à self.l_hachage qui peut etre inférieure à k """ 768 G = self.E.get(k).get(radical) 769 if G: 770 return self.E.get(k).get(radical).iterkeys() 771 else: return []

772

773 - def tous_radicaux_iteration(self,k):

774 """ Retourne la liste des index-chaines (ou radicaux) de longueur k """ 775 G = self.E.get(k) 776 if G: 777 return self.E.get(k).iterkeys() 778 else: return []

779

780 - def nettoyer_radical(self, k, radical):

781 """ Parcours les listes d'occurences associées à un radical 782 Si parmi ces listes, une est vide ou ne possède pas de répétitions 783 entre le texte1 et le texte2 alors supprimer cette liste d'occurences """ 784 for occ in self.toutes_occ_chaines_it(k, radical): 785 if not self.repetition(self.E.get(k).get(radical)[occ]): 786 del self.E.get(k).get(radical)[occ] 787 if self.E.get(k)[radical] == { }: 788 del self.E.get(k)[radical]

789

790 - def repetition(self, Locc):

791 """ Teste si la liste d'occurrences Locc mentionne des occurrences répétitives """ 792 return (Locc <> [] and (Locc[0] < self.lg_texte1) and (Locc[-1] >= self.lg_texte1))

793

794 - def eliminer_toutes_occurrences(self, ch):

795 """ supprime la liste d'occurence d'une chaine ch 796 ch est de type chaineMot """ 797 #k = len(ch) 798 k = ch.length() 799 #G = self.E.get(k).get(ch[0:self.l_hachage]) 800 G = self.E.get(k).get(ch.sliceCar(0,self.l_hachage)) 801 if G: 802 #del self.E.get(k).get(ch[0:self.l_hachage])[self.occ_chaine(ch)] 803 del self.E.get(k).get(ch.sliceCar(0,self.l_hachage))[self.occ_chaine(ch)] 804 #self.nettoyer_radical(k, ch[0:self.l_hachage]) 805 self.nettoyer_radical(k, ch.sliceCar(0,self.l_hachage))

806

807 - def etat_dict(self):

808 sys.stderr.write( "Impression etat dictionnaire\n") 809 for k in self.E: 810 nbre = len(self.E[k]) 811 if nbre != -1: 812 sys.stderr.write("k = "+ str(k)+ " nombre chaines: "+ str(nbre) +"\n") 813 # if k>1: 814 # for x in self.E[k]: 815 # sys.stderr.write("E("+str(k)+") = "+x+"\n") 816 sys.stderr.flush()

817 818

819 -class stockage_chaines_optimales:

820 """ C'est là une classe qui contient, dans un dictionnaire toutes les chaînes 821 optimales. Plus exactement, chaque chaine est repérée par son occurrence sur 822 le texte (l'occurrence de rang inférieur pour être plus précis), et par 823 l'occurrence de la fin de la chaîne. Cette classe est utilisée par la fonction 824 "blocs_maximaux" """ 825

826 - def __init__(self, Dict, texte, lg_texte1, carOuMot, long_min_pivots):

827 """ L'initialisation se fait à l'aide du dictionnaire qui comprend l'ensemble des 828 fragments répétés et de la longueur du premier texte. """ 829 self.tool = Utile() 830 # chaines_optimales: [0..lg] à chaque case i correspond la position du dernier caracctère 831 # du bloc auquel appartient la position i 832 self.chaines_optimales = { } 833 # occs_optimales : [0..lg] à chaque case i correspond la liste des blocs identiques 834 # au bloc auquel appartient cette case i 835 self.occs_optimales = { } # 16 aout 2004 836 self.clefs = self.tool.non_nul_keys(Dict.E) 837 self.clefs.sort() 838 self.clefs.reverse() 839 self.lg_texte1 = lg_texte1 840 self.lg = len(texte) 841 self.texte = texte 842 self.carOuMot = carOuMot 843 self.long_min_pivots = long_min_pivots 844 for i in range(0, self.lg): 845 self.chaines_optimales[i] = i 846 self.occs_optimales[i] = [] 847 # sys.stderr.write("1 self.chaines_optimales = "+str(self.chaines_optimales)+"\n") 848 # sys.stderr.write("1 self.occs_optimales = "+str(self.occs_optimales)+"\n") 849 self.construire_chaines_optimales(Dict) 850 #for clef in self.clefs: 851 # Dict.E[clef]= {} 852 #Dict = {} 853 # sys.stderr.write("2 self.chaines_optimales = "+str(self.chaines_optimales)+"\n") 854 # sys.stderr.write("2 self.occs_optimales = "+str(self.occs_optimales)+"\n") 855 self.allonger_chaines_i(0) 856 # sys.stderr.write("3 self.chaines_optimales = "+str(self.chaines_optimales)+"\n") 857 # sys.stderr.write("3 self.occs_optimales = "+str(self.occs_optimales)+"\n") 858 self.stockage_chaines(texte)

859 #self.blocs_texte.sort() 860 # for x in self.blocs_texte: 861 # sys.stderr.write(x+" "+str(self.blocs_texte[x])+"\n") 862 # A l'issue de l'initialisation, les chaînes optimales sont stockées 863 # dans la variable "blocs_texte" 864

865 - def occ_sous_optimale(self, occ, chaine):

866 return (self.chaines_optimales[occ] >= occ + len(chaine))

867 # Teste si l'occurrence "occ" de la chaîne "chaine" 868 # est incluse dans l'une des chaînes optimales 869

870 - def repetition(self, Locc):

871 # Teste si la liste d'occurrences Locc mentionne des occurrences répétitives 872 return (Locc <> [] and (Locc[0] < self.lg_texte1) and (Locc[-1] >= self.lg_texte1))

873

874 - def ajout_occs(self, Locc, ln):

875 # Ajoute les occurrences de "chaine" de taille ln contenues dans "Locc" 876 N=0 877 #sys.stderr.write( "Appel ajout_occs" +str(Locc)+ "; lg="+str(ln)+"\n") 878 LLocc = Locc[:] 879 while LLocc: 880 O = LLocc[0] 881 while O < LLocc[0]+ln and self.chaines_optimales[O] < LLocc[0]+ln: 882 N=1 883 self.chaines_optimales[O] = LLocc[0] + ln 884 self.occs_optimales[O] = Locc 885 O = O+1 886 #self.allonger_chaines(LLocc[0]) 887 LLocc = LLocc[1:] 888 return N

889 890 # Impression etat dictionnaire 891 #k = 32 nombre chaines: 169 892 #k = 1 nombre chaines: 5 893 #k = 4 nombre chaines: 4 894 #k = 1024 nombre chaines: 2256 895 #k = 8 nombre chaines: 25 896 #k = 64 nombre chaines: 611 897 #k = 128 nombre chaines: 1060 898 #k = 256 nombre chaines: 1892 899 #k = 16 nombre chaines: 126 900 #k = 512 nombre chaines: 3539

901 - def construire_chaines_optimales(self, Dict):

902 clefs = self.clefs 903 while clefs <> []: 904 # sys.stderr.write("clef[0]= "+str(clefs[0])+"\n") 905 # tous les radicaux de longueur clefs[0] 906 for radical in Dict.tous_radicaux_iteration(clefs[0]): 907 # toutes les occurences de ce radical 908 for occ in Dict.toutes_occ_chaines_it(clefs[0], radical): 909 Loccs = [] #Dict[clefs[0]][chaine][:] 910 #chaine = Dict.texte[occ:occ+clefs[0]] 911 # texte correspondant à cette occurence et de longueur clefs[0] 912 chaine = chaineMot(Dict.texteMot.sliceC(occ,0,occ,clefs[0]), self.carOuMot,True) 913 # sys.stderr.write("Chaine à l'étude: "+ chaine.toStr()+"\n") 914 # pour toutes les occurencs de chaine 915 for occ_ch in Dict.occs_chaine(chaine): 916 if not self.occ_sous_optimale(occ_ch, chaine.toStr()): 917 Loccs.append(occ_ch) 918 #Loccs.append(occ_ch) 919 if self.repetition(Loccs): 920 #self.ajout_occs(Loccs, len(chaine)) 921 self.ajout_occs(Loccs, chaine.lengthC()) 922 clefs = clefs[1:]

923 #print "Fin de la transcription du dictionnaire" 924

925 - def allonger_chaines_i(self, Occ):

926 #position du dernier carac du bloc auquel appartient Occ 927 NOcc = self.chaines_optimales[Occ] 928 if NOcc == Occ: 929 NOcc = Occ + 1 930 i=0 931 while ((Occ < self.lg_texte1 and NOcc < self.lg_texte1) 932 or (Occ >= self.lg_texte1 and NOcc < self.lg)): 933 # sys.stderr.write("Appel allonger chaines sur '"+ self.texte[Occ:NOcc]+"'\n") 934 while self.allonger_chaines_(Occ): 935 #print self.chaines_optimales.values() 936 pass 937 Occ += 1 #NOcc # passage au bloc suivant 938 NOcc = self.chaines_optimales[Occ] # denier car du boc 939 if NOcc == Occ: 940 NOcc = Occ + 1 941 i+=1

942 # sys.stderr.write("compt allonger_chaines_i = "+ str(i)+"\n") 943

944 - def allonger_chaines_(self, Occ):

945 Occ_fin = self.chaines_optimales[Occ] 946 NOcc = Occ 947 while (NOcc < self.lg and 948 self.repetition(self.occs_optimales[NOcc]) and 949 not self.chaines_optimales[NOcc] > Occ_fin): 950 NOcc = NOcc + 1 951 # sys.stderr.write("NOcc = "+str(NOcc)+" / ") 952 if NOcc >= self.lg: 953 NOcc = self.lg - 1 954 Occ_fin = self.lg 955 else: Occ_fin = self.chaines_optimales[NOcc] 956 LOcc = self.tool.composition_decalee_(self.occs_optimales[Occ], self.occs_optimales[NOcc], NOcc - Occ) 957 # sys.stderr.write("allonger chaines; LOcc= " +str(LOcc)+" / Occ = "+str(Occ)+" / NOcc = "+str(NOcc)+" / Occ_fin = "+str(Occ_fin)+"\n") 958 # sys.stderr.write("Occs gauche: "+str(self.occs_optimales[Occ])+"; chaine: '"+ self.texte[Occ:self.chaines_optimales[Occ]]+ "'\n") 959 # sys.stderr.write("Occs droites: "+str(self.occs_optimales[NOcc])+"; chaine: '"+ self.texte[NOcc:self.chaines_optimales[NOcc]]+ "'\n") 960 # sys.stderr.write("Decalage: "+str( NOcc - Occ)+"\n") 961 if self.repetition(LOcc): 962 # sys.stderr.write("ajout_occs:'"+ self.texte[Occ:Occ_fin]+ "' " +str(LOcc)+"\n\n") 963 return self.ajout_occs(LOcc, Occ_fin - Occ) 964 else: 965 # sys.stderr.write("\n") 966 return 0

967 968 # def sto(self): 969 # self.stockage_chaines(e.texte, e.E) 970

971 - def stockage_chaines(self, texte):

972 d = 0 973 f = 0 974 self.blocs_texte = {} # stockage des blocs optimaux dans un dictionnaire 975 while d < len(self.chaines_optimales): 976 if f <> self.chaines_optimales[d] : 977 f = self.chaines_optimales[d] 978 if (f-d >= self.long_min_pivots): 979 #self.blocs_texte[texte[d:f]] = Dict[f-d][texte[d:f]] 980 if self.blocs_texte.has_key(texte[d:f]): 981 self.blocs_texte[texte[d:f]].append(d) 982 else: self.blocs_texte[texte[d:f]] = [d] 983 # sys.stderr.write( "chaine: "+ texte[d:f]+ "; rang:"+ str(d)+"\n") 984 d = d+1

985 986

987 -def test_miroir():

988 tool = Utile() 989 locc = [(10,20),(40,45),(42,60)] 990 LRes = tool.miroir(locc,0,100)

991 992 if __name__ == '__main__': 993 test_miroir() 994

Source Code for Module medite.MediteAppli.utile