medite.MediteAppli.recouvrement

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 logging, heapq, bisect, sys, random 20 import numpy.oldnumeric as Numeric 21 import utile 22

23 -class Recouvrement(object):

24 """ Classe gérant et résolvant les recouvrements """

25 - def __init__(self,texte,blocs_texte,lg_texte1, min_size=1):

26 self.texte = texte 27 self.blocs_texte = blocs_texte 28 self.lg_texte1 = lg_texte1 29 self.lg_texte2 = len(self.texte)-self.lg_texte1 30 self.min_size = min_size 31 self.tool = utile.Utile()

32

33 - def couverture(self):

34 """ Renvoie sous forme d'une liste croissante d'intervalles tous les segments 35 couverts dans "blocs_texte"; cette fonction permet ensuite 36 determiner les recouvrements """ 37 #logging.debug("debut couverture") 38 L = [] 39 for chaine,liste_pos in self.blocs_texte.iteritems(): 40 ln = len(chaine) 41 for occ in liste_pos: 42 L = self.tool.addition_intervalle(L, [occ, occ + ln]) 43 #logging.debug("fin couverture") 44 return L

45

46 - def recouvrements__(self, couv):

47 """ Cette fonction prends en entree la couverture, c'est-a-dire la 48 liste des intervalles couverts par les chaines de "blocs_texte" 49 Elle renvoie les zones de recouvrement sous forme quadruplets: 50 [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] """ 51 logging.debug("debut recouvrements") 52 L = [] 53 while len(couv)>1: 54 if couv[0][-1] > couv[1][0]: 55 L = self.tool.addition_intervalle(L, [couv[1][0], couv[0][-1], couv[0], couv[1]]) 56 couv = couv[1:] 57 logging.debug("fin recouvrements") 58 return L

59

60 - def recouvrements(self, couv):

61 """ Cette fonction prend en entree la couverture, c'est-a-dire la 62 liste des intervalles couverts par les chaines de "blocs_texte" 63 Elle renvoie les zones de recouvrement sous forme quadruplets: 64 [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] """ 65 #logging.debug("debut recouvrements") 66 L = [] 67 i = 0 68 while i < len(couv)-1: 69 if couv[i][-1] > couv[i+1][0]: 70 L = self.tool.addition_intervalle(L, [couv[i+1][0], couv[i][-1], couv[i], couv[i+1]]) 71 i += 1 72 #logging.debug("fin recouvrements") 73 return L

74

75 - def resoudre_recouvrement_(self, I):

76 """ part d'un intervalle qui corresponds a un recouvrement 77 et trouve une cesure judicieuse (par exemple un blanc) 78 On coupera sur cette cesure 79 I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] """ 80 #sys.stderr.write(str(I)) 81 #logging.debug(self.texte[I[2][0]:I[2][1]]+' / ' +self.texte[I[3][0]:I[3][1]] + 82 # ' / ' + self.texte[I[0]:I[1]]) 83 if (I[0] == 0 or I[0] == self.lg_texte1 or 84 self.texte[I[0]-1] in [' ', '.', '-', ',', '!', '?', ':', ';']): 85 return I[0] 86 if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or 87 self.texte[I[1]] in [' ', '.', '-', ',', '!', '?', ':', ';']): 88 return I[1] 89 90 #taillech1=I[2][1]-I[2][0] 91 #taillech2=I[3][1]-I[3][0] 92 #if taillech1<=taillech2: L = range(I[0], I[1] + 1) 93 #else: L = range(I[1], I[0]-1, -1) 94 L = range(I[0], I[1]+1) 95 for x in L: 96 if self.texte[x] == ' ': 97 return x 98 for x in L: 99 if self.texte[x] in ['.', '-', ',', '!', '?', ':', ';']: 100 return x 101 return L[0]

102

103 - def resoudre_recouvrement____(self, I):

104 """ part d'un intervalle qui corresponds a un recouvrement 105 et trouve une cesure judicieuse (par exemple un blanc) 106 On coupera sur cette cesure 107 I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] """ 108 #sys.stderr.write(str(I)) 109 110 res = I[0] 111 if (I[0] == 0 or I[0] == self.lg_texte1 or 112 self.texte[I[0]-1] in [' ', '.', '-', ',', '!', '?', ':', ';']): 113 res = I[0] 114 elif (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or 115 self.texte[I[1]] in [' ', '.', '-', ',', '!', '?', ':', ';']): 116 res = I[1] 117 118 119 else: 120 #L = range(I[0], I[1]+1) 121 taillech1=I[2][1]-I[2][0] 122 taillech2=I[3][1]-I[3][0] 123 if taillech1<=taillech2: L = range(I[0], I[1] + 1) 124 else: L = range(I[1], I[0]-1, -1) 125 res = L[0] 126 #for x in L: 127 # if self.texte[x] == ' ': 128 # res = x 129 # break 130 #else: 131 for x in L: 132 if self.texte[x] in [' ', '.', '-', ',', '!', '?', ':', ';']: 133 res = x 134 break 135 logging.debug(self.texte[I[2][0]:I[2][1]]+' / ' +self.texte[I[3][0]:I[3][1]] + 136 ' / ' + self.texte[I[0]:I[1]] + ' / res='+self.texte[res-1:res+2] ) 137 return res

138

139 - def resoudre_recouvrement(self, I):

140 """ part d'un intervalle qui correspond à un recouvrement 141 et trouve une cesure judicieuse (par exemple un blanc) 142 On coupera sur cette cesure 143 I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] 144 145 Attention !! pb dans BBL.extractDeplacements(), ne respecte plus l'assertion 146 d'ordre si on utilise cette fonction""" 147 sep = " .-,!?:;\r\n\t" 148 tailleChAnt=I[2][1]-I[2][0] 149 tailleChPost=I[3][1]-I[3][0] 150 res = I[0] 151 match = False 152 #print 'ant:'+self.texte[I[2][0]:I[2][1]]+':'+str(I[2]) 153 #print 'post:'+self.texte[I[3][0]:I[3][1]]+':'+str(I[3]) 154 if tailleChAnt < tailleChPost: 155 #si la chaine antérieure est + petite, on privilégie une coupure dans cettte chaine 156 if (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in sep): 157 res = I[0] 158 match = True 159 elif (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or 160 self.texte[I[1]] in sep): 161 res = I[1] 162 match = True 163 else: # sinon dans l'autre 164 if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or 165 self.texte[I[1]] in sep): 166 res = I[1] 167 match = True 168 elif (I[0] == 0 or I[0] == self.lg_texte1 or 169 self.texte[I[0]-1] in sep): 170 res = I[0] 171 match = True 172 173 if not match: #sinon, on parcours tout le recouvrement dans un sens ou l'autre 174 if tailleChAnt <= tailleChPost: L = range(I[0], I[1] + 1) 175 else: L = range(I[1], I[0]-1, -1) 176 res = L[0] 177 #L = range(I[0], I[1]+1) 178 #for x in L: 179 # if self.texte[x] == ' ': 180 # res = x 181 # match = True 182 if not match: 183 for x in L: 184 if self.texte[x] in sep: 185 res = x 186 if tailleChAnt <= tailleChPost: pass#res = max(L[0],res-1) 187 else: res = max(res+1,L[0]) 188 break 189 #logging.debug(self.texte[I[2][0]:I[2][1]]+' / ' +self.texte[I[3][0]:I[3][1]] + 190 # ' / ' + self.texte[I[0]:I[1]] + ' / res='+self.texte[res-1:res+2] ) 191 if res < 0: res = 0 192 elif res > self.lg_texte1 + self.lg_texte2: res = self.lg_texte1 + self.lg_texte2 193 assert 0 <= res <= self.lg_texte1 + self.lg_texte2 194 return res

195

196 - def adapter_cesure(self, cesure, seg_anterieur, seg_posterieur):

197 """ Une cesure etant donnee, cette fonction rogne les blocs de textes 198 qui recouvrent cette cesure, a savoir les segments anterieur 199 et posterieur qui sont donnes comme argument """ 200 chaine_anterieure = self.texte[seg_anterieur[0]: seg_anterieur[1]] 201 chaine_posterieure = self.texte[seg_posterieur[0]: seg_posterieur[1]] 202 #print "Appel adapter cesure - cesure: ", cesure, " ch1: ", chaine_anterieure, " ch2: ", chaine_posterieure 203 #print "\t\tOccs ch1:", seg_anterieur, " occs ch2: ", seg_posterieur 204 205 Nouv_chaine_anterieure = self.texte[seg_anterieur[0]: cesure] 206 Nouv_chaine_posterieure = self.texte[cesure:seg_posterieur[1]] 207 decalage_ant = seg_anterieur[1] - cesure 208 decalage_post = cesure - seg_posterieur[0] 209 min_size = self.min_size 210 211 if decalage_ant != 0: 212 #print "A ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] 213 if len(self.blocs_texte[chaine_anterieure]) <= 2: 214 if len(Nouv_chaine_anterieure) >= min_size: 215 self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] 216 del self.blocs_texte[chaine_anterieure] 217 else: 218 #try: 219 assert len(self.blocs_texte[chaine_anterieure]) > 2 220 self.blocs_texte[chaine_anterieure].remove(seg_anterieur[0]) 221 #except ValueError,e: 222 # print (e,self.blocs_texte[chaine_anterieure],seg_anterieur[0],chaine_anterieure) 223 if len(Nouv_chaine_anterieure) >= min_size: 224 try: #if not self.blocs_texte.has_key(Nouv_chaine_anterieure): 225 bisect.insort_right(self.blocs_texte[Nouv_chaine_anterieure],seg_anterieur[0]) 226 except KeyError: 227 self.blocs_texte[Nouv_chaine_anterieure] = [seg_anterieur[0]] 228 if __debug__: 229 if self.blocs_texte.has_key(chaine_anterieure): 230 assert len(self.blocs_texte[chaine_anterieure]) >= 2 231 232 if decalage_post != 0: 233 #print "P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] 234 if len(self.blocs_texte[chaine_posterieure]) <= 2: 235 NL = [occ + decalage_post for occ in self.blocs_texte[chaine_posterieure]] 236 if len(Nouv_chaine_posterieure) >= min_size: 237 self.blocs_texte[Nouv_chaine_posterieure] = NL 238 del self.blocs_texte[chaine_posterieure] 239 else: 240 assert len(self.blocs_texte[chaine_posterieure]) > 2 241 self.blocs_texte[chaine_posterieure].remove(seg_posterieur[0]) 242 if len(Nouv_chaine_posterieure) >= min_size: 243 try: 244 bisect.bisect_right(self.blocs_texte[Nouv_chaine_posterieure], cesure) 245 except KeyError: 246 self.blocs_texte[Nouv_chaine_posterieure] = [cesure] 247 if __debug__: 248 if self.blocs_texte.has_key(chaine_posterieure): 249 assert len(self.blocs_texte[chaine_posterieure]) >= 2

250 251 #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) 252 253 #print "Sortie adapter cesure Nouv ch1: ", Nouv_chaine_anterieure, " Nouv ch2: ", Nouv_chaine_posterieure 254 #print "\t\tOccs nouv ch1:", [seg_anterieur[0], cesure], " nouv occs ch2: ", [cesure, seg_posterieur[1]] 255

256 - def adapter_cesure2(self, cesure, seg_anterieur, seg_posterieur):

257 """ Une cesure etant donnee, cette fonction rogne les blocs de textes 258 qui recouvrent cette cesure, a savoir les segments anterieur 259 et posterieur qui sont donnes comme argument """ 260 chaine_anterieure = self.texte[seg_anterieur[0]: seg_anterieur[1]] 261 chaine_posterieure = self.texte[seg_posterieur[0]: seg_posterieur[1]] 262 #print "\nAppel adapter cesure - cesure: ", cesure, " ch1: ", chaine_anterieure, " ch2: ", chaine_posterieure 263 #print "\t\tOccs ch1:", seg_anterieur, " occs ch2: ", seg_posterieur 264 265 Nouv_chaine_anterieure = self.texte[seg_anterieur[0]: cesure] 266 Nouv_chaine_posterieure = self.texte[cesure:seg_posterieur[1]] 267 decalage_ant = seg_anterieur[1] - cesure 268 decalage_post = cesure - seg_posterieur[0] 269 270 if decalage_ant != 0: 271 #print "A ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] 272 if len(self.blocs_texte[chaine_anterieure])==2: 273 self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] 274 #self.blocs_texte[chaine_anterieure] = [] 275 del self.blocs_texte[chaine_anterieure] 276 else: 277 try: 278 self.blocs_texte[chaine_anterieure].remove(seg_anterieur[0]) 279 if not self.blocs_texte.has_key(Nouv_chaine_anterieure): 280 self.blocs_texte[Nouv_chaine_anterieure]=[] 281 self.blocs_texte[Nouv_chaine_anterieure].append(seg_anterieur[0]) 282 except Exception: 283 #print "EEEA ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] 284 pass 285 self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] 286 del self.blocs_texte[chaine_anterieure] #= [] 287 288 if decalage_post != 0: 289 #print "P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] 290 if len(self.blocs_texte[chaine_posterieure])==2: 291 NL = [] 292 for occ in self.blocs_texte[chaine_posterieure]: 293 NL.append(occ + decalage_post) 294 self.blocs_texte[Nouv_chaine_posterieure] = NL 295 #self.blocs_texte[chaine_posterieure] = [] 296 del self.blocs_texte[chaine_posterieure] 297 else: 298 if not self.blocs_texte.has_key(Nouv_chaine_posterieure): 299 self.blocs_texte[Nouv_chaine_posterieure]=[] 300 self.blocs_texte[Nouv_chaine_posterieure].append(cesure) 301 try: 302 self.blocs_texte[chaine_posterieure].remove(seg_posterieur[0]) 303 except Exception: 304 # #print "EEE P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] 305 pass 306 NL = [] 307 for occ in self.blocs_texte[chaine_posterieure]: 308 NL.append(occ + decalage_post) 309 self.blocs_texte[Nouv_chaine_posterieure] = NL 310 del self.blocs_texte[chaine_posterieure] #= []

311 312 #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) 313 314 #print "Sortie adapter cesure Nouv ch1: ", Nouv_chaine_anterieure, " Nouv ch2: ", Nouv_chaine_posterieure 315 #print "\t\tOccs nouv ch1:", [seg_anterieur[0], cesure], " nouv occs ch2: ", [cesure, seg_posterieur[1]] 316

317 - def adapter_cesure1(self, cesure, seg_anterieur, seg_posterieur):

318 """ Une cesure etant donnee, cette fonction rogne les blocs de textes 319 qui recouvrent cette cesure, a savoir les segments anterieur 320 et posterieur qui sont donnes comme argument """ 321 chaine_anterieure = self.texte[seg_anterieur[0]: seg_anterieur[1]] 322 chaine_posterieure = self.texte[seg_posterieur[0]: seg_posterieur[1]] 323 #print "\nAppel adapter cesure - cesure: ", cesure, " ch1: ", chaine_anterieure, " ch2: ", chaine_posterieure 324 #print "\t\tOccs ch1:", seg_anterieur, " occs ch2: ", seg_posterieur 325 326 Nouv_chaine_anterieure = self.texte[seg_anterieur[0]: cesure] 327 Nouv_chaine_posterieure = self.texte[cesure:seg_posterieur[1]] 328 decalage_ant = seg_anterieur[1] - cesure 329 decalage_post = cesure - seg_posterieur[0] 330 331 if decalage_ant != 0: 332 #print "A ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] 333 #if len(self.blocs_texte[chaine_anterieure])==2: 334 try: 335 self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] 336 #self.blocs_texte[chaine_anterieure] = [] 337 del self.blocs_texte[chaine_anterieure] 338 except KeyError: 339 pass 340 #else: 341 # try: 342 # self.blocs_texte[chaine_anterieure].remove(seg_anterieur[0]) 343 # if not self.blocs_texte.has_key(Nouv_chaine_anterieure): 344 # self.blocs_texte[Nouv_chaine_anterieure]=[] 345 # self.blocs_texte[Nouv_chaine_anterieure].append(seg_anterieur[0]) 346 # except Exception: 347 # #print "EEEA ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] 348 # pass 349 # self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] 350 # del self.blocs_texte[chaine_anterieure] #= [] 351 352 if decalage_post != 0: 353 #print "P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] 354 #if len(self.blocs_texte[chaine_posterieure])==2: 355 try: 356 NL = [] 357 for occ in self.blocs_texte[chaine_posterieure]: 358 NL.append(occ + decalage_post) 359 self.blocs_texte[Nouv_chaine_posterieure] = NL 360 #self.blocs_texte[chaine_posterieure] = [] 361 del self.blocs_texte[chaine_posterieure] 362 except KeyError: 363 pass

364 #else: 365 # if not self.blocs_texte.has_key(Nouv_chaine_posterieure): 366 # self.blocs_texte[Nouv_chaine_posterieure]=[] 367 # self.blocs_texte[Nouv_chaine_posterieure].append(cesure) 368 # try: 369 # self.blocs_texte[chaine_posterieure].remove(seg_posterieur[0]) 370 # except Exception: 371 # #print "EEE P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] 372 # pass 373 # NL = [] 374 # for occ in self.blocs_texte[chaine_posterieure]: 375 # NL.append(occ + decalage_post) 376 # self.blocs_texte[Nouv_chaine_posterieure] = NL 377 # del self.blocs_texte[chaine_posterieure] #= [] 378 379 #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) 380 381 #print "Sortie adapter cesure Nouv ch1: ", Nouv_chaine_anterieure, " Nouv ch2: ", Nouv_chaine_posterieure 382 #print "\t\tOccs nouv ch1:", [seg_anterieur[0], cesure], " nouv occs ch2: ", [cesure, seg_posterieur[1]] 383

384 - def adapter_cesure_nocoordo(self, cesure, seg_anterieur, seg_posterieur):

385 """ Une cesure etant donnee, cette fonction rogne les blocs de textes 386 qui recouvrent cette cesure, a savoir les segments anterieur 387 et posterieur qui sont donnes comme argument """ 388 chaine_anterieure = self.texte[seg_anterieur[0]: seg_anterieur[1]] 389 chaine_posterieure = self.texte[seg_posterieur[0]: seg_posterieur[1]] 390 #print "\nAppel adapter cesure - cesure: ", cesure, " ch1: ", chaine_anterieure, " ch2: ", chaine_posterieure 391 #print "\t\tOccs ch1:", seg_anterieur, " occs ch2: ", seg_posterieur 392 393 Nouv_chaine_anterieure = self.texte[seg_anterieur[0]: cesure] 394 Nouv_chaine_posterieure = self.texte[cesure:seg_posterieur[1]] 395 decalage_ant = seg_anterieur[1] - cesure 396 decalage_post = cesure - seg_posterieur[0] 397 398 if decalage_ant != 0: 399 if not self.blocs_texte.has_key(Nouv_chaine_anterieure): 400 self.blocs_texte[Nouv_chaine_anterieure] = [] 401 self.blocs_texte[Nouv_chaine_anterieure].append(seg_anterieur[0]) 402 403 try: 404 self.blocs_texte[chaine_anterieure].remove(seg_anterieur[0]) 405 except ValueError: pass 406 if len(self.blocs_texte[chaine_anterieure]) == 0: 407 del self.blocs_texte[chaine_anterieure] 408 409 if decalage_post != 0: 410 if not self.blocs_texte.has_key(Nouv_chaine_posterieure): 411 self.blocs_texte[Nouv_chaine_posterieure] = [] 412 self.blocs_texte[Nouv_chaine_posterieure].append(cesure) 413 414 try: 415 self.blocs_texte[chaine_posterieure].remove(seg_posterieur[0]) 416 except ValueError: pass 417 if len(self.blocs_texte[chaine_posterieure]) == 0: 418 del self.blocs_texte[chaine_posterieure]

419 420

421 - def eliminer_recouvrements__(self):

422 a = True 423 if a: print 'self.min_size=',self.min_size 424 tot = sum([len(chaine)*len(locc) for chaine,locc in self.blocs_texte.iteritems()]) 425 logging.debug("debut eliminer_recouvrements len(chaines dic)=%d",tot) 426 #print "Appel eliminer recouvrements" 427 Recouvre = self.recouvrements(self.couverture()) 428 i=0 429 while Recouvre != []: 430 #logging.debug("debut itération "+str(i)) ; i += 1 431 #print "Recouvre=",Recouvre 432 for Int in Recouvre: 433 if a: print '----------------------------------------------------------' 434 assert Int[2][1]-Int[2][0] >= self.min_size 435 assert Int[3][1]-Int[3][0] >= self.min_size 436 # Int: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] 437 # Clefs_actives = non_nul_keys(self.blocs_texte) 438 if ( self.blocs_texte.has_key(self.texte[Int[2][0]:Int[2][1]]) and 439 self.blocs_texte.has_key(self.texte[Int[3][0]:Int[3][1]])): 440 if self.tool.inclus_(Int[2], Int[3]): 441 ch = self.texte[Int[2][0]:Int[2][1]] 442 if a: print '*',ch,'* inclus dans *', self.texte[Int[3][0]:Int[3][1]],'*' 443 pos = bisect.bisect_right(self.blocs_texte[ch], Int[2][0]) 444 if a: print pos, Int[2][0], self.blocs_texte[ch] 445 if Int[2][0] == self.blocs_texte[ch][pos-1]: 446 #if Int[2][0] in self.blocs_texte[ch]: 447 if a: print 'occ ',Int[2][0],' removed' 448 self.blocs_texte[ch].remove(Int[2][0]) 449 if len(self.blocs_texte[ch]) == 0: 450 del self.blocs_texte[ch] 451 elif self.tool.inclus_(Int[3], Int[2]): 452 ch = self.texte[Int[3][0]:Int[3][1]] 453 if a: print '*',ch,'* inclus dans *',self.texte[Int[2][0]:Int[2][1]],'*' 454 pos = bisect.bisect_right(self.blocs_texte[ch], Int[3][0]) 455 if a: print pos, Int[3][0], self.blocs_texte[ch] 456 if Int[3][0] == self.blocs_texte[ch][pos-1]: 457 #if Int[3][0] in self.blocs_texte[ch]: 458 if a: print 'occ ',Int[3][0],' removed' 459 self.blocs_texte[ch].remove(Int[3][0]) 460 if len(self.blocs_texte[ch]) == 0: 461 del self.blocs_texte[ch] 462 else: 463 ch1 = self.texte[Int[2][0]:Int[2][1]] 464 ch2 = self.texte[Int[3][0]:Int[3][1]] 465 if a: print 'chevauchement entre *',ch1,'* et *',ch2,'*' 466 #if len(self.blocs_texte[ch1]) > 0 and len(self.blocs_texte[ch2]) > 0: 467 if self.blocs_texte.has_key(ch1) and self.blocs_texte.has_key(ch2): 468 pos1 = bisect.bisect_right(self.blocs_texte[ch1], Int[2][0]) 469 pos2 = bisect.bisect_right(self.blocs_texte[ch2], Int[3][0]) 470 if a: print pos1, Int[2][0], self.blocs_texte[ch1] 471 if a: print pos2, Int[3][0], self.blocs_texte[ch2] 472 if (Int[2][0] == self.blocs_texte[ch1][pos1-1] and 473 Int[3][0] == self.blocs_texte[ch2][pos2-1]): 474 #if Int[2][0] in self.blocs_texte[ch1] and Int[3][0] in self.blocs_texte[ch2]: 475 self.adapter_cesure2(self.resoudre_recouvrement(Int), Int[2], Int[3]) 476 if a: print 'cesure adapted' 477 #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) 478 Recouvre = self.recouvrements(self.couverture()) 479 #print "sortie eliminer recouvrements" 480 tot = sum([len(chaine)*len(locc) for chaine,locc in self.blocs_texte.iteritems()]) 481 logging.debug("fin eliminer_recouvrements len(chaines dic)=%d",tot) 482 483 return self.blocs_texte

484

485 - def eliminer_recouvrements(self, cesureRandom=True):

486 tot = sum([len(chaine)*len(locc) for chaine,locc in self.blocs_texte.iteritems()]) 487 #logging.debug("debut eliminer_recouvrements len(chaines dic)=%d",tot) 488 #print "Appel eliminer recouvrements" 489 Recouvre = self.recouvrements(self.couverture()) 490 i=0 491 while Recouvre != []: 492 #logging.debug("debut itération "+str(i)) ; i += 1 493 #print "Recouvre=",Recouvre 494 for Int in Recouvre: 495 # Int: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] 496 # Clefs_actives = non_nul_keys(self.blocs_texte) 497 if ( self.blocs_texte.has_key(self.texte[Int[2][0]:Int[2][1]]) and 498 self.blocs_texte.has_key(self.texte[Int[3][0]:Int[3][1]])): 499 if self.tool.inclus_(Int[2], Int[3]): 500 ch = self.texte[Int[2][0]:Int[2][1]] 501 if Int[2][0] in self.blocs_texte[ch]: 502 self.blocs_texte[ch].remove(Int[2][0]) 503 if len(self.blocs_texte[ch]) == 0: 504 del self.blocs_texte[ch] 505 elif self.tool.inclus_(Int[3], Int[2]): 506 ch = self.texte[Int[3][0]:Int[3][1]] 507 if Int[3][0] in self.blocs_texte[ch]: 508 self.blocs_texte[ch].remove(Int[3][0]) 509 if len(self.blocs_texte[ch]) == 0: 510 del self.blocs_texte[ch] 511 else: 512 if cesureRandom: 513 self.adapter_cesure_nocoordo(random.randint(Int[0],Int[1]), Int[2], Int[3]) 514 else: 515 self.adapter_cesure_nocoordo(self.resoudre_recouvrement(Int), Int[2], Int[3]) 516 517 #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) 518 Recouvre = self.recouvrements(self.couverture()) 519 #print "sortie eliminer recouvrements" 520 #tot = sum([len(chaine)*len(locc) for chaine,locc in self.blocs_texte.iteritems()]) 521 #logging.debug("fin eliminer_recouvrements len(chaines dic)=%d",tot) 522 523 return self.blocs_texte

524

525 -class Recouvrement2(Recouvrement):

526 - def resoudre_recouvrement__(self, I):

527 """ part d'un intervalle qui correspond à un recouvrement 528 et trouve une cesure judicieuse (par exemple un blanc) 529 On coupera sur cette cesure 530 I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] 531 532 Attention !! pb dans BBL.extractDeplacements(), ne respecte plus l'assertion 533 d'ordre si on utilise cette fonction""" 534 sep = " .-,!?:;" 535 tailleChAnt=I[2][1]-I[2][0] 536 tailleChPost=I[3][1]-I[3][0] 537 #print 'ant:'+self.texte[I[2][0]:I[2][1]]+':'+str(I[2]) 538 #print 'post:'+self.texte[I[3][0]:I[3][1]]+':'+str(I[3]) 539 if tailleChAnt < tailleChPost: 540 #si la chaine antérieure est + petite, on privilégie une coupure dans cettte chaine 541 if (I[0] == 0 or I[0] == self.lg_texte1 or 542 self.texte[I[0]-1] in sep): 543 return I[0] 544 if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or 545 self.texte[I[1]] in sep): 546 return I[1] 547 else: # sinon dans l'autre 548 if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or 549 self.texte[I[1]] in sep): 550 return I[1] 551 if (I[0] == 0 or I[0] == self.lg_texte1 or 552 self.texte[I[0]-1] in sep): 553 return I[0] 554 555 if tailleChAnt <= tailleChPost: L = range(I[0], I[1] + 1) 556 else: L = range(I[1], I[0]-1, -1) 557 #L = range(I[0], I[1]+1) 558 for x in L: 559 if self.texte[x] == ' ': 560 return x 561 for x in L: 562 if self.texte[x] in sep: 563 return x 564 return L[0]

565

566 - def add_bloc(self,debut,fin):

567 chaine = self.texte[debut:fin] 568 try: 569 self.res[chaine].append(debut) 570 except KeyError: 571 self.res[chaine] = [debut]

572

573 - def eliminer_recouvrements(self):

574 #logging.log(5,"debut eliminer_recouvrements") 575 seq_repeat = self.blocs_texte 576 #print seq_repeat[:100] 577 self.res = {} 578 nbFusion = 1 ; n=0 ; cut = False 579 while nbFusion > 0 : #or (nbFusion == 0 and cut): 580 nbFusion = 0 ; n += 1 581 #print n 582 pos = old_debut = len(seq_repeat)-1 583 while pos >= 0: 584 (debut,fin) = seq_repeat[pos] 585 if debut == fin: pos -= 1 ; continue 586 pos = debut 587 pos -= 1 588 (debut_prec,fin_prec) = seq_repeat[pos] 589 if pos == -1: (debut_prec,fin_prec) = (-1,-1) # cas d'arrêt 590 if fin_prec >= fin: # le bloc courant est inclus dans le bloc précédent 591 assert debut_prec <= debut, str(debut_prec)+' '+str(debut) 592 for i in xrange(debut,fin): seq_repeat[i] = (debut_prec,fin_prec) 593 nbFusion += 1 594 continue 595 if fin_prec <= debut: # pas de chevauchement 596 continue 597 assert debut_prec <= debut < fin_prec <= fin # chevauchement 598 #if cut: 599 coupure = self.resoudre_recouvrement((debut,fin_prec,(debut_prec,fin_prec),(debut,fin))) 600 #print 'coupure='+str(coupure) 601 for i in xrange(coupure,fin): 602 seq_repeat[i] = (coupure, fin) 603 #seq_repeat[fin] = (coupure, fin) 604 #seq_repeat[pos-1] = (coupure, fin) 605 for i in xrange(debut_prec, coupure): 606 seq_repeat[i] = (debut_prec, coupure) 607 #seq_repeat[pos] = (debut_prec, coupure) # MAJ du bloc précédent coupé 608 #seq_repeat[debut_prec] = (debut_prec, coupure) 609 nbFusion += 1 610 #if nbFusion == 0 and not cut: cut = True 611 #elif nbFusion == 0 and cut: cut = False 612 pos = len(seq_repeat)-1 613 while pos >= 0: 614 (debut,fin) = seq_repeat[pos] 615 if fin-debut > 0: self.add_bloc(debut,fin) 616 pos = debut - 1 617 #print n,seq_repeat[:100] 618 return self.res

619

620 - def eliminer_recouvrementsww(self):

621 #logging.debug("debut eliminer_recouvrements") 622 seq_repeat = self.blocs_texte 623 longueur_sequence = len(seq_repeat) 624 #print seq_repeat[:100] 625 self.res = {} 626 nbFusion = 1 ; n=0 627 while nbFusion > 0: 628 nbFusion = 0 ; n += 1 629 print n 630 pos = old_debut = 0 631 while pos < longueur_sequence: 632 (debut,fin) = seq_repeat[pos] 633 pos = fin + 1 634 if debut == fin: continue 635 if pos >= longueur_sequence: (debut_prec,fin_prec) = (longueur_sequence+1,longueur_sequence+1) # cas d'arrêt 636 else: (debut_prec,fin_prec) = seq_repeat[pos] 637 638 if fin >= fin_prec: # le bloc suivant est inclus dans le bloc courant 639 assert debut <= debut_prec 640 for i in xrange(debut_prec,fin_prec): seq_repeat[i] = (debut,fin) 641 nbFusion += 1 642 continue 643 if fin <= debut_prec: # pas de chevauchement 644 continue 645 if debut >= debut_prec: 646 for i in xrange(debut,fin): seq_repeat[i] = (debut_prec,fin_prec) 647 nbFusion += 1 648 continue # bloc courant inclus dans bloc suivant 649 assert debut <= debut_prec < fin <= fin_prec, str(pos)+str((debut,fin))+str((debut_prec,fin_prec)) # chevauchement 650 coupure = self.resoudre_recouvrement((debut_prec,fin,(debut,fin),(debut_prec,fin_prec))) 651 for i in xrange(debut,coupure): 652 seq_repeat[i] = (debut, coupure) 653 #seq_repeat[fin] = (coupure, fin) 654 #seq_repeat[pos-1] = (coupure, fin) 655 for i in xrange(coupure, fin_prec): 656 seq_repeat[i] = (coupure, fin_prec) 657 nbFusion += 1 658 print nbFusion 659 pos = 0 660 while pos < len(seq_repeat): 661 (debut,fin) = seq_repeat[pos] 662 self.add_bloc(debut,fin) 663 pos = fin + 1 664 #print n,seq_repeat[:100] 665 return self.res

666

667 - def eliminer_recouvrementsuu(self):

668 logging.debug("debut eliminer_recouvrements") 669 seq_repeat = self.blocs_texte 670 self.res = {} 671 pos = old_debut = len(seq_repeat)-1 672 #old_debut = len(seq_repeat)+1 673 (debut_av,fin_av) = (len(seq_repeat),len(seq_repeat)) 674 while pos >= 0: 675 #print pos 676 (debut,fin) = seq_repeat[pos] 677 pos = debut 678 pos -= 1 679 if debut == fin: continue 680 (debut_prec,fin_prec) = seq_repeat[pos] 681 if pos == -1: (debut_prec,fin_prec) = (-1,-1) # cas d'arrêt 682 if fin_prec >= fin: # le bloc courant est inclus dans le bloc précédent 683 #print (debut_prec,fin_prec),(debut,fin) 684 assert debut_prec <= debut 685 continue 686 if fin_prec <= debut: # pas de chevauchement 687 self.add_bloc(debut,fin); continue 688 assert debut_prec <= debut < fin_prec <= fin # chevauchement 689 coupure = self.resoudre_recouvrement((debut,fin_prec,(debut_prec,fin_prec),(debut,fin))) 690 self.add_bloc(coupure,fin) 691 seq_repeat[pos] = (debut_prec, coupure) # MAJ du bloc précédent coupé 692 return self.res

693

694 - def eliminer_recouvrementsMMM(self):

695 logging.debug("debut eliminer_recouvrements") 696 seq_repeat = self.blocs_texte 697 longueur_sequence = len(seq_repeat) 698 self.res = {} 699 pos = old_debut = 0 700 #old_debut = len(seq_repeat)+1 701 #(debut_av,fin_av) = (len(seq_repeat),len(seq_repeat)) 702 while pos < longueur_sequence: 703 #print pos 704 (debut,fin) = seq_repeat[pos] 705 pos = fin 706 pos += 1 707 if debut == fin: continue 708 if pos >= longueur_sequence: (debut_prec,fin_prec) = (longueur_sequence+1,longueur_sequence+1) # cas d'arrêt 709 else: (debut_prec,fin_prec) = seq_repeat[pos] 710 711 if fin >= fin_prec: # le bloc suivant est inclus dans le bloc courant 712 #print (debut_prec,fin_prec),(debut,fin) 713 assert debut <= debut_prec 714 self.add_bloc(debut,fin) 715 continue 716 if fin <= debut_prec: # pas de chevauchement 717 self.add_bloc(debut,fin); continue 718 if debut >= debut_prec: 719 continue # bloc courant inclus dans bloc suivant 720 assert debut <= debut_prec < fin <= fin_prec, str(pos)+str((debut,fin))+str((debut_prec,fin_prec)) # chevauchement 721 coupure = self.resoudre_recouvrement((debut_prec,fin,(debut,fin),(debut_prec,fin_prec))) 722 self.add_bloc(debut,coupure) 723 seq_repeat[pos] = (coupure,fin_prec) # MAJ du bloc précédent coupé 724 return self.res

725

726 - def eliminer_recouvrements__(self):

727 logging.debug("debut eliminer_recouvrements") 728 seq_repeat = self.blocs_texte 729 res = {} 730 pos = len(seq_repeat)-1 731 old_debut = len(seq_repeat)+1 732 (debut_av,fin_av) = (len(seq_repeat),len(seq_repeat)) 733 while pos >= 0: 734 #print 'pos=',pos 735 pos_BU = pos 736 (debut,fin) = seq_repeat[pos] 737 #print (debut,fin),self.texte[debut:fin] 738 assert debut <= fin 739 if debut == fin: 740 pos = debut-1 741 #(debut,fin) = seq_repeat[pos] 742 else: 743 pos = debut # remonte au début du bloc 744 (debut_prec,fin_prec) = seq_repeat[pos-1] 745 #print (debut_prec,fin_prec),self.texte[debut_prec:fin_prec] 746 while pos-2 >= 0: 747 (debut_prec2,fin_prec2) = seq_repeat[pos-2] 748 if fin_prec2 >= fin_prec: 749 assert debut_prec2 <= debut_prec,str(debut_prec2)+'/'+str(debut_prec) 750 (debut_prec,fin_prec) = seq_repeat[pos-2] 751 pos -= 1 752 else: break 753 #print (debut_prec,fin_prec),self.texte[debut_prec:fin_prec] 754 pos -= 1 # pos désigne maintenant le bloc précédent 755 if fin_prec >= fin: # bloc courant inclus dans bloc precedent 756 continue #= debut -1 ; continue 757 #(debut_prec,fin_prec) = seq_repeat[pos-1] 758 if fin_prec > debut: # chevauchement 759 coupure = self.resoudre_recouvrement((debut,fin_prec,(debut_prec,fin_prec),(debut,fin))) 760 debut = coupure 761 seq_repeat[pos] = (debut_prec,coupure) #debut-1] = (debut_prec,coupure) 762 #print 'coupure=',coupure 763 # le bloc est overlap-free, on peut l'ajouter au dico résultat 764 if fin > debut_av: 765 coupure2 = debut_av 766 fin = coupure2 767 #print 'coupure2=',coupure2 768 assert fin <= old_debut,str(fin)+'/'+str(old_debut) 769 assert fin <= debut_av 770 chaine = self.texte[debut:fin] 771 try: 772 res[chaine].append(debut) 773 except KeyError: 774 res[chaine] = [debut] 775 (debut_av,fin_av) = (debut,fin) 776 old_debut = debut 777 #pos = debut-1 778 #assert pos < pos_BU, str(pos)+'/'+str(pos_BU) 779 #print '------------------' 780 logging.debug("fin eliminer_recouvrements") 781 return res

782

783 - def eliminer_recouvrements_(self):

784 logging.debug("debut eliminer_recouvrements") 785 seq_repeat = self.blocs_texte 786 res = {} 787 pos = 0#len(seq_repeat)-1 788 old_fin = -1#len(seq_repeat)+1 789 (debut_av,fin_av) = (-1,-1)#(len(seq_repeat),len(seq_repeat)) 790 while pos < len(seq_repeat)-1: 791 #print 'pos=',pos 792 pos_BU = pos 793 (debut,fin) = seq_repeat[pos] 794 #print (debut,fin),self.texte[debut:fin] 795 assert debut <= fin 796 if debut == fin: 797 pos = fin+1 798 #(debut,fin) = seq_repeat[pos] 799 else: 800 pos = fin # remonte au début du bloc 801 if pos >= len(seq_repeat)-1: 802 try: 803 chaine = self.texte[debut:fin] 804 res[chaine].append(debut) 805 except KeyError: 806 res[chaine] = [debut] 807 break 808 809 (debut_prec,fin_prec) = seq_repeat[pos+1] 810 #print (debut_prec,fin_prec),self.texte[debut_prec:fin_prec] 811 while pos+2 <len(seq_repeat): 812 (debut_prec2,fin_prec2) = seq_repeat[pos+2] 813 if (debut_prec2 == debut_prec and fin_prec2 >= fin_prec): 814 assert debut_prec2 >= debut_prec,str(debut_prec2)+'/'+str(debut_prec) 815 (debut_prec,fin_prec) = seq_repeat[pos+2] 816 pos += 1 817 else: break 818 pos += 1 819 #print (debut_prec,fin_prec),self.texte[debut_prec:fin_prec] 820 #if fin >= fin_prec: # bloc courant inclus dans bloc precedent 821 # pos = debut+1 ; continue 822 # (debut_prec,fin_prec) = seq_repeat[pos-1] 823 if debut_prec < fin: # chevauchement 824 coupure = self.resoudre_recouvrement((debut_prec,fin,(debut,fin),(debut_prec,fin_prec))) 825 fin = coupure 826 seq_repeat[pos] = (coupure,fin_prec) #fin+1] = (coupure,fin_prec) 827 #print 'coupure=',coupure 828 # le bloc est overlap-free, on peut l'ajouter au dico résultat 829 if debut > fin_av: 830 coupure2 = fin_av 831 debut = coupure2 832 #print 'coupure2=',coupure2 833 assert fin >= old_fin,str(fin)+'/'+str(old_fin) 834 #assert fin <= debut_av 835 chaine = self.texte[debut:fin] 836 try: 837 res[chaine].append(debut) 838 except KeyError: 839 res[chaine] = [debut] 840 (debut_av,fin_av) = (debut,fin) 841 old_fin = fin 842 #pos = fin+1 843 #assert pos < pos_BU, str(pos)+'/'+str(pos_BU) 844 #print '------------------' 845 logging.debug("fin eliminer_recouvrements") 846 return res

847

848 -class Recouvrement3(Recouvrement2):

849 """ Renvoie un dico indexé par un tuplet (cle,longueur) 850 plutot que par chaine[debut:fin], ce qui évite de stocker les chaines 851 dans le dico """

852 - def add_bloc(self,debut,fin):

853 cle = hash(self.texte[debut:fin]) 854 longueur = fin-debut 855 try: 856 self.res[(cle,longueur)].append(debut) 857 except KeyError: 858 self.res[(cle,longueur)] = [debut] 859 self.NOSMEM_nb_bloc += 1

860

861 -class RecouvrementNaif(Recouvrement3):

862 - def __init__(self,texte,blocs_texte,lg_texte1,min_size):

863 self.min_size = min_size 864 Recouvrement3.__init__(self,texte,blocs_texte,lg_texte1)

865

866 - def transformListe(self):

867 """ Transforme self.blocs_texte en une file de priorité indexé par la taille des blocs: 868 les blocs les + grands sont prioritaires. Un bloc est constitué de son index, 869 sa longueur, sa cle unique et sa liste d'occurrences""" 870 liste1 = [] ; liste2 = [] ; liste = [] ; listet = [] 871 nb_bloc = 0 ; tot=0 ; nb_occ = 0 872 for longueur, dicoOcc in self.blocs_texte.iteritems(): 873 for cle_hash, lOcc in dicoOcc.iteritems(): 874 for occ in lOcc: 875 if occ < self.lg_texte1: 876 bisect.insort_right(liste1, (occ,occ+longueur)) 877 else: 878 bisect.insort_right(liste2, (occ,occ+longueur)) 879 bisect.insort_right(liste, (occ,occ+longueur)) 880 lOcc.sort() 881 bisect.insort_right(listet, [lOcc[0], longueur, cle_hash , lOcc]) 882 nb_bloc += 1 883 nb_occ += len(lOcc) 884 tot += len(lOcc) * longueur 885 ###logging.debug( hq) 886 assert len(liste) == nb_occ 887 self.SMEM_nb_bloc = nb_bloc # nb SMEM à l'origine 888 self.SMEM_nb_occ = nb_occ # nb d'occurences de SMEM à l'origine 889 self.SMEM_tot_size = tot # taille totale des SMEM à l'origine 890 ###logging.debug("debut eliminer_recouvrements len(chaines dic)=%d",tot) 891 return listet

892

893 - def eliminer_recouvrements(self):

894 listet = self.transformListe() 895 896 longueur_totale = self.lg_texte1+self.lg_texte2+1 897 self.seq_repeat_deb = Numeric.zeros(longueur_totale,Numeric.Int) 898 self.seq_repeat_fin = Numeric.zeros(longueur_totale,Numeric.Int) 899 for i in xrange(longueur_totale): 900 #self.seq_repeat.append((i,i)) 901 self.seq_repeat_deb[i] = i 902 self.seq_repeat_fin[i] = i 903 904 self.totalAjout = self.totalRogneG = self.totalRogneD = self.nb_reinclusion = 0 905 bb= False 906 i = 0 907 while i < len(listet)-1: 908 [deb, longueur, cle_hash , lOcc] = listet[i] 909 k = 0 910 while k < len(lOcc)-1: #auto-recouvrement, une merveille de la nature stringologique 911 occ1 = lOcc[k] ; occ2 = lOcc[k+1] 912 if occ1+longueur > occ2: 913 pos = lOcc.index(occ2) 914 lOcc.pop(pos) 915 else: k+= 1 916 917 j = i + 1 918 while j < len(listet): 919 (deb2, longueur2, cle_hash2 , lOcc2) = listet[j] 920 dd1 = dd2 = dg1 = dg2 = 0 921 for occ in lOcc: 922 for occ2 in lOcc2: 923 #print self.texte[occ:occ+longueur],'vs.',self.texte[occ2:occ2+longueur2] 924 if '&&é&éé.nous.' == self.texte[occ:occ+longueur] :# and '.la.place.gommant.sa.fla' == self.texte[occ2:occ2+longueur2]: 925 print listet[i],listet[j] 926 bb = True 927 #print occ < occ2 < occ+longueur, occ+longueur < longueur_totale-1 928 #print occ2 < occ < occ2+longueur2, occ2+longueur2 < longueur_totale-1 929 if occ <= occ2 < occ2+longueur2 <= occ+longueur: 930 pos = lOcc2.index(occ2) 931 lOcc2.pop(pos) 932 if occ2 <= occ < occ+longueur <= occ2+longueur2: 933 pos = lOcc.index(occ) 934 lOcc.pop(pos) 935 if occ < occ2 < occ+longueur and occ+longueur < longueur_totale-1: 936 if bb: print dd1,dg1 937 cd = self.resoudre_recouvrement([occ2, occ+longueur,[occ,occ+longueur], [occ2,occ2+longueur2]]) 938 dd1 = max(dd1,occ+longueur-cd) 939 dg1 = max(dg1, cd-occ2) 940 if bb: print cd,dd1,dg1 941 if occ2 < occ < occ2+longueur2 and occ2+longueur2 < longueur_totale-1: 942 if bb: print dd2,dg2 943 cg = self.resoudre_recouvrement([occ, occ2+longueur2,[occ2,occ2+longueur2], [occ,occ+longueur]]) 944 dg2 = max(dg2, cg-occ) 945 dd2 = max(dd2, occ2+longueur2-cg) 946 if bb: print cg,dd2,dg2 947 if dd1 > 0 or dg1 > 0: 948 longueur -= dd1 949 lOcc2 = [occ+dg1 for occ in lOcc2] 950 longueur2 -= dg1 951 952 if dd2 > 0 or dg2 > 0: 953 longueur2 -= dd2 954 lOcc = [occ+dg2 for occ in lOcc] 955 longueur -= dg2 956 957 if len(lOcc2) == 0: 958 listet[j] = [sys.maxint, longueur2, cle_hash2 , lOcc2] 959 else: listet[j] = [lOcc2[0], longueur2, cle_hash2 , lOcc2] 960 961 if bb: print listet[i],listet[j] 962 j += 1 963 if bb: bb= False 964 if len(lOcc) == 0: 965 listet[i] = [sys.maxint, longueur, cle_hash , lOcc] 966 else: listet[i] = [lOcc[0], longueur, cle_hash , lOcc] 967 (deb, longueur, cle_hash , lOcc) = listet[i] 968 i += 1 969 #HqOccBlocc vide, on a fini 970 #logging.debug(self.seq_repeat) 971 972 #i = 0 973 #while i < len(listet 974 self.NOSMEM_nb_bloc = 0 # nb NOSMEM 975 self.NOSMEM_nb_occ = 0 # nb d'occurences de NOSMEM 976 self.NOSMEM_tot_size = 0 # taille totale des NOSMEM 977 self.res = {} 978 pos = 0#len(self.seq_repeat)-1 979 #while pos >= 0: 980 981 for nosmem in listet: 982 (deb, longueur, cle_hash , lOcc) = nosmem 983 if longueur == 0: 984 #print 'ZERO',nosmem 985 continue 986 if len(lOcc) == 1: 987 #print 'UN LEN',lOcc 988 continue 989 prev = -1 990 for occ in lOcc: 991 if occ > prev: 992 self.add_bloc(occ,occ+longueur) 993 self.NOSMEM_nb_occ += 1 994 self.NOSMEM_tot_size += longueur 995 prev = occ + longueur 996 997 998 999 #logging.debug('=========================') 1000 #logging.debug('fin recouv self.totalAjout=%d / self.totalRogneG=%d / self.totalRogneD=%d / self.nb_reinclusion=%d / len(self.res)=%d', 1001 # self.totalAjout,self.totalRogneG,self.totalRogneD,self.nb_reinclusion,len(self.res)) 1002 #logging.debug('self.res = '+str(self.res)) 1003 for cle,lOcc in self.res.iteritems(): 1004 lOcc.reverse() # on reverse car dans la suite dans l'algo c'est nécessaire 1005 1006 return self.res

1007

1008 - def resoudre_recouvrement_random(self, I):

1009 """ part d'un intervalle qui correspond à un recouvrement 1010 et trouve une cesure judicieuse (par exemple un blanc) 1011 On coupera sur cette cesure 1012 I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] 1013 1014 Attention !! pb dans BBL.extractDeplacements(), ne respecte plus l'assertion 1015 d'ordre si on utilise cette fonction""" 1016 sep = " .-,!?:;\r\n\t" 1017 tailleChAnt=I[2][1]-I[2][0] 1018 tailleChPost=I[3][1]-I[3][0] 1019 res = random.randint(I[0],I[1]) 1020 if res < 0: res = 0 1021 elif res > self.lg_texte1 + self.lg_texte2: res = self.lg_texte1 + self.lg_texte2 1022 assert 0 <= res <= self.lg_texte1 + self.lg_texte2 1023 return res

1024

1025 -class Recouvrement4(Recouvrement3):

1026 - def __init__(self,texte,blocs_texte,lg_texte1,min_size):

1027 self.min_size = min_size 1028 Recouvrement3.__init__(self,texte,blocs_texte,lg_texte1)

1029

1030 - def eliminer_recouvrements(self):

1031 #self.seq_repeat = [] ; 1032 self.dicoOccLiee = {} 1033 longueur_totale = self.lg_texte1+self.lg_texte2+1 1034 self.seq_repeat_deb = Numeric.zeros(longueur_totale,Numeric.Int) 1035 self.seq_repeat_fin = Numeric.zeros(longueur_totale,Numeric.Int) 1036 for i in xrange(longueur_totale): 1037 #self.seq_repeat.append((i,i)) 1038 self.seq_repeat_deb[i] = i 1039 self.seq_repeat_fin[i] = i 1040 self.hqOccBloc = self.transformHeapQueue() 1041 self.old_len_add = 10000000 1042 self.totalAjout = self.totalRogneG = self.totalRogneD = self.nb_reinclusion = 0 1043 1044 while len(self.hqOccBloc) > 0: # parcour de tous les blocs 1045 ###logging.debug(len(self.hqOccBloc)) 1046 (index,longueur,cle_hash,lOcc) = heapq.heappop(self.hqOccBloc) # bloc le + long 1047 ###logging.debug(len(self.hqOccBloc)) 1048 ###logging.debug(str((index,longueur,cle_hash,lOcc))+' / bloc: '+self.texte[lOcc[0]:lOcc[0]+longueur]) 1049 #if longueur >= self.min_size: 1050 if len(lOcc) > 1: 1051 #logging.debug('ajoutOccurences: '+self.texte[lOcc[0]:lOcc[0]+longueur]+' / '+str(longueur)+' / '+str(lOcc)) 1052 self.ajoutOccurences(longueur,lOcc) 1053 ###logging.debug(len(self.hqOccBloc)) 1054 #logging.debug('----------------------------') 1055 1056 #HqOccBlocc vide, on a fini 1057 #logging.debug(self.seq_repeat) 1058 self.NOSMEM_nb_bloc = 0 # nb NOSMEM 1059 self.NOSMEM_nb_occ = 0 # nb d'occurences de NOSMEM 1060 self.NOSMEM_tot_size = 0 # taille totale des NOSMEM 1061 self.res = {} 1062 pos = 0#len(self.seq_repeat)-1 1063 #while pos >= 0: 1064 while pos < len(self.seq_repeat_deb): 1065 debut = self.seq_repeat_deb[pos] 1066 fin = self.seq_repeat_fin[pos] 1067 if fin-debut > 0: 1068 self.add_bloc(debut,fin) 1069 pos = fin 1070 self.NOSMEM_nb_occ += 1 1071 self.NOSMEM_tot_size += fin-debut 1072 else: pos += 1 1073 #pos = debut - 1 1074 1075 #logging.debug('=========================') 1076 #logging.debug('fin recouv self.totalAjout=%d / self.totalRogneG=%d / self.totalRogneD=%d / self.nb_reinclusion=%d / len(self.res)=%d', 1077 # self.totalAjout,self.totalRogneG,self.totalRogneD,self.nb_reinclusion,len(self.res)) 1078 #logging.debug('self.res = '+str(self.res)) 1079 for cle,lOcc in self.res.iteritems(): 1080 lOcc.reverse() # on reverse car dans la suite dans l'algo c'est nécessaire 1081 1082 return self.res

1083

1084 - def ajoutOccurences(self,longueur,lOcc):

1085 """ Ajoute la liste des occurrences lOcc à self.seq_repeat """ 1086 lNonOverlap, lOverlap = self.checkOverlap(longueur,lOcc) 1087 if len(lNonOverlap) == 1: 1088 # bloc non chevauchant unique, on l'ajoute aux blocs chevauchants 1089 # car il peut y en avoir plusieurs qui ont été césurés 1090 bisect.insort_right(lOverlap,lNonOverlap[0]) 1091 elif len(lNonOverlap) > 1: 1092 # si plusieurs non chevauchants, on les ajoute à self.seq_repeat 1093 cle = hash(self.texte[lNonOverlap[0][1]:lNonOverlap[0][2]]) 1094 longueur2 = lNonOverlap[0][2] - lNonOverlap[0][1] 1095 locc = [item[1] for item in lNonOverlap] 1096 try: # dico stockant les occurrences d'une chaine 1097 #self.dicoOccLiee[(cle,longueur2)].update(set(locc)) 1098 self.dicoOccLiee[(cle,longueur2)].extend(locc) 1099 except KeyError: 1100 self.dicoOccLiee[(cle,longueur2)] = locc 1101 self.addOccSeq(lNonOverlap) 1102 1103 if len(lOverlap) > 1: # si plusieurs blocs ayant des chevauchements 1104 item_min = lOverlap[0] ; lOcc = [] 1105 for item in lOverlap: assert item_min[0] <= item[0] # le + petit 1106 max_decalageG = max_decalageD = 0 1107 for item in lOverlap: 1108 # on cherche les + grands décalages G et D qui vont être 1109 # utilisés pour césurer l'ensemble des blocs chevauchants 1110 max_decalageG = max(max_decalageG, item[3]) 1111 max_decalageD = max(max_decalageD, item[4]) 1112 for item in lOverlap: 1113 # construction des nouvelles occurences des blocs, on enlève item[3] 1114 # qui est césure éventuellement déjà attachée à un bloc 1115 lOcc.append(item[1]-item[3]+max_decalageG) 1116 # calcul de la nouvelle longueur des blocs 1117 nouveau_debut_item_min = item_min[1]-item_min[3]+max_decalageG 1118 nouveau_fin_item_min = item_min[2]-item_min[4]+max_decalageD 1119 longueur2 = nouveau_fin_item_min - nouveau_debut_item_min 1120 if longueur2 > 0: 1121 # restockage du bloc dans la file de priotrité 1122 cle_hash = hash(self.texte[nouveau_debut_item_min:nouveau_fin_item_min]) 1123 item = (1.0/longueur2,longueur2,cle_hash,lOcc) 1124 #logging.debug('reinclusion de '+str(item)) 1125 self.nb_reinclusion += 1 1126 heapq.heappush(self.hqOccBloc, item) 1127

1128 - def addOccSeq(self,lNonOverlap):

1129 """Ajout effectif des occurrences d'un bloc à self.seq_repeat """ 1130 #logging.debug('addOccSeq: lNonOverlap='+str(lNonOverlap)) 1131 cle_dic = hash(self.texte[lNonOverlap[0][1]:lNonOverlap[0][2]]) # cle du bloc 1132 longeur_dic = lNonOverlap[0][0] # longueur du bloc 1133 for longueur,debut,fin,decalageG,decalageD in lNonOverlap: # parcours des occurrences du bloc 1134 #logging.debug('ajout: '+self.texte[debut:debut+longueur]) 1135 self.totalAjout += longueur 1136 # si chevauchement à gauche 1137 #debut_prec,fin_prec = self.seq_repeat[debut] # bloc existant à gauche de l'occ à insérer 1138 debut_prec = self.seq_repeat_deb[debut] 1139 fin_prec = self.seq_repeat_fin[debut] 1140 if debut < fin_prec: #debut_prec < fin_prec and 1141 #logging.debug('addOccSeq: cesureG / '+str((debut_prec,fin_prec))) 1142 pos_cesure = debut - debut_prec # position de la césure dans le bloc 1143 longueur_prec = fin_prec - debut_prec # longueur bloc précédent 1144 cle_prec = hash(self.texte[debut_prec:fin_prec]) # clé bloc précédent 1145 if self.dicoOccLiee.has_key((cle_prec,longueur_prec)): 1146 locc_prec = list(self.dicoOccLiee[(cle_prec,longueur_prec)]) # liste des occ du bloc précédent 1147 else: locc_prec = [debut_prec] # si il n'y en a pas alors au moins debut_prec 1148 for debut_occ_prec in locc_prec:# pour chaque occ du bloc précédent, on va le césurer 1149 for i in xrange(debut_occ_prec,debut_occ_prec+longueur_prec):# chaque caractère du bloc est modifié dans self.seq_repeat 1150 if i < debut_occ_prec+pos_cesure: 1151 #self.seq_repeat[i] = (debut_occ_prec,debut_occ_prec+pos_cesure) 1152 self.seq_repeat_deb[i] = debut_occ_prec 1153 self.seq_repeat_fin[i] = debut_occ_prec+pos_cesure 1154 else: 1155 #self.seq_repeat[i] = (i,i) # partie césurée qui va être remodifiée par le nouveau bloc 1156 self.seq_repeat_deb[i] = i 1157 self.seq_repeat_fin[i] = i 1158 self.totalRogneG += 1 1159 # suppression de l'ancienne chaine du bloc dans le dico et ajout du nouveau bloc précédent césuré 1160 if self.dicoOccLiee.has_key((cle_prec,longueur_prec)): del self.dicoOccLiee[(cle_prec,longueur_prec)] 1161 try: self.dicoOccLiee[hash(self.texte[locc_prec[0]:locc_prec[0]+pos_cesure]),pos_cesure].extend(locc_prec) 1162 except KeyError: self.dicoOccLiee[hash(self.texte[locc_prec[0]:locc_prec[0]+pos_cesure]),pos_cesure]=locc_prec 1163 # chevauchement à droite 1164 #debut_suiv,fin_suiv = self.seq_repeat[fin] # bloc suivant 1165 debut_suiv = self.seq_repeat_deb[fin] 1166 fin_suiv = self.seq_repeat_fin[fin] 1167 if debut_suiv < fin: 1168 #logging.debug('addOccSeq: cesureG / '+str((debut_suiv,fin_suiv))) 1169 pos_cesure = fin - debut_suiv # position de la césure dans le bloc suivant 1170 longueur_suiv = fin_suiv - debut_suiv # longueur du bloc suivant 1171 cle_suiv = hash(self.texte[debut_suiv:fin_suiv]) # cle du bloc suivant 1172 if self.dicoOccLiee.has_key((cle_suiv,longueur_suiv)): # occurrences du bloc suivant 1173 locc_suiv = list(self.dicoOccLiee[(cle_suiv,longueur_suiv)]) 1174 else: locc_suiv = [debut_suiv] # au minimum debut_suiv 1175 nouv_longueur_suiv = longueur_suiv - pos_cesure # nouvelle longueur du bloc après césure 1176 nouv_locc_suiv = [] # nouvelle liste des occurrences du bloc suivant après césure 1177 for debut_occ_suiv in locc_suiv: # pour chaque occurrence du bloc suivant 1178 for i in xrange(debut_occ_suiv,debut_occ_suiv+longueur_suiv): # chaque caractère du bloc suivant à césurer 1179 if i < debut_occ_suiv+pos_cesure: 1180 #self.seq_repeat[i] = (i,i) # partie à césurer 1181 self.seq_repeat_deb[i] = i ; self.seq_repeat_fin[i] = i 1182 else: 1183 #self.seq_repeat[i] = (debut_occ_suiv+pos_cesure,debut_occ_suiv+longueur_suiv) # partie conservée 1184 self.seq_repeat_deb[i] = debut_occ_suiv+pos_cesure 1185 self.seq_repeat_fin[i] = debut_occ_suiv+longueur_suiv 1186 nouv_locc_suiv.append(debut_occ_suiv+pos_cesure) # stockage du nouveau début du bloc suivant 1187 self.totalRogneD += 1 1188 # suppression de l'ancienne chaine du bloc dans le dico et ajout du nouveau bloc suivant césuré 1189 if self.dicoOccLiee.has_key((cle_suiv,longueur_suiv)): del self.dicoOccLiee[(cle_suiv,longueur_suiv)] 1190 try: self.dicoOccLiee[hash(self.texte[nouv_locc_suiv[0]:nouv_locc_suiv[0]+nouv_longueur_suiv]),nouv_longueur_suiv].extend(nouv_locc_suiv) 1191 except KeyError: self.dicoOccLiee[hash(self.texte[nouv_locc_suiv[0]:nouv_locc_suiv[0]+nouv_longueur_suiv]),nouv_longueur_suiv]=nouv_locc_suiv 1192 # ajout effectif du bloc après le travail de mise à jour des blocs chevauchants 1193 #if debut < fin_prec: assert self.seq_repeat[debut] == (debut,debut), self.seq_repeat[debut-5:debut+5] 1194 #if debut_suiv < fin: assert self.seq_repeat[fin] == (fin,fin), self.seq_repeat[fin-5:fin+5] 1195 for i in xrange(debut,fin): 1196 #self.seq_repeat[i] = (debut,fin) 1197 self.seq_repeat_deb[i] = debut 1198 self.seq_repeat_fin[i] = fin

1199

1200 - def checkOverlap(self,longueur,lOcc):

1201 '''Recherche des chevauchements gauche et droits d'une liste d'occurrences d'un bloc. 1202 Les césures potentielles sont recherchées et stockées avec les blocs associés. 1203 lNonOverlap est une liste d'occurrences sans chevauchement et lOverlap avec. 1204 lOverlap est ordonée de façon croissante sur la longueur des blocs césurés. 1205 les overlap G et D sont résolus ensemble''' 1206 ###logging.debug(str(longueur)+'/'+str(lOcc)) 1207 lNonOverlap = [] ; lOverlap = [] ; discarded = 0 1208 for occ in lOcc: 1209 debut = occ ; fin = occ+longueur 1210 try: 1211 #d1,f1 = self.seq_repeat[debut] # bloc existant au début du bloc à insérer 1212 d1 = self.seq_repeat_deb[debut] ; f1 = self.seq_repeat_fin[debut] 1213 #d2,f2 = self.seq_repeat[fin] # bloc existant à la fin du bloc à insérer 1214 d2 = self.seq_repeat_deb[fin] ; f2 = self.seq_repeat_fin[fin] 1215 except IndexError: # sale 1216 return lNonOverlap, lOverlap 1217 ###logging.debug((d1,f1)) 1218 if d1 <= debut < fin <= f1: 1219 # bloc courant inclus dans un autre bloc, on le discard 1220 discarded += 1 1221 ###logging.debug(str(debut) + ' discarded') 1222 else: 1223 overlapG = d1 <= debut < f1 <= fin # chevauchement gauche ? 1224 overlapD = debut <= d2 < fin <= f2 # chevauchement droit ? 1225 # recherche des points de césure 1226 if overlapG: cesureG = self.resoudre_recouvrement([debut,f1,[d1,f1],[debut,fin]]) 1227 else: cesureG = debut 1228 if overlapD: cesureD = self.resoudre_recouvrement([d2,fin,[debut,fin],[d2,f2]]) 1229 else: cesureD = fin 1230 #logging.debug('checkOverlap: cesureG = '+str(cesureG)+' / cesureD = '+str(cesureD)) 1231 # calcul des décalages 1232 decalageG = cesureG - debut ; decalageD = fin - cesureD 1233 # ajout des blocs avec infos de césure dans les listes résultat 1234 if (not overlapG and not overlapD) or (decalageG == decalageD == 0): 1235 assert cesureG == debut and cesureD == fin 1236 lNonOverlap.append((longueur,debut,debut+longueur,0,0)) 1237 else: bisect.insort_right(lOverlap,(cesureD-cesureG,cesureG,cesureD,decalageG,decalageD)) 1238 assert len(lOcc) == discarded + len(lNonOverlap) + len(lOverlap) 1239 #logging.debug('discarded = '+str(discarded) +' / lNonOverlap = '+str(lNonOverlap)+' / lOverlap = '+str(lOverlap)) 1240 return lNonOverlap, lOverlap

1241

1242 - def transformHeapQueue(self):

1243 """ Transforme self.blocs_texte en une file de priorité indexé par la taille des blocs: 1244 les blocs les + grands sont prioritaires. Un bloc est constitué de son index, 1245 sa longueur, sa cle unique et sa liste d'occurrences""" 1246 hq = [] ; nb_bloc = 0 ; tot=0 ; nb_occ = 0 1247 for longueur, dicoOcc in self.blocs_texte.iteritems(): 1248 for cle_hash, lOcc in dicoOcc.iteritems(): 1249 # item indexé par l'inverse de la longueur pour avoir les blocs 1250 # les plus longs au début du heapq 1251 item = (1.0/longueur,longueur,cle_hash,lOcc) 1252 heapq.heappush(hq, item) 1253 nb_bloc += 1 1254 nb_occ += len(lOcc) 1255 tot += len(lOcc) * longueur 1256 ###logging.debug( hq) 1257 assert len(hq) == nb_bloc 1258 self.SMEM_nb_bloc = nb_bloc # nb SMEM à l'origine 1259 self.SMEM_nb_occ = nb_occ # nb d'occurences de SMEM à l'origine 1260 self.SMEM_tot_size = tot # taille totale des SMEM à l'origine 1261 ###logging.debug("debut eliminer_recouvrements len(chaines dic)=%d",tot) 1262 return hq

1263

1264 - def resoudre_recouvrement__(self, I):

1265 """ part d'un intervalle qui corresponds a un recouvrement 1266 et trouve une cesure judicieuse (par exemple un blanc) 1267 On coupera sur cette cesure 1268 I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] 1269 la chaine la + longue est favorisée""" 1270 #logging.debug('resoudre_recouvrement: I='+str(I)) 1271 taillech1=I[2][1]-I[2][0] 1272 taillech2=I[3][1]-I[3][0] 1273 sep = " .-,!?:;\r\n\t" 1274 if taillech1<=taillech2: 1275 if (I[0] == 0 or I[0] == self.lg_texte1 or 1276 self.texte[I[0]-1] in sep): 1277 return I[0] 1278 if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or 1279 self.texte[I[1]] in sep): 1280 return I[1] 1281 else: 1282 if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or 1283 self.texte[I[1]] in sep): 1284 return I[1] 1285 if (I[0] == 0 or I[0] == self.lg_texte1 or 1286 self.texte[I[0]-1] in sep): 1287 return I[0] 1288 1289 if taillech1<=taillech2: L = range(I[0], I[1] + 1) 1290 else: L = range(I[1], I[0]-1, -1) 1291 #L = range(I[0], I[1]+1) 1292 for x in L: 1293 if self.texte[x] == ' ': 1294 return x 1295 for x in L: 1296 if self.texte[x] in sep: 1297 return x 1298 return L[0]

1299

Source Code for Module medite.MediteAppli.recouvrement