medite.MediteAppli.MediteAppli

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 # Nom: MediteAppli.py 20 #---------------------------------------------------------------------------- 21 22 import sys, time,logging, gc 23 #from time import clock, localtime, gmtime, strftime 24 from math import * 25 import profile,traceback,pstats,bisect 26 import string 27 import suffix_tree 28 import alignement 29 import utile 30 from Donnees.resultatAppli import Resultat 31 import synthetic 32 #from caseless import dictFactory 33 #from ft.xml.domlette import NonvalidatingReader 34 #doc = NonvalidatingReader.parseUri("http://xmlhack.com/read.php?item=1560") 35 #from Numeric import array, Float, ones, zeros, cumsum, searchsorted, \ 36 # argmax, multiarray, reshape, add, allclose, floor, where, \ 37 # product, sqrt, dot, multiply, alltrue, log, Int,equal,NewAxis,take 38 # Seules variables globales: longueur minimale des chaines pivots (et deplacees) 39 # ratio minimal de longueur des chaines pour valider un remplacement 40 # et seuil du rapport de longueur des chaines pour valider un lissage 41 global long_min_pivots 42 global ratio_min_remplacement 43 global ratio_seuil_lissage 44 45 46

47 -def transDiacritic(txt):

48 sepTable = string.maketrans("çéèàùâêîôûäëïöüÿÇÉÈÀÙÂÊÎÔÛÄËÏÖÜ","ceeauaeiouaeiouyCEEAUAEIOUAEIOU") 49 return txt.translate(sepTable)

50 51

52 -class ecartTextes(object):

53 - def __init__(self, chaine1, chaine2, pP1, pP2, pP3, carOuMot, caseSensitive, separatorSensivitive, diacriticSensitive, planTravail,algoAligneur=''):

54 self.tool = utile.Utile() 55 ## Les parametres 56 global long_min_pivots 57 global ratio_min_remplacement 58 global ratio_seuil_lissage 59 self.algoAligneur = algoAligneur # choix de l'algo, par défaut Astar 60 61 62 long_min_pivots = pP1 63 ratio_min_remplacement = pP2 64 ratio_seuil_lissage = pP3 65 self.carOuMot = carOuMot 66 self.caseSensitive = caseSensitive 67 self.separatorSensivitive = separatorSensivitive 68 self.diacriticSensitive = diacriticSensitive 69 self.texte1 = chaine1 70 self.texte2 = chaine2 71 self.texte_original = self.texte1 + self.texte2 72 self.texte1_original = self.texte1 73 self.texte2_original = self.texte2 74 self.planTravail = planTravail 75 76 # uniformisation entre espaces et espaces insécables ALT+0160 77 # transfo des espaces insécables en espcaces 78 self.sepTable = string.maketrans(" "," ") 79 self.texte1 = self.texte1.translate(self.sepTable) 80 self.texte2 = self.texte2.translate(self.sepTable) 81 82 if not self.diacriticSensitive: 83 self.sepTable = string.maketrans("çéèàùâêîôûäëïöüÿÇÉÈÀÙÂÊÎÔÛÄËÏÖÜ","ceeauaeiouaeiouyCEEAUAEIOUAEIOU") 84 self.texte1 = self.texte1.translate(self.sepTable) 85 self.texte2 = self.texte2.translate(self.sepTable) 86 87 if not self.caseSensitive: 88 # si comparaison insensible à la casse, on convertit les 2 chaines en minuscule 89 self.texte1 = self.texte1.lower() 90 self.texte2 = self.texte2.lower() 91 92 if not self.separatorSensivitive: 93 # si insensible aux séparateurs, on convertit tous les séparateurs en point 94 self.sepTable = string.maketrans(""" !\r,\n:\t;-?"'`’()""","................") 95 self.texte1 = self.texte1.translate(self.sepTable) 96 self.texte2 = self.texte2.translate(self.sepTable) 97 # chaque clé est une position du texte original ou un séparateur a été supprimé 98 self.dictPosSuppression={} 99 # à chaque position du nouveau texte est associé le nb de suppression 100 # de séparateur jusqu'à cette position 101 self.tabNbSuppression={} 102 self.texte1,self.texte2=self.preTraitSuppSep(self.texte1,self.texte2) 103 #print self.dictPosSuppression 104 #print self.tabNbSuppression 105 #sys.stderr.write("self.tabNbSuppression = "+str(self.tabNbSuppression)+"\n") 106 #sys.stderr.write("self.dictPosSuppression = "+str(self.dictPosSuppression)+"\n") 107 108 #self.texte = self.texte1 + self.texte2 # texte intégral 109 self.lg_texte1 = len(self.texte1) # longueur texte antérieur 110 self.lg_texte2 = len(self.texte2) # longueur texte postérieur 111 self.lg_texte = self.lg_texte1 + self.lg_texte2 112 #print "##"+self.texte1+"**" 113 #print "##"+self.texte2+"**" 114 sys.stdout.flush() 115 #logging.debug('t1='+self.texte1) 116 #logging.debug('t2='+self.texte2) 117 # dictionnaire contenant l'ensemble des fragments répétés 118 # ce dictionnaire est indexé par la longueur des fragments 119 # puis par les fragments eux-mêmes. En regard, on trouve les 120 # occurrences d'apparition de ces fragments 121 self.blocs_texte = {} 122 123 sys.stderr.flush() 124 self.insertions = [] 125 self.suppressions = [] 126 self.identites = [] 127 128 self.occs_texte1 = [] 129 self.occs_texte2 = [] 130 self.occs_deplaces = [] 131 self.occs_remplacements = [] 132 self.blocs_remplacements = [] 133 self.tous_remplacements = []

134 #self.Dict.etat_dict() 135 #sys.stderr.write( 'done init\n') 136 #sys.stderr.flush() 137

138 - def preTraitSuppSep(self,texte1,texte2):

139 """ Prétraitement supprimant plusieurs séparateurs se suivant et n'en laissant qu'un 140 Prend en entrée texte1 et texte2 et les renvoie traités """ 141 debut=0 142 j=0 143 comptSuppression=0 144 res=[] 145 for texte in [texte1,texte2]: 146 i=0 147 lTexte=[] 148 while i<len(texte)-1: 149 if texte[i]=='.' and texte[i+1]=='.': 150 comptSuppression+=1 151 # position du texte original ou un séparateur a été supprimé 152 self.dictPosSuppression[i+debut]='.' 153 else: 154 lTexte.append(texte[i]) 155 # à chaque position du nouveau texte est associé le nb de suppression 156 # de séparateur jusqu'à cette position 157 self.tabNbSuppression[j]=comptSuppression 158 j+=1 159 i+=1 160 lTexte.append(texte[i]) 161 self.tabNbSuppression[j]=comptSuppression 162 j+=1 163 debut=i+1 164 res.append(''.join(lTexte)) # chaine 165 self.tabNbSuppression[j]=comptSuppression 166 return res[0],res[1]

167

168 - def postTraitSuppSep2(self,listeOcc):

169 res=[] 170 for (occ1,occ2) in listeOcc: 171 #print (occ1,occ2) 172 Nocc1 = occ1+self.tabNbSuppression[occ1] 173 Nocc2 = occ2+self.tabNbSuppression[occ2] 174 #len_bloc=occ2-occ1 175 #i=0 176 #nbSup=0 177 #while i<(len_bloc+nbSup): 178 # if self.dictPosSuppression.has_key(Nocc1+i): 179 # nbSup+=1 180 # i+=1 181 #assert(Nocc2==Nocc1+len_bloc+nbSup) 182 #res.append((Nocc1,Nocc1+len_bloc+nbSup)) 183 res.append((Nocc1,Nocc2)) 184 #print res 185 return res

186

187 - def postTraitSuppSep(self):

188 self.insertions = self.postTraitSuppSep2(self.insertions) 189 self.suppressions = self.postTraitSuppSep2(self.suppressions) 190 self.occs_deplaces = self.postTraitSuppSep2(self.occs_deplaces) 191 self.tous_remplacements = self.postTraitSuppSep2(self.tous_remplacements) 192 self.blocsCommuns = self.postTraitSuppSep2(self.blocsCommuns) 193 res=[] 194 for b in self.lDepl: 195 res.append(self.postTraitSuppSep2(b)) 196 self.lDepl=res 197 198 #self.texte1_no_sep = self.texte1 199 #self.texte2_no_sep = self.texte2 200 #self.texte_no_sep = self.texte 201 #self.lg_texte1_no_sep = self.lg_texte1 202 #self.lg_texte2_no_sep = self.lg_texte2 203 204 self.texte1 = self.texte1_original 205 self.texte2 = self.texte2_original 206 #self.texte = self.texte_original 207 self.lg_texte1 = len(self.texte1) 208 self.lg_texte2 = len(self.texte2)

209

210 - def toString(self):

211 return ("EcartTextes : long_min_pivots = "+str(long_min_pivots)+ 212 " / ratio_min_remplacement = "+str(ratio_min_remplacement)+ 213 " / ratio_seuil_lissage = "+str(ratio_seuil_lissage)+ 214 "\ntexte1 = "+str(self.texte1)+ 215 "\ntexte2 = "+str(self.texte2))

216

217 - def blocs_maximaux(self):

218 self.D = utile.stockage_chaines_optimales(self.Dict, self.texte, self.lg_texte1,self.carOuMot,long_min_pivots) 219 self.blocs_texte = self.D.blocs_texte 220 i=0 221 nbcar=0 222 nbocc=0 223 for bloc in self.blocs_texte: 224 # sys.stderr.write("B2 "+bloc+"\n") 225 nbcar += len(bloc) 226 nbocc += len(self.blocs_texte[bloc]) 227 i+=1

228 # sys.stderr.write("nbCarMoy = "+str(nbcar/i)+" / nbOccMoy = "+str(nbocc/i)+"\n") 229 # sys.stderr.write("blocs_texte ="+ str(self.blocs_texte)+"\n") 230 231 # def postTraitSuppSep(self): 232 # sys.stderr.write(u"Entrée postTraitSuppSep\n") 233 # sys.stderr.flush() 234 # if self.separatorSensivitive: 235 # # tous les occurences ont la meme taille len(bloc) 236 # for bloc in self.blocs_texte: 237 # len_bloc=len(bloc) 238 # locc2=[] 239 # for occ in self.blocs_texte[bloc]: 240 # locc2.append((occ,len_bloc)) 241 # self.blocs_texte[bloc]=locc2 242 # else: 243 # for bloc in self.blocs_texte: 244 # locc=[] 245 # for occ in self.blocs_texte[bloc]: 246 # locc.append(occ+self.tabNbSuppression[occ]) 247 # nbSup={} 248 # locc2=[] 249 # len_bloc=len(bloc) 250 # for occ in locc: 251 # i=0 252 # nbSup[occ]=0 253 # while i<(len_bloc+nbSup[occ]): 254 # if self.dictPosSuppression.has_key(occ+i): 255 # nbSup[occ]+=1 256 # i+=1 257 # locc2.append((occ,len_bloc+nbSup[occ])) 258 # self.blocs_texte[bloc]=locc2 259 260 # for bloc in self.blocs_texte: 261 # sys.stderr.write("bloc2 "+bloc) 262 # for occ,len_occ in self.blocs_texte[bloc]: 263 # sys.stderr.write(" / "+self.texte[occ:occ+len_occ]) 264 # sys.stderr.write("\n") 265

266 - def construction_equivalence_double_opt(self,a) :

267 """calcul optimise de E[a+a] * partir de E[a] 268 notons qu'au cours de ce calcul, on élimine de E[a] les 269 occurrences i qui appartiennent * E[a+a] car le but est 270 d'obtenir les sous-structures répétitives de taille maximale """ 271 272 # boucle sur toutes les chaines de taille a 273 for radical in self.Dict.tous_radicaux_iteration(a): 274 # boucle sur toutes les occurences de radical 275 for oc_chaine in self.Dict.toutes_occ_chaines_it(a, radical): 276 # chaine réelle 277 chaine = utile.chaineMot(self.texteMot.sliceC(oc_chaine, 0, oc_chaine, a), self.carOuMot,True) 278 #for chaine in self.Dict.toutes_chaines_lg(a): 279 # renvoie toutes les occurences de la chaine réelle 280 occs = self.Dict.occs_chaine(chaine) 281 # sys.stderr.write( "chaine initiale: "+ chaine.toStr()+ "/ occs: ") 282 # for l in occs: sys.stderr.write (str(l)+", ") 283 # sys.stderr.write("\n") 284 # Tq liste!=[] et on est dans le 1er texte 285 #while occs and occs[0]+a+a < self.lg_texte1: 286 # vérifier 2e condition d'arrêt, pas de débordement ? 287 #sys.stderr.write("self.lg_texte1 "+str(self.lg_texte1)+"\n") 288 #currentPos = self.texteMot.posCarMot(occs[0], a+a) 289 # -1 < est la condition d'arrêt pour le mode mot et > lg_texte1 pour le mode caractère 290 while (occs and ( -1 < self.texteMot.posCarMot(occs[0], a+a) < self.texteMot1.lengthC())): 291 occ = occs[0] # 1e occ de la liste actuelle 292 #n_chaine = self.texte[occ:occ+a+a] # nouvelle chaine de taille 2a 293 # sys.stderr.write( "n_chaine = "+self.texte[occ:occ+a+a]) 294 n_chaine = utile.chaineMot(self.texteMot.sliceC(occ, 0, occ, a+a), self.carOuMot, True) 295 # sys.stderr.write( "n_chaine = "+n_chaine.toStr()) 296 # n_chaine.printTab() 297 #sys.stderr.write(" Composition: _"+n_chaine.sliceM(0,0,a,0)+"_ / _"+n_chaine.sliceM(a,0,0,n_chaine.lengthC())+"_\n") 298 # si nouvelle chaine non présente dans dico 299 if not self.Dict.occ_chaine(n_chaine) : 300 #sys.stderr.write( n_chaine.toStr()+"not in dico \n") 301 #n_chaine.printTab() 302 # occurences de la 2e moitié de la nouvelle chaine 303 #occs_suite = self.Dict.occs_chaine(n_chaine[a:]) 304 occs_suite = self.Dict.occs_chaine(utile.chaineMot(n_chaine.sliceM(a,0,0,n_chaine.lengthC()),self.carOuMot, True)) 305 if occs_suite and not self.carOuMot: # mode mot 306 l_aux=self.tool.composition_decalee_mot(occs,occs_suite,a,self.texteMot) 307 elif occs_suite and (len(occs_suite) > 5 or len(occs) > 7): 308 l_aux=self.tool.composition_decalee_b(occs,occs_suite,a) 309 else: l_aux=self.tool.composition_decalee_(occs,occs_suite,a) 310 # l_aux contient la liste des occurences de taille 2a 311 # enlève de occs les éléments de l_aux 312 occs = self.tool.difference(occs[1:],l_aux) 313 # si 2 occs de la même chaine, une dans chaque texte 314 if self.repetition(l_aux): 315 # ajout de la nouvelle chaine au dico 316 self.Dict.ajout_occs(n_chaine, l_aux) 317 else: occs = occs[1:] 318 319 #self.Dict.nettoyer(a+a) 320 for radical in self.Dict.tous_radicaux_iteration(a+a): 321 for oc_chaine in self.Dict.toutes_occ_chaines_it(a+a, radical): 322 #chaine = self.texte[oc_chaine:oc_chaine+a+a] 323 chaine = utile.chaineMot(self.texteMot.sliceC(oc_chaine,0,oc_chaine,a+a),self.carOuMot,True) 324 #for chaine in self.Dict.toutes_chaines_lg(a+a): 325 chaine0a = utile.chaineMot(chaine.sliceC(0,0,0,a),self.carOuMot,True) 326 occs_chaine_chaine = self.Dict.occs_chaine(chaine) 327 if not self.repetition(self.tool.difference(self.Dict.occs_chaine(chaine0a), 328 occs_chaine_chaine)): 329 self.Dict.eliminer_toutes_occurrences(chaine0a) 330 chainea2a = utile.chaineMot(chaine.sliceM(a,0,0,chaine.lengthC()),self.carOuMot,True) 331 if not self.carOuMot and not self.repetition(self.tool.composition_decalee_mot(self.Dict.occs_chaine(chainea2a), 332 occs_chaine_chaine, 333 a,self.texteMot)): 334 self.Dict.eliminer_toutes_occurrences(chainea2a) 335 elif not self.repetition(self.tool.composition_decalee_b(self.Dict.occs_chaine(chainea2a), 336 occs_chaine_chaine, 337 a)): 338 self.Dict.eliminer_toutes_occurrences(chainea2a)

339 #self.Dict.nettoyer(a) 340

341 - def construction_blocs_maximaux1(self) :

342 debut=time.clock() 343 self.texteMot1 = utile.chaineMot(self.texte1, carOuMot, True) 344 self.texteMot2 = utile.chaineMot(self.texte2, carOuMot, True) 345 self.texteMot = utile.chaineMot(self.texte, carOuMot, True) 346 #self.texteMot.printTab() 347 self.Dict = utile.dict_chaines(260, self.texteMot, self.lg_texte1, self.carOuMot) 348 k = 1 # initialisation de la relation d'Equivalence: E[1] -> motifs de longueur 1 349 350 # dEbut de la boucle sur k... construire la relation E pour les puissances de 2 351 #while 2*k <= min(self.lg_texte1, self.lg_texte2) : 352 while 2*k <= min(self.texteMot1.lengthM(), self.texteMot2.lengthM()) : 353 # sys.stderr.write( "Construction de la classe d'Equivalence pour 2*"+str(k)+"\n") 354 #self.construction_equivalence_double_opt_quart(k) 355 self.construction_equivalence_double_opt(k) 356 #self.Dict.etat_dict() 357 #self.eliminer_blocs_inutiles(k) 358 #print "Nombre d'ElEments dans la classe 2*", k, ": ", len(non_nul_keys(self.E[2*k])) 359 k = 2*k 360 #print "fin de la construction des puissances de 2" 361 362 # construction de la relation d'Equivalence pour les autres nombres 363 #while k >= 1 : 364 # if not self.toutes_occurrences_couvertes(k, k) : 365 # self.ajustage(k, k) 366 # k = k/2 367 #print "fin de l'ajustage" 368 #self.ajustage_() 369 #print "fin de l'ajustage" 370 #self.Dict.etat_dict() 371 # enfin, calcul des blocs maximaux... 372 self.blocs_maximaux() 373 # for x in self.blocs_texte: 374 # sys.stderr.write(x+" "+str(self.blocs_texte[x])+"\n") 375 sys.stderr.write("construction blocs max = "+str(time.clock()-debut)+"\n") 376 sys.stderr.write("Nombre de blocs maximaux avant elimination recouvrements:"+ str(len(self.blocs_texte))+"\n") 377 self.debut=time.clock() 378 self.d1=self.blocs_texte 379 # elimination des recouvrements entre blocs 380 # sys.stderr.write("Nombre de blocs maximaux:"+str(len(self.blocs_texte))+"\n") 381 recouv = Recouvrement(self.texte,self.blocs_texte,self.lg_texte1) 382 self.blocs_texte = recouv.eliminer_recouvrements() 383 # for x in self.blocs_texte: 384 # sys.stderr.write(x+" "+str(self.blocs_texte[x])+"\n") 385 sys.stderr.write("Nombre de blocs maximaux apres elimination recouvrements:"+ str(len(self.blocs_texte))+"\n") 386 #self.postTraitSuppSep() 387 # Et, pour finir, remplissage des trous par des ajouts 388 # ou des suppressions 389 self.completer_blocs_m() 390 sys.stderr.write("completer_blocs_m done:"+ str(len(self.blocs_texte))+"\n") 391 sys.stderr.flush() 392 # for x in self.blocs_texte: 393 # sys.stderr.write(x+" "+str(self.blocs_texte[x])+"\n") 394 nbx=nby=0 395 for x in self.blocs_texte: 396 nbx+=1 397 for y in self.blocs_texte[x]: 398 nby+=1 399 sys.stderr.write("nbx:+"+str(nbx)+" / nby:"+str(nby)+"\n")

400

401 - def construction_blocs_maximaux(self) :

402 #self.construction_blocs_maximaux1() 403 404 self.construction_blocs_maximaux2()

405 # i=0 406 # for x in self.d2: 407 # if not self.d1.has_key(x): 408 # sys.stderr.write(x+" "+str(self.d2[x])+"\n") 409 # i+=1 410 # sys.stderr.write("nb= "+str(i)+"\n") 411

412 - def clean_bt(self):

413 dic={} 414 i=0 415 for x in self.blocs_texte: 416 if len(x)<long_min_pivots or len(self.blocs_texte[x])<2: 417 pass 418 # elif len(x)<long_min_pivots: 419 # #sys.stderr.write("Bloc "+x+ " inf long_min_pivots\n") 420 # pass 421 # elif len(self.blocs_texte[x])<2: 422 # #sys.stderr.write("Bloc "+x+ " inf 2\n") 423 # pass 424 else: 425 dic[x]=self.blocs_texte[x] 426 sys.stderr.write("Bloc "+x+ " " +str(dic[x])+" "+str(len(self.blocs_texte[x]))+"\n") 427 i+=1 428 sys.stderr.write("nb= "+str(i)+"\n") 429 self.blocs_texte=dic

430

431 - def construction_blocs_maximaux2(self) :

432 debut=time.clock() 433 sequences = [self.texte1, self.texte2] 434 st = suffix_tree.GeneralisedSuffixTree(sequences) 435 self.blocs_texte={} 436 sys.stderr.write("construction blocs max1 = "+str(time.clock()-debut)+"\n") 437 debut=time.clock() 438 self.LL={} 439 #self.LL=st.shared_substrings3(long_min_pivots) 440 self.LL=st.get_MEM_index_chaine(long_min_pivots) 441 # profile.runctx('self.LL=st.shared_substrings3(long_min_pivots)',globals(), locals(),'Z:\workspace\medite\statFile') 442 # s = pstats.Stats('Z:\workspace\medite\statFile') 443 # s.sort_stats('time') 444 # s.print_stats() 445 # sys.stderr.flush() 446 # sys.stdout.flush() 447 # for (start,stop) in self.LL: 448 # chaine=self.texte[start:stop] 449 # if self.blocs_texte.has_key(chaine): 450 # self.blocs_texte[chaine].append(start) 451 # else: self.blocs_texte[chaine] = [start] 452 self.blocs_texte=self.LL 453 #self.clean_bt() 454 self.d2={} 455 for x in self.blocs_texte: 456 self.d2[x]=self.blocs_texte[x] 457 # self.d2=self.blocs_texte 458 # t1,t2,t3=self.dico_to_listes() 459 # for x in t3: 460 # sys.stderr.write(str(x)+"\n") 461 sys.stderr.write("construction blocs max2 = "+str(time.clock()-debut)+"\n") 462 # for x in self.blocs_texte: 463 # sys.stderr.write("*"+x+"* "+str(self.blocs_texte[x])+"\n") 464 # else: sys.stderr.write("self.blocs_texte vide\n") 465 sys.stderr.write("Nombre de blocs maximaux avant elimination recouvrements:"+ str(len(self.blocs_texte))+"\n") 466 sys.stderr.flush() 467 468 self.debut=time.clock() 469 # elimination des recouvrements entre blocs 470 recouv = Recouvrement(self.texte,self.blocs_texte,self.lg_texte1) 471 self.blocs_texte = recouv.eliminer_recouvrements() 472 # for x in self.blocs_texte: 473 # sys.stderr.write(x+" "+str(self.blocs_texte[x])+"\n") 474 475 sys.stderr.write("Nombre de blocs maximaux apres elimination recouvrements:"+ str(len(self.blocs_texte))+"\n") 476 sys.stderr.flush() 477 # Et, pour finir, remplissage des trous par des ajouts ou des suppressions 478 self.completer_blocs_m() 479 480 sys.stderr.write("Nombre de blocs maximaux après complétion par les blocs uniques:"+ str(len(self.blocs_texte))+"\n") 481 sys.stderr.flush()

482 # for x in self.blocs_texte: 483 # sys.stderr.write(x+" "+str(self.blocs_texte[x])+"\n") 484 485

486 - def repetition(self, liste_occ) : # détermine s'il y a une occurrence inférieure

487 # et une occurrence supérieure * frontière dans "liste_occ" (liste_occ est une 488 # liste ordonnée qui correspond * une liste d'occurrences) 489 return (not liste_occ == [] and liste_occ[0] < self.lg_texte1 and liste_occ[-1] >= self.lg_texte1) 490

491 - def occurrence_valide(self, occ, k) :

492 # renvoie un booléen vrai si l'occurrence est valide au rang k 493 # c'est-à-dire si l'occurrence occ peut correspondre à un 494 # motif de longueur k, ce qui veut dire que 495 # (occ >= 0 et occ =< lg_texte1 - k) ou 496 # (occ >= lg_texte1 et occ =< lg_texte1 + lg_texte2 - k) 497 return (((occ >= 0) and 498 (occ <= self.lg_texte1 - k)) or 499 ((occ >= self.lg_texte1) and 500 (occ <= self.lg_texte1 + self.lg_texte2 - k)))

501

502 - def completer_blocs_m(self):

503 L = [[0, self.lg_texte1], [self.lg_texte1, self.lg_texte1 + self.lg_texte2]] 504 LC = self.blocs_texte.keys() 505 for chaine in LC : 506 k = len(chaine) 507 for occ in self.blocs_texte[chaine] : 508 # for (occ,len_occ) in self.blocs_texte[chaine] : 509 L = self.tool.dif_intervalles(L, [occ, occ+k]) 510 # L = dif_intervalles(L, [occ, occ+len_occ]) 511 #sys.stderr.write("L = "+str(L)+"\n") 512 for inter in L : 513 if self.blocs_texte.has_key(self.texte[inter[0]:inter[1]]): 514 self.blocs_texte[self.texte[inter[0]:inter[1]]].append(inter[0]) 515 # self.blocs_texte[self.texte[inter[0]:inter[1]]].append((inter[0],inter[1]-inter[0])) 516 else: self.blocs_texte[self.texte[inter[0]:inter[1]]] = [inter[0]]

517 # else: self.blocs_texte[self.texte[inter[0]:inter[1]]] = [(inter[0],inter[1]-inter[0])] 518

519 - def insertions_et_suppressions(self):

520 """ Constructions des listes d'insertion et suppressions """ 521 for Clef in self.blocs_texte.keys(): 522 Occs = self.blocs_texte[Clef] 523 # si Occs ne contient qu'une seule occurence alors elle n'est présente que dans un des 2 texte 524 if (not self.repetition(Occs)):# or len(Clef)<long_min_pivots): 525 for occ in Occs: 526 if occ < self.lg_texte1: 527 self.suppressions = self.tool.ajout_intervalle(self.suppressions,[occ, occ + len(Clef)]) 528 else: 529 self.insertions = self.tool.ajout_intervalle(self.insertions,[occ, occ + len(Clef)]) 530 else: 531 for occ in Occs: 532 self.identites = self.tool.addition_intervalle(self.identites, [occ, occ + len(Clef)])

533

534 - def construire_remplacements(self):

535 #print len(self.insertions),len(self.occs_texte2),len(self.occs_deplaces) 536 #print len(self.suppressions),len(self.occs_texte1),len(self.occs_deplaces) 537 insertions = self.tool.fusion(self.tool.rang_blocs(self.insertions, self.occs_texte2, self.occs_deplaces)) 538 suppressions = self.tool.fusion(self.tool.rang_blocs(self.suppressions, self.occs_texte1, self.occs_deplaces)) 539 #print len(insertions),len(self.insertions),len(self.occs_texte2),len(self.occs_deplaces) 540 #print len(suppressions),len(self.suppressions),len(self.occs_texte1),len(self.occs_deplaces) 541 #print "Insertions: ", insertions 542 #print "Suppressions: ", suppressions 543 #sys.stdout.flush() 544 self.tous_remplacements = self.tool.correspondance_(suppressions, insertions, self.texte, ratio_min_remplacement) 545 self.occs_remplacements = self.tool.correspondance(suppressions, insertions, self.texte, ratio_min_remplacement) 546 aux0 = [] 547 aux1 = [] 548 for x in self.occs_remplacements[0]: 549 aux0.append(self.texte[x[0][0]: x[0][1]]) 550 for x in self.occs_remplacements[1]: 551 aux1.append(self.texte[x[0][0]: x[0][1]]) 552 self.blocs_remplacements = [aux0, aux1] 553 554 insertions_ = [] 555 for x in insertions: 556 #print "INS2.1 : ",self.texte[x[0][0]:x[0][1]] 557 W = self.tool.soustr_l_intervalles([x[0]], self.occs_deplaces) 558 #print self.tool.longueur(W)," ",str(x[0][0])," ",str(x[0][1]) 559 #print W 560 ratio = float(self.tool.longueur(W))/float(x[0][1]-x[0][0]) 561 #print" / Ratio insertion: ",ratio 562 if ratio > ratio_seuil_lissage: #ajout de l'ins complète 563 insertions_.append(x[0]) 564 else: # ajout de l'ins sans les déplacements 565 insertions_ = self.tool.union(insertions_ , W) 566 567 suppressions_ = [] 568 for x in suppressions: 569 #sys.stderr.write("SUPP2.1 : "+self.texte[x[0][0]:x[0][1]]) 570 W = self.tool.soustr_l_intervalles([x[0]], self.occs_deplaces) 571 ratio = float(self.tool.longueur(W))/(x[0][1]-x[0][0]) 572 #sys.stderr.write( " / Ratio suppression: "+ str(ratio)+"\n") 573 if ratio > ratio_seuil_lissage: 574 suppressions_.append(x[0]) 575 else: 576 suppressions_ = self.tool.union(suppressions_ , W) 577 # sys.stderr.write( " / ratio_seuil_lissage: "+ str(ratio_seuil_lissage)+"\n") 578 # sys.stderr.write( " / suppressions_: "+ str(suppressions_)+"\n") 579 #self.insertions = elimine_int_couverts(self.supp_liste(self.tous_remplacements,0), insertions_,self.texte) 580 self.insertions = self.tool.elimine_int_couverts(self.tous_remplacements, insertions_) 581 # self.suppressions = elimine_int_couverts(self.tous_remplacements, suppressions_,self.texte) 582 self.suppressions = self.tool.elimine_int_couverts(self.supp_liste(self.tous_remplacements,1), suppressions_)

583 # for x in self.insertions: 584 # sys.stderr.write("INS2.3 : "+self.texte[x[0]:x[1]]+"\n") 585 # for x in self.suppressions: 586 # sys.stderr.write("SUPP2.3 : "+self.texte[x[0]:x[1]]+"\n") 587

588 - def supp_liste(self,L,texte1):

589 res=[] 590 for x in L: 591 if texte1 and x[1]<=self.lg_texte1: 592 res.append(x) 593 elif not texte1 and x[0]>=self.lg_texte1: 594 res.append(x) 595 return res

596

597 - def reconstituer_textes(self):

598 self.occs_texte1 = [] # occurences des blocs communs du texte 1 599 self.occs_texte2 = [] # occurences des blocs communs du texte 2 600 self.occs_deplaces = [] 601 602 # pour tous les blocs appartenant aux 2 textes 603 for x in self.identites: 604 if x[0] < self.lg_texte1: 605 self.occs_texte1.append(x) 606 else: self.occs_texte2.append(x) 607 608 self.statBlocs() 609 sys.stderr.write("Debut de l'alignement\n") 610 sys.stderr.flush() 611 deb_al=time.clock() 612 aligneur = alignement.AlignAstar2(self.texte) 613 self.occs_deplaces,self.blocsCommuns = aligneur.deplacements_pond(self.occs_texte1, self.occs_texte2) 614 615 sys.stderr.write("Fin de l'alignement : "+str(time.clock()-deb_al)+"\n") 616 sys.stderr.flush() 617 self.statLB(self.blocsCommuns,"BC") 618 self.statLB(self.occs_deplaces,"Dep") 619 620 # ajout des déplacements dans les insertions et les suppressions 621 for x in self.occs_deplaces: 622 if self.tool.adjacent_(x, self.insertions): 623 #if x[0]>=self.lg_texte1: 624 self.insertions = self.tool.ajout_intervalle(self.insertions, x) 625 if self.tool.adjacent_(x, self.suppressions): 626 #if x[1]<self.lg_texte1: 627 self.suppressions = self.tool.ajout_intervalle(self.suppressions, x) 628 629 for x in self.insertions: 630 self.occs_texte2 = self.tool.addition_intervalle(self.occs_texte2, x) 631 for x in self.suppressions: 632 self.occs_texte1 = self.tool.addition_intervalle(self.occs_texte1, x) 633 634 # construction des occurrences de remplacements 635 self.construire_remplacements() 636 637 # remise à jour de tous les registres... 638 # self.occs_texte1 = [] 639 # self.occs_texte2 = [] 640 # 641 # for x in self.insertions: 642 # self.occs_texte2 = ajout_intervalle(self.occs_texte2, x) 643 # for x in self.suppressions: 644 # self.occs_texte1 = ajout_intervalle(self.occs_texte1, x) 645 # 646 # for x in self.occs_remplacements[0]: 647 # self.occs_texte1 = ajout_intervalle(self.occs_texte1, x[0]) 648 # for x in self.occs_remplacements[1]: 649 # self.occs_texte2 = ajout_intervalle(self.occs_texte2, x[0]) 650 # 651 # for x in self.identites: 652 # if ((not x in self.occs_deplaces) or 653 # (not ( inclus(x, self.occs_texte1) or 654 # inclus(x, self.occs_texte2)))): 655 # if x[0] < self.lg_texte1: 656 # self.occs_texte1 = addition_intervalle(self.occs_texte1, x) 657 # else: self.occs_texte2 = addition_intervalle(self.occs_texte2, x) 658 659 ## construction des blocs communs 660 # self.blocsCommuns = [] 661 # i=0 662 # for x in self.occs_texte1: 663 # if (not self.absent(x, self.occs_texte2) and 664 # #self.absent(x, self.occs_deplaces) and 665 # self.absent(x, self.suppressions)): 666 # self.blocsCommuns.append(x) 667 # sys.stderr.write("BC1 "+str(i)+" "+self.texte[x[0]:x[1]]+"\n") 668 # i+=1 669 # 670 # nb=taille=0 671 # L=[] 672 # for x in self.blocsCommuns: 673 # nb+=1 674 # taille+=x[1]-x[0] 675 # L.append((x[1]-x[0],(x[0],x[1]))) 676 # L.sort() 677 # sys.stderr.write("BC : Nb = "+str(nb)+" / moy = "+str(taille/nb)+" / méd = "+str(L[len(L)/2][0])+" / +gros = "+str(L[-1])+"\n") 678 # i=0 679 # for x in self.occs_texte2: 680 # if (not self.absent(x, self.occs_texte1) and 681 # #self.absent(x, self.occs_deplaces) and 682 # self.absent(x, self.insertions )): # suppressions 683 # self.blocsCommuns.append(x) 684 # sys.stderr.write("BC2 "+str(i)+" "+self.texte[x[0]:x[1]]+"\n") 685 # i+=1 686 687 # construction des paires de blocs déplacés 688 self.lDepl = self.calcPairesBlocsDeplaces(self.occs_deplaces) 689 690 if not self.separatorSensivitive: 691 self.postTraitSuppSep()

692

693 - def trace(self,commande,dic_locals):

694 #profile.runctx(commande,globals(), locals(),'Z:\workspace\medite\statFile') 695 profile.runctx(commande,globals(), dic_locals,'c:\workspace\medite\statFile') 696 s = pstats.Stats('c:\workspace\medite\statFile') 697 s.sort_stats('time') 698 s.print_stats() 699 sys.stderr.flush() 700 sys.stdout.flush()

701

702 - def calcPairesBlocsDeplaces(self, blocsDepl, filtrageDeplacements=True):

703 """Construction de paires de blocs déplacés entre le source et le cible. 704 705 On met en correspondance chaque bloc du source et le ou les blocs identiques du cible. 706 On peut avoir un bloc source qui correspond à plusieurs cibles et vice-versa, 707 auquel cas on aura autant de paires 2 à 2 qu'il y a de correspondances. 708 709 Si on filtre les déplacements, alors on enlève ceux trop petits en fonction 710 de leur distance. Et on replace ces bocs dans les listes d'insérés ou supprimés. 711 @type blocsDepl: list 712 @param blocsDepl: liste des blocs déplacés 713 @type filtrageDeplacements: boolean 714 @param filtrageDeplacements: si vrai on filtre les déplacement non intéressants""" 715 lDepl = [] 716 i=0 717 while (len(blocsDepl) > 0 and blocsDepl[i][0] < self.lg_texte1): 718 #texte1 = self.texte1[blocsDepl[i][0]:blocsDepl[i][1]] 719 longueur = blocsDepl[i][1] - blocsDepl[i][0] 720 for y in blocsDepl[i+1:]: 721 if (y[0] > self.lg_texte1-1 and longueur == y[1] - y[0] and 722 self.texte1[blocsDepl[i][0]:blocsDepl[i][1]] == self.texte2[y[0]-self.lg_texte1:y[1]-self.lg_texte1]): 723 lDepl.append((blocsDepl[i],y)) 724 i += 1 725 726 if filtrageDeplacements: 727 newLDepl = [] 728 # on ajoute les blocs en fonction de leur longueur et de leur distance 729 for b1,b2 in lDepl: 730 longueurBloc = b1[1] - b1[0] 731 ajoutBloc = False 732 # on ajoute systématiquement les grands blocs 733 if longueurBloc > 15: 734 ajoutBloc = True 735 else: 736 assert longueurBloc <= 15 737 positionRelativeT1 = b1[0] 738 positionRelativeT2 = b2[0] - self.lg_texte1 739 assert 0 <= positionRelativeT1 < self.lg_texte1 740 assert 0 <= positionRelativeT2 < self.lg_texte2 741 # distance entre les positions des 2 blocs 742 distanceBloc = abs(positionRelativeT1 - positionRelativeT2) 743 #logging.debug('distanceBloc='+str(distanceBloc)) 744 # ajout des petits blocs distants de moins d'une page 745 if longueurBloc < 8 and distanceBloc < 3000: 746 ajoutBloc = True 747 # ajout des blocs moyens distants d'au plus 3 pages 748 elif 8 <= longueurBloc <= 15 and distanceBloc < 9000: 749 ajoutBloc = True 750 751 #logging.debug((longueurBloc,b1,b2,self.texte1[b1[0]:b1[1]],self.lg_texte1,self.lg_texte2)) 752 # si le déplacement est validé, on va l'afficher 753 if ajoutBloc: 754 newLDepl.append((b1,b2)) 755 else: 756 # sinon, il cela devient une suppression ou une insertion simple 757 # et on l'ajoute à le liste correspondante 758 self.suppressions = self.tool.addition_intervalle(self.suppressions, (b1[0],b1[1])) 759 self.insertions = self.tool.addition_intervalle(self.insertions, (b2[0],b2[1])) 760 try: # et on le supprime de la liste des déplacements 761 k = self.occs_deplaces.index(b1) 762 #logging.debug('k='+str(k)+' / len(o_d)='+str(len(self.occs_deplaces))) 763 self.occs_deplaces.pop(k) 764 except ValueError: 765 # b1 déjà supprimé de la liste, on contiue 766 pass 767 #logging.debug('len(o_d)='+str(len(self.occs_deplaces))) 768 try: #idem 769 k = self.occs_deplaces.index(b2) 770 self.occs_deplaces.pop(k) 771 #logging.debug('k='+str(k)+' / len(o_d)='+str(len(self.occs_deplaces))) 772 except ValueError: 773 # b2 déjà supprimé de la liste, on contiue 774 pass 775 del lDepl 776 lDepl = newLDepl 777 return lDepl

778 779 # Methode d'appel pour effectuer la comparaison

780 - def comparaison(self):

781 self.construction_blocs_maximaux() 782 # self.Dict.etat_dict() 783 self.insertions_et_suppressions() 784 self.reconstituer_textes()

785

786 - def dico_to_listes(self):

787 """ Transformation du dico des blocs maximaux disjoints en 2 listes ordonnées, 1 par texte 788 Les 2 listes contiennent des paires (debut de bloc, fin de bloc) """ 789 t1 = [] 790 t2 = [] 791 t3 = [] 792 for x in self.blocs_texte: 793 t3.append((x,self.blocs_texte[x])) 794 for y in self.blocs_texte[x]: 795 if y < self.lg_texte1: 796 t1.append((y,y+len(x))) 797 else: 798 t2.append((y,y+len(x))) 799 # tri optimisé des listes 800 t1.sort() 801 t2.sort() 802 t3.sort() 803 t4 = [t for t in t1] 804 t5 = [t for t in t2] 805 t6 = [t for t in t3] 806 return t4,t5,t6

807

808 - def mode_car(self):

809 NLC = self.m1() 810 self.blocs_texte = NLC

811 # for x in self.blocs_texte: 812 # sys.stderr.write("blocs_texte["+x+"] = "+str(self.blocs_texte[x])+"\n") 813

814 - def rang2(self, I, S):

815 """ Retourne la distance du bloc I dans la liste S en nombre de caractères et en nb de blocs """ 816 ncar = 0 817 nbloc = 0 818 i=0 819 while i < len(S) and self.texte[I[0]:I[1]] <> self.texte[S[i][0]:S[i][1]]: 820 ncar = ncar + S[i][1] - S[i][0] 821 nbloc += 1 822 i += 1 823 if nbloc>1: nbloc -= 1 824 return ncar,nbloc

825

826 - def m1(self):

827 """ Affinage du mode caractère """ 828 t1,t2 = self.dico_to_listes() # listes de blocs des textes 1 et 2 829 listeBlocsCommuns=[] # liste des blocs communs aux 2 textes 830 NLC={} # Nouvelle liste communs: nouveaux blocs communs détectés grâce au raffinage en mode caractère 831 # indexation par la chaine et liste des positions en regard 832 NLC1={} # idem mais seulement ceux du texte 1, indexation par la position et chaine en regard 833 NLC2={} # idem mais seulement ceux du texte 2 834 LDEP={} # blocs déplacés 835 locCumul={} # localise le début réel dans le texte des chaines concaténées 836 cumulStr2="" #cumul des blocs à comparer précédents du texte2 837 cumulCompt=prevCumulCompt=0 # compteurs de cumul 838 d1=(0,0) # bloc d1 commençant au caractère d1[0] et finissant au caractère d1[1] du texte1 839 # il est aligné avec le bloc d2 du texte2 840 f1=(0,0) # idem d1 mais aligné avec f2 841 d2=(self.lg_texte1,self.lg_texte1) 842 f2=(self.lg_texte1,self.lg_texte1) 843 bComp = False # lancer ou non une comparaison à cette itération 844 firstAlignementDone = False # le 1er alignement entre blocs communs (BC) a été trouvé 845 #locCumul[-1]=t2[0][1] 846 while (t1!=[] and t2!=[]): 847 # sys.stderr.write("t1[0] "+self.texte[t1[0][0]:t1[0][1]] +" / t2[0] "+ self.texte[t2[0][0]:t2[0][1]]+"\n") 848 if t1==[]: 849 # sys.stderr.write("t1 vide\n") 850 t2=[] 851 elif t2==[]: 852 # sys.stderr.write("t2 vide\n") 853 t1=[] 854 elif self.texte[t1[0][0]:t1[0][1]] == self.texte[t2[0][0]:t2[0][1]]: 855 # les 2 blocs courants sont identiques, on met à jour les d avec les anciens f et les f avec ces 2 nouveaux blocs 856 # sys.stderr.write("t1[0] = t2[0]\n") 857 if firstAlignementDone: d1=f1 858 f1=(t1[0][0],t1[0][1]) 859 if firstAlignementDone: d2=f2 860 f2=(t2[0][0],t2[0][1]) 861 t1=t1[1:] 862 t2=t2[1:] 863 bComp = True 864 firstAlignementDone = True 865 elif self.absent(t1[0], t2): 866 # sys.stderr.write("t1[0] absent de t2\n") 867 t1=t1[1:] 868 elif self.absent(t2[0], t1): 869 # sys.stderr.write("t2[0] absent de t1\n") 870 t2=t2[1:] 871 else: 872 #on recherche le bloc le plus près dans l'autre texte et on avance dans ce texte pour retrouver ce bloc 873 # vaut-il mieux avancer de 1 à la place de nbloc ? à tester 874 ecart1,nbloc1 = self.rang2(t1[0],t2) #recherche du bloc t1[0] dans t2 875 ecart2,nbloc2 = self.rang2(t2[0],t1) 876 # sys.stderr.write("ecart1 "+str(ecart1)+" / nbloc1 "+str(nbloc1)+" / ecart2 "+str(ecart2)+" / nbloc2 "+str(nbloc2)+"\n") 877 if (ecart1 < ecart2 or (ecart1 == ecart2 and (t1[0][1] - t1[0][0]) > (t2[0][1] - t2[0][0]))): 878 t2=t2[nbloc1:] 879 else: t1=t1[nbloc2:] 880 # sys.stderr.write("d1 "+str(d1)+" / f1 "+str(f1)+" / d2 "+str(d2)+" / f2 "+str(f2)+"\n") 881 #si un nouvel alignement a été fait ou si on est à la fin des listes 882 if (bComp or (t1==[] and t2==[])): 883 listeBlocsCommuns.append((f1,f2)) #ajout du nouvel alignement à la liste des BC 884 str1 = self.texte[d1[1]:f1[0]] # extraction des chaines à comparer entre les 2 derniers alignements 885 str2 = self.texte[d2[1]:f2[0]] 886 # sys.stderr.write("blocsAComparer1 = "+str1+"\n") 887 # sys.stderr.write("blocsAComparer2 = "+str2+"\n") 888 # sys.stderr.flush() 889 if not(str1=="" and str2==""): 890 appli2 = ecartTextes(str1, str2,long_min_pivots,ratio_min_remplacement, ratio_seuil_lissage, 891 1, self.caseSensitive, self.separatorSensivitive) # algo en mode caractère 892 appli2.construction_blocs_maximaux() 893 for x in appli2.blocs_texte: # pour chaque bloc résultant 894 if x!="": # comme on permet la comparaison avec str1 ou str2 vide, des blocs vides sont retournés dans blocs_texte qui sont filtrés ici 895 l=[] #liste des occurences du bloc x 896 if NLC.has_key(x): #si ce bloc était déjà ajouté dans les nouveaux BC 897 l=NLC[x] # on extrait sa liste d'occurences 898 # sys.stderr.write("NLC[x] HAS KEY= "+x+" / l = "+str(l)+"\n") 899 for y in appli2.blocs_texte[x]: # pour chaque nouvelle occurence 900 # on retrouve l'occurence réelle dans le texte original 901 if (y>=len(str1) or str1==""): # dans le texte 2 902 z=y+d2[1]-len(str1) 903 NLC2[z]=x #localise à la position z tu texte 1 le bloc x 904 else: # dans le texte 1 905 z=y+d1[1] 906 NLC1[z]=x 907 l.append(z) # ajout de cette occurence à la liste 908 NLC[x]=l # stockage de la liste d'occurences associées au bloc x 909 # sys.stderr.write("NLC[x] = "+str(NLC[x])+" / x = "+x+"\n") 910 # sys.stderr.write("appli2.blocs_texte = "+str(appli2.blocs_texte)+"\n") 911 # comparaison entre la nouvelle chaine à comparer du texte 1 et l'ensemble des 912 # chaines nouvellement compérées précédentes concaténées du texte 2 913 # ceci pour détecter des nouveaux blocs communs non détectés par le mode mot 914 # entre str1 et les chaines précédentes du texte2 915 # c'est à dire des déplacements 916 if not(str1=="" and cumulStr2==""): 917 appli3 = ecartTextes(str1, cumulStr2,long_min_pivots,ratio_min_remplacement, ratio_seuil_lissage, 918 1, self.caseSensitive, self.separatorSensivitive) 919 appli3.construction_blocs_maximaux() 920 for x in appli3.blocs_texte: 921 if (x!="" and len(appli3.blocs_texte[x])>1): 922 l=[] 923 if LDEP.has_key(x): # si le bloc x a déjà été identifié comme un déplacement 924 l=LDEP[x] # on résupère sa liste d'occurences 925 # sys.stderr.write("LDEP[x] HAS KEY= "+x+" / l = "+str(l)+"\n") 926 for y in appli3.blocs_texte[x]: # calcul des positions réelles 927 if (y>=len(str1) or str1==""): z=y+locCumul[y-len(str1)][0]-len(str1)-locCumul[y-len(str1)][1] 928 else: z=y+d1[1] 929 if l.count(z)==0: l.append(z) 930 LDEP[x]=l # stckage de la liste des occurences déplacées du bloc x 931 # sys.stderr.write("LDEP[x] = "+str(LDEP[x])+" / x = "+x+"\n") 932 # sys.stderr.write("appli3.blocs_texte = "+str(appli3.blocs_texte)+"\n") 933 # on stocke dans locCumul pour chaque caractère de cumulStr2, la position réelle 934 # dans le texte du bloc auquel il appartient qui est la fin du bloc aligné de gauche d2[1] 935 while cumulCompt<prevCumulCompt+len(str2): 936 locCumul[cumulCompt]=(d2[1],prevCumulCompt) 937 cumulCompt+=1 938 prevCumulCompt=cumulCompt 939 cumulStr2+=str2 # concaténation du cumul, trouver plus otpimiser 940 bComp = False 941 # sys.stderr.write("------------------------------------------------------\n") 942 # fusion des blocs communs adjacents 943 # Pour tous les BC trouvés en mode mot et grâce aux nouveaux BC dans NLC 944 # on va chercher si certains anciens BC ne sont pas adjacents à des nouveaux BC 945 # (ces nouveaux BC étant adjacents à droite des anicens) 946 # auquel cas on les concatène et maj les listes 947 # (l'adjacence à gauche n'est pas recherchée, à faire ?) 948 moved=True 949 while moved: # tant qu'une fusion a été opérée dans la liste à l'itération précédente on relance le processus 950 moved=False 951 for b1,b2 in listeBlocsCommuns: # pour chaque BC alignés entre texte1 et 2 952 sys.stderr.write("*") 953 a=b1[1] # position immédiatement à droite du bloc 954 b=b2[1] 955 if (NLC1.has_key(a) and NLC2.has_key(b)): # cette position est-elle un nouveau BC 956 x=NLC1[a] # bloc présent à cette nouvelle position 957 y=NLC2[b] 958 if (self.texte[b1[0]:a+len(x)] == self.texte[b2[0]:b+len(y)]): # si les fusions sont effectivement identiques 959 listeBlocsCommuns.remove((b1,b2)) # suppression de b1 et b2 des BC 960 sys.stderr.write("remove lBC "+str((b1,b2))+"\n") 961 listeBlocsCommuns.append(((b1[0],a+len(x)),(b2[0],b+len(y)))) # ajout des blocs fusionnés 962 sys.stderr.write("add lBC"+str(((b1[0],a+len(x)),(b2[0],b+len(y))))+"\n") 963 sys.stderr.write("del "+str(NLC1[a])+" / "+str(NLC2[b])+" / "+str(NLC[x])+"\n") 964 del NLC1[a] # suppresions des nouveaux blocs 965 del NLC2[b] 966 l=NLC[x] # suppresions des 2 occurences ou de l'entrée si elle n'avait que ces 2 occurences 967 l.remove(a) 968 l.remove(b) 969 if l==[]: del NLC[x] 970 else: NLC[x]=l 971 moved=True 972 # ajout dans NLC des blocs communs trouvé en mode mot 973 for b1,b2 in listeBlocsCommuns: 974 cle1 = self.texte[b1[0]:b1[1]] 975 # cle2 = self.texte[b2[0]:b2[1]] 976 if cle1!="": #évite les clés vides 977 # ajout des occurences, else inutile ?? 978 if self.blocs_texte.has_key(cle1): NLC[cle1] = self.blocs_texte[cle1] 979 else:NLC[cle1]=[b1[0],b2[0]] 980 # if cle2!="": NLC[cle2] = self.blocs_texte[cle2] 981 # ajout dans NLC des blocs communs déplacés 982 for x in LDEP: 983 l=LDEP[x] 984 if NLC.has_key(x): 985 l2=NLC[x] 986 for e1 in l: # si l'occurence est absente de la liste, on l'ajoute 987 if l2.count(e1)==0:l2.append(e1) 988 NLC[x]=l2 989 else:NLC[x]=l 990 sys.stderr.write("EXIT M1\n") 991 return NLC

992

993 - def statBlocs(self):

994 nbx=0 995 cum=0.0 996 LB=[] 997 for x in self.identites: 998 nbx+=1 999 lx=x[1]-x[0] 1000 cum+=lx 1001 LB.append(lx) 1002 LB.sort() 1003 sys.stderr.write("Nb blocs:+"+str(nbx)+" / Tmoy:"+str(cum/nbx)+" / Tmed:"+str(LB[len(LB)/2])+"\n")

1004

1005 - def statLB(self,liste,nom):

1006 if len(liste)==0: return 1007 nb=0 1008 taille=0.0 1009 L=[] 1010 BC={} 1011 LBC=[] 1012 i=0 1013 for x in liste: 1014 t=self.texte[x[0]:x[1]] 1015 if x[1]<=self.lg_texte1: 1016 nb+=1 1017 taille+=x[1]-x[0] 1018 L.append((x[1]-x[0],(x[0],x[1]))) 1019 LBC.append(t) 1020 if not BC.has_key(t): BC[t]=[] 1021 BC[t].append(x[0]) 1022 #sys.stderr.write("BC"+str(i)+" / "+t+"\n") 1023 i+=1 1024 L.sort() 1025 logging.info("%s : Nb = %d / moy = %.2f / med = %.2f / +gros = %s",nom,nb,taille/nb,L[len(L)/2][0],L[-1]) 1026 sys.stderr.flush()

1027

1028 - def run(self):

1029 #appli.comparaison() 1030 self.construction_blocs_maximaux() 1031 # profile.runctx('appli.construction_blocs_maximaux()',globals(), locals(),'statFile') 1032 # s = pstats.Stats('statFile') 1033 # s.sort_stats('time') 1034 # s.print_stats() 1035 #appli.Dict.etat_dict() 1036 # sys.stderr.write( 'etat_dict') 1037 # sys.stderr.flush() 1038 if (self.carOuMot == 0): 1039 self.mode_car() 1040 self.Dict.etat_dict() 1041 self.insertions_et_suppressions() 1042 # sys.stderr.write( 'insertions_et_suppressions') 1043 # sys.stderr.flush() 1044 self.reconstituer_textes() 1045 # sys.stderr.write( 'reconstituer_textes') 1046 # sys.stderr.flush() 1047 sys.stderr.write("2e phase = "+str(time.clock()-self.debut)+"\n") 1048 # construction de l'instance a retourner 1049 resultat = Resultat(self.insertions, self.suppressions, 1050 self.occs_deplaces, self.tous_remplacements, 1051 self.lg_texte1, self.texte_original, 1052 self.blocsCommuns, self.lDepl) 1053 return resultat

1054

1055 -class ecartTextesRecur(ecartTextes):

1056 """ Classe utilisant les premiers algos d'alignement récursifs """

1057 - def testIn(self,L,name):

1058 for x in L: 1059 #if "tes," in self.texte[x[0]:x[1]]:print "tes, in "+name+str(x)+self.texte[x[0]:x[1]] 1060 #if "jours" in self.texte[x[0]:x[1]]:print "jours in "+name+str(x)+self.texte[x[0]:x[1]] 1061 #if " patte" in self.texte[x[0]:x[1]]:print " patte in "+name+str(x)+self.texte[x[0]:x[1]] 1062 if " dans l" in self.texte[x[0]:x[1]]:print " dans l in "+name+str(x)+self.texte[x[0]:x[1]]

1063

1064 - def reconstituer_textes(self):

1065 self.occs_texte1 = [] # occurences des blocs communs du texte 1 1066 self.occs_texte2 = [] # occurences des blocs communs du texte 2 1067 self.occs_deplaces = [] 1068 1069 # pour tous les blocs appartenant aux 2 textes 1070 for x in self.identites: 1071 if x[0] < self.lg_texte1: 1072 self.occs_texte1.append(x) 1073 else: self.occs_texte2.append(x) 1074 1075 self.statBlocs() 1076 sys.stderr.write("Début de l'alignement\n") 1077 sys.stderr.flush() 1078 deb_al=time.clock() 1079 aligneur = alignement.AlignAstarRecur4(self.texte,self.lg_texte1,long_min_pivots) 1080 self.occs_deplaces,self.blocsCommuns,self.LUnique = aligneur.deplacements_pond(self.occs_texte1, self.occs_texte2) 1081 #self.trace('self.occs_deplaces,self.blocsCommuns,self.LUnique = aligneur.deplacements_pond(self.occs_texte1, self.occs_texte2)',locals()) 1082 sys.stderr.write("Fin de l'alignement : "+str(time.clock()-deb_al)+"\n") 1083 self.statLB(self.blocsCommuns,"BC") 1084 self.statLB(self.occs_deplaces,"Dep") 1085 1086 for x in self.LUnique: 1087 if x[0] < self.lg_texte1: 1088 self.suppressions = self.tool.ajout_intervalle(self.suppressions,x) 1089 else: self.insertions = self.tool.ajout_intervalle(self.insertions,x) 1090 1091 # permet d'oter des ins et supp les nouveaux blocs pivots détectés lors des alignements récursifs 1092 self.suppressions = self.tool.soustr_l_intervalles(self.suppressions,self.blocsCommuns) 1093 self.insertions = self.tool.soustr_l_intervalles(self.insertions,self.blocsCommuns) 1094 for x in self.blocsCommuns: 1095 # ajout des nouveaux blocs pivots détectés lors des alignements récursifs à occs_texte1 et occs_texte2 1096 if x[0] < self.lg_texte1: 1097 self.occs_texte1 = self.tool.addition_intervalle(self.occs_texte1, x) 1098 else: self.occs_texte2 = self.tool.addition_intervalle(self.occs_texte2, x) 1099 1100 for x in self.occs_deplaces: 1101 if self.tool.adjacent_(x, self.insertions): 1102 self.insertions = self.tool.ajout_intervalle(self.insertions, x) 1103 if self.tool.adjacent_(x, self.suppressions): 1104 self.suppressions = self.tool.ajout_intervalle(self.suppressions, x) 1105 1106 for x in self.insertions: 1107 self.occs_texte2 = self.tool.addition_intervalle(self.occs_texte2, x) 1108 for x in self.suppressions: 1109 self.occs_texte1 = self.tool.addition_intervalle(self.occs_texte1, x) 1110 1111 # construction des occurrences de remplacements 1112 self.construire_remplacements() 1113 1114 # construction des paires de blocs déplacés 1115 self.lDepl = self.calcPairesBlocsDeplaces(self.occs_deplaces) 1116 1117 if not self.separatorSensivitive: 1118 self.postTraitSuppSep()

1119

1120 -class ecartTextesRecur2(ecartTextes):

1121 """ Classe utilisant l'algo d'alignement récursif simplifié et amélioré"""

1122 - def extraire_ins_supp(self,occs_t1,occs_t2):

1123 self.suppressions = [[0, self.lg_texte1]] 1124 for x in occs_t1: 1125 self.suppressions = self.tool.dif_intervalles(self.suppressions, x) 1126 self.insertions = [[self.lg_texte1, self.lg_texte1 + self.lg_texte2]] 1127 for x in occs_t2: 1128 self.insertions = self.tool.dif_intervalles(self.insertions, x)

1129

1130 - def reconstituer_textes__(self):

1131 self.occs_texte1 = [] # occurences des blocs communs du texte 1 1132 self.occs_texte2 = [] # occurences des blocs communs du texte 2 1133 1134 #self.statBlocs() 1135 logging.info("Debut de l'alignement") 1136 deb_al=time.clock() 1137 1138 aligneur = alignement.AlignAstarRecur5(self.texte,self.lg_texte1,long_min_pivots) 1139 1140 self.occs_deplaces,self.blocsCommuns = aligneur.run(self.texte1, self.texte2) 1141 #self.trace('self.occs_deplaces,self.blocsCommuns,self.LUnique = aligneur.deplacements_pond(self.occs_texte1, self.occs_texte2)',locals()) 1142 logging.info("Fin de l'alignement : %.2f s",time.clock()-deb_al) 1143 self.statLB(self.blocsCommuns,"BC") 1144 self.statLB(self.occs_deplaces,"Dep") 1145 # pour tous les blocs appartenant aux 2 textes 1146 for x in self.occs_deplaces+self.blocsCommuns: 1147 if x[0] < self.lg_texte1: self.occs_texte1.append(x) 1148 else: self.occs_texte2.append(x) 1149 self.extraire_ins_supp(self.occs_texte1, self.occs_texte2) 1150 1151 #for x in self.LUnique: 1152 # if x[0] < self.lg_texte1: 1153 # self.suppressions = self.tool.ajout_intervalle(self.suppressions,x) 1154 # else: self.insertions = self.tool.ajout_intervalle(self.insertions,x) 1155 1156 # permet d'oter des ins et supp les nouveaux blocs pivots détectés lors des alignements récursifs 1157 #self.suppressions = self.tool.soustr_l_intervalles(self.suppressions,self.blocsCommuns) 1158 #self.insertions = self.tool.soustr_l_intervalles(self.insertions,self.blocsCommuns) 1159 #for x in self.blocsCommuns: 1160 # ajout des nouveaux blocs pivots détectés lors des alignements récursifs à occs_texte1 et occs_texte2 1161 # if x[0] < self.lg_texte1: 1162 # self.occs_texte1 = self.tool.addition_intervalle(self.occs_texte1, x) 1163 # else: self.occs_texte2 = self.tool.addition_intervalle(self.occs_texte2, x) 1164 #print self.suppressions 1165 #print self.occs_deplaces 1166 for x in self.occs_deplaces: 1167 1168 #if self.tool.adjacent_(x, self.insertions): 1169 if x[0] >= self.lg_texte1: 1170 self.insertions = self.tool.ajout_intervalle(self.insertions, x) 1171 else: 1172 #print x,self.texte[x[0]:x[1]] 1173 #if self.tool.adjacent_(x, self.suppressions): 1174 self.suppressions = self.tool.ajout_intervalle(self.suppressions, x) 1175 1176 for x in self.insertions: 1177 self.occs_texte2 = self.tool.addition_intervalle(self.occs_texte2, x) 1178 for x in self.suppressions: 1179 self.occs_texte1 = self.tool.addition_intervalle(self.occs_texte1, x) 1180 #print x,self.texte[x[0]:x[1]] 1181 1182 # construction des occurrences de remplacements 1183 self.construire_remplacements() 1184 # construction des paires de blocs déplacés 1185 self.lDepl = self.calcPairesBlocsDeplaces(self.occs_deplaces) 1186 1187 if not self.separatorSensivitive: 1188 self.postTraitSuppSep()

1189 1190

1191 - def reconstituer_textes(self, coeff=None):

1192 self.occs_texte1 = [] # occurences des blocs communs du texte 1 1193 self.occs_texte2 = [] # occurences des blocs communs du texte 2 1194 1195 logging.log(5,"Debut de l'alignement") 1196 deb_al=time.clock() 1197 # prendre tout le temps AStarRecur car les autres sont uniquement pour des XP 1198 #self.algoAligneur = 'HIS' 1199 if self.algoAligneur == 'Shapira' : 1200 aligneur = alignement.AlignShapiraRecur(self.lg_texte1, 1201 long_min_pivots, algoAlign=self.algoAligneur, coeff=coeff, sep=self.separatorSensivitive) 1202 elif self.algoAligneur == 'ShapiraGap' : 1203 aligneur = alignement.AlignShapiraRecurGap(self.lg_texte1, 1204 long_min_pivots, algoAlign=self.algoAligneur, coeff=coeff, sep=self.separatorSensivitive) 1205 elif self.algoAligneur == 'MOAstar': 1206 aligneur = alignement.AlignAstarRecur2(self.lg_texte1, 1207 long_min_pivots, coeff=coeff, sep=self.separatorSensivitive) 1208 else : aligneur = alignement.AlignAstarRecur(self.lg_texte1, 1209 long_min_pivots, algoAlign=self.algoAligneur, coeff=coeff, sep=self.separatorSensivitive) 1210 1211 self.occs_deplaces,self.blocsCommuns = aligneur.run(self.texte1, self.texte2) 1212 logging.log(5,"Fin de l'alignement : %.2f s",time.clock()-deb_al) 1213 #self.statLB(self.blocsCommuns,"BC") 1214 #self.statLB(self.occs_deplaces,"Dep") 1215 # pour tous les blocs appartenant aux 2 textes 1216 #for x in self.occs_deplaces+self.blocsCommuns: 1217 # if x[0] < self.lg_texte1: self.occs_texte1.append(x) 1218 # else: self.occs_texte2.append(x) 1219 #self.extraire_ins_supp(self.occs_texte1, self.occs_texte2) 1220 #ins1 = self.insertions ; sup1 = self.suppressions 1221 1222 #self.occs_texte1 = [] ; self.occs_texte2 = [] 1223 # on fait 2 boucles pour ne pas faire for x in L1 + L2, trop 1224 # gourmand quand les listes sont grandes 1225 for x in self.occs_deplaces: 1226 if x[0] < self.lg_texte1: self.occs_texte1 = self.tool.addition_intervalle(self.occs_texte1, x) 1227 else: self.occs_texte2 = self.tool.addition_intervalle(self.occs_texte2, x) 1228 for x in self.blocsCommuns: 1229 if x[0] < self.lg_texte1: self.occs_texte1 = self.tool.addition_intervalle(self.occs_texte1, x) 1230 else: self.occs_texte2 = self.tool.addition_intervalle(self.occs_texte2, x) 1231 self.insertions = self.tool.miroir(self.occs_texte2,self.lg_texte1,self.lg_texte) 1232 self.suppressions = self.tool.miroir(self.occs_texte1,0,self.lg_texte1) 1233 #assert len(ins1) == len(self.insertions) 1234 #assert len(sup1) == len(self.suppressions) 1235 #for x in self.occs_deplaces: 1236 #if self.tool.adjacent_(x, self.insertions): 1237 # if x[0] >= self.lg_texte1: 1238 # self.insertions = self.tool.ajout_intervalle(self.insertions, x) 1239 # else: 1240 #print x,self.texte[x[0]:x[1]] 1241 #if self.tool.adjacent_(x, self.suppressions): 1242 # self.suppressions = self.tool.ajout_intervalle(self.suppressions, x) 1243 1244 # construction des paires de blocs déplacés 1245 #logging.debug((len(self.suppressions),self.suppressions)) 1246 self.lDepl = self.calcPairesBlocsDeplaces(self.occs_deplaces) 1247 1248 self.insertions = self.fusionItemsAdjacents(self.insertions) 1249 self.suppressions = self.fusionItemsAdjacents(self.suppressions) 1250 1251 if not self.separatorSensivitive: 1252 self.postTraitSuppSep()

1253

1254 - def fusionItemsAdjacents(self, liste):

1255 """Fusionne les items qui se "touchent" dans une liste 1256 1257 cad les items dont la fin de l'un est le début de l'autre 1258 @type liste: list 1259 @param liste: liste de tuplet de blocs (debut,fin)""" 1260 i = 0 1261 #logging.debug((len(liste),liste)) 1262 while i < len(liste)-1: 1263 #logging.debug(liste[i]) 1264 (deb,fin) = liste[i] 1265 (deb2, fin2) = liste[i+1] 1266 if ((deb == deb2 and fin == fin2) or # blocs identiques 1267 (deb2 <= deb and fin <= fin2) or # bloc i inclus dans bloc i+1 1268 (deb <= deb2 and fin2 <= fin) or # bloc i+1 inclus dans bloc i 1269 (fin == deb2)): # blocs adjacents 1270 liste[i:i+2] = [(deb,fin2)] 1271 else: 1272 i += 1 1273 #logging.debug((len(liste),liste)) 1274 return liste

1275 - def run__(self):

1276 self.reconstituer_textes__() 1277 #sys.stderr.write("2e phase = "+str(time.clock()-self.debut)+"\n") 1278 # construction de l'instance a retourner 1279 resultat = Resultat(self.insertions, self.suppressions, 1280 self.occs_deplaces, self.tous_remplacements, 1281 self.lg_texte1, self.texte_original, 1282 self.blocsCommuns, self.lDepl) 1283 1284 bbl = synthetic.BiBlocListWD(resultat,self.planTravail) 1285 res = bbl.toResultat() 1286 res.setPairesBlocsDeplaces(self.calcPairesBlocsDeplaces(res.getListeDeplacements())) 1287 1288 bbl.print_html() 1289 return res

1290 1291

1292 - def reconstituer_textes_apparies(self):

1293 """Comparaison de 2 textes déjà alignés ligne à ligne""" 1294 def addInter(src, dest1=None,dest2=None,testEquality=False): 1295 assert dest1 is not None or dest2 is not None 1296 e1 = e2 = 0 1297 for inter in src: 1298 if isinstance(inter[0],list): # cas lDepl seulement 1299 dest1.append(([inter[0][0]+increment1,inter[0][1]+increment1], 1300 [inter[1][0]+increment2,inter[1][1]+increment2])) 1301 else: # toutes les autres listes 1302 if inter[1] <= self.lg_texte1: 1303 increment = increment1 1304 x = (inter[0]+increment,inter[1]+increment) 1305 assert 0 <= x[0] < x[1] <= lg_texte1 1306 dest1.append(x) 1307 e1+=1 1308 else: 1309 increment = increment2-len(l1) 1310 x = (inter[0]+increment,inter[1]+increment) 1311 assert lg_texte1 <= x[0] < x[1] <= lg_texte,str(lg_texte1)+str(x)+str(lg_texte) 1312 dest2.append(x) 1313 e2+=1 1314 if testEquality: assert e1 == e2

1315 1316 # accumulateurs des résultats intermédiaires 1317 insertions = [] ; suppressions = [] ; occs_deplaces1 = [] ; occs_deplaces2 = [] 1318 tous_remplacements1 = [] ; tous_remplacements2 = [] ; blocsCommuns1 = [] 1319 blocsCommuns2 = [] ; lDepl = [] 1320 # sauvegarde des params initiaux globaux, car ceux-ci vont être utilisés à chaque étape dans reconstituer_textes() 1321 texte1 = self.texte1 ; texte2 = self.texte2 ; lg_texte1 = self.lg_texte1 ; lg_texte2 = self.lg_texte2 1322 sepSensitive = self.separatorSensivitive ; #texte = texte1 + texte2 ; lg_texte = len(texte) 1323 lg_texte = lg_texte1 + lg_texte2 1324 # désactive le postTraitement dans reconstituer_textes, il ne doit etre effectué qu'à la fin de cette fonction 1325 self.separatorSensivitive = True 1326 ltexte1 = texte1.splitlines(True)# garde les \n dans chaque ligne 1327 ltexte2 = texte2.splitlines(True) 1328 1329 #logging.debug(str(len(ltexte1))+ '/'+str(len(ltexte2))) 1330 #print texte1 1331 assert len(ltexte1) == len(ltexte2) ,str(len(ltexte1))+'/'+str(len(texte2))# les 2 textes doivent avoir la même longueur 1332 if __debug__: 1333 t1 = t2 = 0 1334 for l in ltexte1: t1 += len(l) 1335 for l in ltexte2: t2 += len(l) 1336 assert t1 == lg_texte1 and t2 == lg_texte-lg_texte1 1337 increment1 = 0 ; increment2 = lg_texte1 1338 #for i in xrange(len(ltexte1)): 1339 i = 0 1340 while len(ltexte1) > 0: 1341 logging.debug("itération %d l à l",i) 1342 #l1 = ltexte1[i] ; l2 = ltexte2[i] 1343 l1 = ltexte1.pop(0) ; l2 = ltexte2.pop(0) 1344 #logging.debug(l1) ; logging.debug(l2) 1345 self.texte1 = l1 ; self.texte2 = l2 1346 #self.texte = l1 + l2 1347 self.lg_texte1 = len(l1) ; self.lg_texte2 = len(l2) 1348 self.lg_texte = self.lg_texte1 + self.lg_texte2 1349 self.reconstituer_textes() 1350 addInter(self.insertions, dest2=insertions) 1351 addInter(self.suppressions, dest1=suppressions) 1352 addInter(self.occs_deplaces, occs_deplaces1, occs_deplaces2) 1353 addInter(self.tous_remplacements, tous_remplacements1, tous_remplacements2, True) 1354 addInter(self.blocsCommuns, blocsCommuns1, blocsCommuns2, True) 1355 addInter(lDepl, self.lDepl) 1356 increment1 += len(l1) ; increment2 += len(l2) 1357 i += 1 1358 self.texte1 = texte1 ; self.texte2 = texte2 1359 self.lg_texte1 = lg_texte1 ; self.lg_texte2 = lg_texte2 1360 self.lg_texte = self.lg_texte1 + self.lg_texte2 1361 self.separatorSensivitive = sepSensitive #; self.texte = texte 1362 self.insertions = insertions ; self.suppressions = suppressions 1363 occs_deplaces1.extend(occs_deplaces2) ; self.occs_deplaces = occs_deplaces1 1364 tous_remplacements1.extend(tous_remplacements2) 1365 self.tous_remplacements = tous_remplacements1 1366 blocsCommuns1.extend(blocsCommuns2) ; self.blocsCommuns = blocsCommuns1 1367 self.lDepl = lDepl 1368 if not self.separatorSensivitive: 1369 self.postTraitSuppSep()

1370

1371 - def run(self, textesApparies=False, dossierRapport=None, coeff=None):

1372 """Lancement de la comparaison entre les 2 textes 1373 si texteApparies est vrai, cela signifie que les 2 textes doivent 1374 déjà être alignés ligne à ligne, ainsi, la comparaison se fera par ligne 1375 1376 @type textesApparies: bool 1377 @param textesApparies: les textes sont préappariés ligneà ligne 1378 @type dossierRapport: string 1379 @param dossierRapport: chemin du dossier où écrire le rapport HTML 1380 @type coeff: tuple 1381 @param coeff: tuple des 3 coefficients d'agrégation""" 1382 #gc.set_debug(gc.DEBUG_UNCOLLECTABLE | gc.DEBUG_INSTANCES | gc.DEBUG_OBJECTS | gc.DEBUG_SAVEALL) 1383 if textesApparies: 1384 self.reconstituer_textes_apparies() 1385 #self.trace('self.reconstituer_textes_apparies()', locals()) 1386 else: 1387 self.reconstituer_textes(coeff) 1388 # construction de l'instance à retourner 1389 self.tous_remplacements = [] 1390 resultat = Resultat(self.insertions, self.suppressions, 1391 self.occs_deplaces, self.tous_remplacements, 1392 self.lg_texte1, self.texte_original, 1393 self.blocsCommuns, self.lDepl) 1394 logging.debug('Création BiBlocListWD') 1395 bbl = synthetic.BiBlocListWD(resultat,self.planTravail) 1396 #bb1 = 0 1397 #self.trace('bbl = synthetic.BiBlocListWD(resultat,self.planTravail)', locals()) 1398 logging.debug('BiBlocListWD.toResultat()') 1399 res = bbl.toResultat() 1400 if not textesApparies: 1401 logging.debug('calcPairesBlocsDeplaces()') 1402 #res.setPairesBlocsDeplaces(self.calcPairesBlocsDeplaces2( 1403 # res.getListeDeplacementsT1(),res.getListeDeplacementsT2())) 1404 res.setPairesBlocsDeplaces(self.lDepl) 1405 logging.debug('BiBlocListWD.print_html()') 1406 bbl.print_html(dossierOutput=dossierRapport) 1407 try: 1408 bbl.evaluation() 1409 except ZeroDivisionError: 1410 logging.debug("Erreur d'evaluation ZeroDivisionError") 1411 #for obj in gc.garbage: logging.debug(obj) 1412 self.bbl = bbl 1413 #print res 1414 return res

1415

1416 - def calcPairesBlocsDeplaces2(self,blocsDepl1,blocsDepl2):

1417 """Construction de paires de blocs déplacés entre le source et le cible. 1418 On met en correspondance chaque bloc du source et le ou les blocs identiques du cible. 1419 On peut avoir un bloc source qui correspond à plusieurs cibles et vice-versa, 1420 auquel cas on aura autant de paires 2 à 2 qu'il y a de correspondances.""" 1421 lDepl = [] 1422 i=0 ; len_blocsDepl1 = len(blocsDepl1) 1423 while (i < len_blocsDepl1 and blocsDepl1[i][0] < self.lg_texte1): 1424 texte1 = self.texte1[blocsDepl1[i][0]:blocsDepl1[i][1]] 1425 longueur = blocsDepl1[i][1] - blocsDepl1[i][0] 1426 for y in blocsDepl2:#l[i+1:]: 1427 if (y[0] > self.lg_texte1-1 and longueur == y[1] - y[0] and 1428 texte1 == self.texte2[y[0]-self.lg_texte1:y[1]-self.lg_texte1]): 1429 lDepl.append((blocsDepl1[i],y)) 1430 i += 1 1431 1432 return lDepl

1433

1434 - def trace(self,commande,dic_locals):

1435 import hotshot,hotshot.stats,sys 1436 prof = hotshot.Profile("c:\workspace\medite\statFile") 1437 benchtime = prof.runctx(commande,globals(), dic_locals) 1438 prof.close() 1439 stats = hotshot.stats.load("c:\workspace\medite\statFile") 1440 stats.strip_dirs() 1441 stats.sort_stats('cumulative','calls','time') 1442 stats.print_stats()

1443 1444

1445 - def xpNgram(self):

1446 def concTok(tok): 1447 if len(tok) == 1: return tok[0] 1448 elif len(tok) == 2: return tok[0]+' '+tok[1] 1449 else: return tok[0]+' '+tok[1]+' '+tok[2]

1450 texte = self.texte1 + self.texte2 1451 dicLeftNgram = {} ; dicRightNgram = {} ; dicLeftRightNgram = {} 1452 i = 0 1453 while i < len(self.bbl.liste)-1: 1454 b1,b2 = self.bbl.liste[i] 1455 if b1 is not None and b1[0] == 'R': 1456 b1_prec,b2_prec = self.bbl.liste[i-1] 1457 b1_suiv,b2_suiv = self.bbl.liste[i+1] 1458 if b1_prec is None or b2_prec is None or b1_suiv is None or b2_suiv is None: 1459 #,str(b1_prec)+'/'+str(b2_prec)+'/'+str(b1_suiv)+'/'+str(b2_suiv) 1460 i += 1 ; continue 1461 if b1_prec[0] != 'BC' or b2_prec[0] != 'BC' or b1_suiv[0] != 'BC' or b2_suiv[0] != 'BC': 1462 #'BC',str(b1_prec)+'/'+str(b2_prec)+'/'+str(b1_suiv)+'/'+str(b2_suiv) 1463 i += 1 ; continue 1464 tp = texte[b1_prec[1]:b1_prec[2]] ; ts = texte[b1_suiv[1]:b1_suiv[2]] 1465 tokenp = tp.split() ; tokens = ts.split() 1466 tokenp = tokenp[-3:] ; tokens = tokens[-3:] 1467 assert len(tokenp) <= 3 and len(tokens) <= 3 1468 tokenp = concTok(tokenp) ; tokens = concTok(tokens) 1469 try: dicLeftNgram[tokenp] += 1 1470 except KeyError: dicLeftNgram[tokenp] = 1 1471 try: dicRightNgram[tokens] += 1 1472 except KeyError: dicRightNgram[tokens] = 1 1473 item = (texte[b1[1]:b1[2]],texte[b2[1]:b2[2]]) 1474 try: 1475 nb,liste = dicLeftRightNgram[tokenp,tokens] 1476 liste.append(item) 1477 dicLeftRightNgram[tokenp,tokens] = nb+1, liste 1478 except KeyError: 1479 dicLeftRightNgram[tokenp,tokens] = 1, [item] 1480 i += 1 1481 listeLeftNgram = [] ; listeRightNgram = [] ; listeLeftRightNgram = [] 1482 #for token,nb in dicLeftNgram.iteritems(): 1483 # bisect.insort_right(listeLeftNgram,(nb,token)) 1484 #listeLeftNgram.reverse() 1485 #logging.info('listeLeftNgram:') 1486 #for x in listeLeftNgram: logging.debug(x) 1487 #logging.info('==============================') 1488 #for token,nb in dicRightNgram.iteritems(): 1489 # bisect.insort_right(listeRightNgram,(nb,token)) 1490 #listeRightNgram.reverse() 1491 #logging.info('listeRightNgram:') 1492 #for x in listeRightNgram: logging.debug(x) 1493 #logging.info('==============================') 1494 for token,(nb,item) in dicLeftRightNgram.iteritems(): 1495 bisect.insort_right(listeLeftRightNgram,(nb,token,'==>',item)) 1496 listeLeftRightNgram.reverse() 1497 logging.info('listeLeftRightNgram:') 1498 for x in listeLeftRightNgram: logging.debug(x) 1499 logging.info('==============================') 1500 1501 1502

1503 -class ecartTextesRecur3(ecartTextesRecur2):

1504 """ pas utilisé """

1505 - def postTraitSuppSep(self, bbl):

1506 """Modifie bbl pour reprendre les coordonnées du texte original """ 1507 tabNbSuppression = self.tabNbSuppression 1508 for i in xrange(len(bbl)-1,-1,-1): 1509 B1,B2 = bbl[i] 1510 if B1 is None: NB1 = None 1511 else: NB1 = (B1[0], B1[1] + tabNbSuppression[B1[1]], B1[2] + tabNbSuppression[B1[2]], 1512 [(d1+tabNbSuppression[d1],d2+tabNbSuppression[d2]) for (d1,d2) in B1[3]]) 1513 if B2 is None: NB2 = None 1514 else: NB2 = (B2[0], B2[1] + tabNbSuppression[B2[1]], B2[2] + tabNbSuppression[B2[2]], 1515 [(d1+tabNbSuppression[d1],d2+tabNbSuppression[d2]) for (d1,d2) in B2[3]]) 1516 bbl[i] = (NB1, NB2) 1517 1518 self.texte1 = self.texte1_original 1519 self.texte2 = self.texte2_original 1520 #self.texte = self.texte_original 1521 self.lg_texte1 = len(self.texte1) 1522 self.lg_texte2 = len(self.texte2)

1523

1524 - def reconstituer_textes(self):

1525 logging.log(5,"Debut de l'alignement") 1526 deb_al=time.clock() 1527 aligneur = alignement.AlignAstarRecurBBL(self.lg_texte1,long_min_pivots) 1528 bbl = aligneur.run(self.texte1, self.texte2) 1529 logging.log(5,"Fin de l'alignement : %.2f s",time.clock()-deb_al) 1530 return bbl

1531 1532

1533 - def reconstituer_textes_apparies(self, stream=False, dossierRapport=None):

1534 """Comparaison de 2 textes déjà alignés ligne à ligne""" 1535 bbl = [] 1536 # sauvegarde des params initiaux globaux, car ceux-ci vont être utilisés à chaque étape dans reconstituer_textes() 1537 texte1 = self.texte1 ; texte2 = self.texte2 ; lg_texte1 = self.lg_texte1 ; lg_texte2 = self.lg_texte2 1538 sepSensitive = self.separatorSensivitive ; #texte = texte1 + texte2 ; lg_texte = len(texte) 1539 lg_texte = lg_texte1 + lg_texte2 1540 # désactive le postTraitement dans reconstituer_textes, il ne doit etre effectué qu'à la fin de cette fonction 1541 self.separatorSensivitive = True 1542 ltexte1 = texte1.splitlines(True)# garde les \n dans chaque ligne 1543 ltexte2 = texte2.splitlines(True) 1544 assert len(ltexte1) == len(ltexte2) ,str(len(ltexte1))+'/'+str(len(texte2))# les 2 textes doivent avoir la même longueur 1545 if __debug__: 1546 t1 = t2 = 0 1547 for l in ltexte1: t1 += len(l) 1548 for l in ltexte2: t2 += len(l) 1549 assert t1 == lg_texte1 and t2 == lg_texte-lg_texte1 1550 increment1 = 0 ; increment2 = lg_texte1 1551 i = 0 ; premier = True 1552 #gc.set_debug(gc.DEBUG_SAVEALL) 1553 while len(ltexte1) > 0: 1554 if i%100 == 0: logging.debug("itération %d l à l",i) 1555 i += 1 1556 l1 = ltexte1.pop(0) ; l2 = ltexte2.pop(0) 1557 len_l1 = len(l1) ; len_l2 = len(l2) 1558 self.texte1 = l1 ; self.texte2 = l2 1559 self.lg_texte1 = len_l1 ; self.lg_texte2 = len_l2 1560 self.lg_texte = self.lg_texte1 + self.lg_texte2 1561 bblLigne = self.reconstituer_textes() 1562 for B1,B2 in bblLigne: 1563 if B1 is None: NB1 = None 1564 else: NB1 = (B1[0], B1[1] + increment1, B1[2] + increment1, 1565 [(d1+increment1,d2+increment1) for (d1,d2) in B1[3]]) 1566 if B2 is None: NB2 = None 1567 else: NB2 = (B2[0], B2[1] + increment2-len_l1, B2[2] + increment2-len_l1, 1568 [(d1+increment2-len_l1,d2+increment2-len_l1) for (d1,d2) in B2[3]]) 1569 bbl.append((NB1, NB2)) 1570 increment1 += len_l1 ; increment2 += len_l2 1571 if i%50 == 0 and stream: 1572 if not sepSensitive: self.postTraitSuppSep(bbl) 1573 bbl2 = synthetic.BiBlocListWDListe(bbl, self.planTravail, 1574 self.texte_original, texte1) # attention prendre les param généraux 1575 if premier: 1576 fBuffer = bbl2.print_html_streaming(dossierOutput=dossierRapport,justPrintEntete=True) 1577 premier = False 1578 bbl2.printTableLine(fBuffer) 1579 #logging.debug('1 len(gc.garbage):%d',len(gc.garbage)) 1580 #for x in gc.garbage: 1581 #logging.debug(x) 1582 # del x 1583 1584 #for i in xrange(len(bbl)-1,-1,-1): bbl.pop() libère pas plus de mémoire 1585 del bbl ; del bbl2 ; bbl = [] 1586 #del gc.garbage[:] 1587 #logging.debug('free done') 1588 #logging.debug('2 len(gc.garbage):%d',len(gc.garbage)) 1589 #for x in gc.garbage: logging.debug(x) 1590 1591 if stream: 1592 if not sepSensitive: self.postTraitSuppSep(bbl) 1593 bbl2 = synthetic.BiBlocListWDListe(bbl, self.planTravail, 1594 self.texte_original, texte1) # attention prendre les param généraux 1595 bbl2.printTableLine(fBuffer) 1596 bbl2.printCloseTable(fBuffer) 1597 del bbl2 ; bbl = [] 1598 1599 self.texte1 = texte1 ; self.texte2 = texte2 1600 self.lg_texte1 = lg_texte1 ; self.lg_texte2 = lg_texte2 1601 self.lg_texte = self.lg_texte1 + self.lg_texte2 1602 self.separatorSensivitive = sepSensitive #; self.texte = texte 1603 return bbl

1604 1605

1606 - def run(self, textesApparies=False, dossierRapport=None):

1607 """Lancement de la comparaison entre les 2 textes 1608 si texteApparies est vrai, cela signifie que les 2 textes doivent 1609 déjà être alignés ligne à ligne, ainsi, la comparaison se fera par ligne """ 1610 #gc.set_debug(gc.DEBUG_UNCOLLECTABLE | gc.DEBUG_INSTANCES | gc.DEBUG_OBJECTS | gc.DEBUG_SAVEALL) 1611 logging.debug('debut run') 1612 if textesApparies: 1613 bbl = self.reconstituer_textes_apparies() 1614 #self.trace('self.reconstituer_textes_apparies()', locals()) 1615 else: 1616 bbl = self.reconstituer_textes() 1617 if not self.separatorSensivitive: 1618 self.postTraitSuppSep(bbl) 1619 logging.debug('BiBlocListWDListe(bbl)') 1620 bbl = synthetic.BiBlocListWDListe(bbl, self.planTravail, self.texte_original, self.lg_texte1) 1621 logging.debug('BiBlocListWD.toResultat()') 1622 res = bbl.toResultat() 1623 if not textesApparies: 1624 logging.debug('calcPairesBlocsDeplaces()') 1625 res.setPairesBlocsDeplaces(self.calcPairesBlocsDeplaces2( 1626 res.getListeDeplacementsT1(),res.getListeDeplacementsT2())) 1627 logging.debug('BiBlocListWD.print_html()') 1628 bbl.print_html(dossierOutput=dossierRapport) 1629 bbl.evaluation() 1630 #for obj in gc.garbage: logging.debug(obj) 1631 return res

1632

1633 - def runStream(self, textesApparies=False, dossierRapport=None):

1634 """Lancement de la comparaison entre les 2 textes 1635 si texteApparies est vrai, cela signifie que les 2 textes doivent 1636 déjà être alignés ligne à ligne, ainsi, la comparaison se fera par ligne """ 1637 #gc.set_debug(gc.DEBUG_UNCOLLECTABLE | gc.DEBUG_INSTANCES | gc.DEBUG_OBJECTS | gc.DEBUG_SAVEALL) 1638 logging.debug('debut run') 1639 self.bbl = self.reconstituer_textes_apparies(stream=True, dossierRapport=dossierRapport) 1640 return []

1641

Source Code for Module medite.MediteAppli.MediteAppli