medite.MediteAppli.aligne

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 copy, logging, bisect 20

21 -class Alignement:

22 - def alignement(self,L1,L2,texte1,texte2,lt1):

23 raise NotImplementedError

24

25 -class AlignGlouton (Alignement):

26

27 - def alignement(self,L1,L2,texte1,texte2,lt1):

28 """ Alignement Glouton entre les 2 séquences 29 pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str) 30 post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \ 31 (len(__return__[0])+1==len(__return__[1])) 32 """ 33 # dicoPos1 stocke pour chaque bloc de L1 ses positions dans cette liste 34 logging.log(5,"debut _appelGlouton") 35 llh1 = [] 36 llh2 = [] 37 i=0 38 for bloc in L1: 39 cle = hash(texte1[bloc[0]:bloc[1]]) 40 llh1.append([bloc[1]-bloc[0],cle,i]) 41 i += 1 42 43 # logging.log(5,'init L1 done') 44 i = 0 45 for bloc in L2: 46 cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1]) 47 llh2.append([bloc[1]-bloc[0],cle,i]) 48 i +=1 49 50 # logging.log(5,'init L2 done') 51 r1,r2 = self._gloutonRecur(llh1,llh2) 52 res1=[] 53 res2=[] 54 r1.sort() 55 r2.sort() 56 57 58 #formatage des listes de retour pour les deplacements 59 lastkey = 0 60 for key in r1 : 61 l = [] 62 for i in xrange(lastkey,key): 63 l.append(L1[i]) 64 res1.append((L1[key],l)) 65 lastkey = key+1 66 if lastkey < len(L1) : 67 l = [] 68 for i in xrange(lastkey,len(L1)): 69 l.append(L1[i]) 70 res1.append((None,l)) 71 72 lastkey = 0 73 for key in r2 : 74 l = [] 75 for i in xrange(lastkey,key): 76 l.append(L2[i]) 77 res2.append((L2[key],l)) 78 lastkey = key+1 79 if lastkey < len(L2) : 80 l = [] 81 for i in xrange(lastkey,len(L2)): 82 l.append(L2[i]) 83 res2.append((None,l)) 84 85 return res1,res2

86

87 - def _gloutonSplit(self,l1,l2):

88 """ Identifie les positions du bloc le plus long commun aux deux listes 89 @type l1: list 90 @param l1: liste de liste de blocs au format suivant [longueur du bloc,hash du bloc, position du bloc dans la liste initaiale des blocs] 91 @type l2: list 92 @param l2: liste de liste de blocs au format suivant [longueur du bloc,hash du bloc, position du bloc dans la liste initaiale des blocs] 93 @rtype: list 94 @return: les 2 éléments communs si on les trouve, None,None sinon 95 """ 96 97 #On copie les listes afins de ne pas modifier les listes initiales 98 l1Copy=copy.copy(l1) 99 l2Copy=copy.copy(l2) 100 # tri des listes par taille des blocs croissants 101 l1Copy.sort() 102 l2Copy.sort() 103 #on inverse pour avoir un tri par taille de blocs décroissants 104 l1Copy.reverse() 105 l2Copy.reverse() 106 trouve = False 107 i = 0 108 109 #tant que l'on a pas trouvé l'élément commun ou que tous les éléments de l1Copy ont été parcourus 110 while trouve == False and i < (len(l1Copy)): 111 j = 0 112 113 #on cherche l'élément de la liste l2Copy de hash egal a l'element actuel 114 #on boucle tant qu'on a un élément dont la taille du bloc est inférieur ou egale a l'éléemnt de l12 auquel on compare puisque les listes sont triées 115 while l1Copy[i][1] != l2Copy[j][1] and j < (len(l2Copy))-1 and l1Copy[i][0]<=l2Copy[j][0] : 116 j+=1 117 118 #position du plus garnd bloc commun trouvée 119 if l1Copy[i][1] == l2Copy[j][1]: 120 trouve = True 121 else : 122 i+=1 123 124 if trouve == False : 125 return None,None 126 else : 127 return l1Copy[i],l2Copy[j]

128

129 - def _gloutonRecur(self,lenHashPos1,lenHashPos2):

130 """ Appel recursif pour l'algorithme glouton 131 @type lenHashPos1: list 132 @param lenHashPos1: liste de liste de blocs au format suivant [longueur du bloc,hash du bloc, position du bloc dans la liste initaiale des blocs] 133 @type lenHashPos2: list 134 @param lenHashPos2: liste de liste de blocs au format suivant [longueur du bloc,hash du bloc, position du bloc dans la liste initaiale des blocs] 135 @rtype: list 136 @return: les positions des plus longs blocs communs, None,None si il n'y en a pas 137 """ 138 #une liste vide : condition d'arret de la recusion 139 if (len(lenHashPos1) != 0 and len(lenHashPos2) != 0) : 140 #recuperation des objets représentant le bloc commun le plus long au deux listes 141 blocSplit1,blocSplit2=self._gloutonSplit(lenHashPos1, lenHashPos2) 142 143 #pas de bloc commun trouvé 144 if (blocSplit1 == None or blocSplit2 == None) : 145 return [],[] 146 #position des objets représentant le bloc commun le plus long dans les listes placées en parametre afin de scinder celles-ci au bon endroit 147 posSplit1 = lenHashPos1.index(blocSplit1) 148 posSplit2 = lenHashPos2.index(blocSplit2) 149 150 #recherche a gauche 151 blocAlignesGauche1,blocAlignesGauche2= self._gloutonRecur(lenHashPos1[:posSplit1],lenHashPos2[:posSplit2]) 152 153 #recherche a droite 154 blocAlignesDroite1,blocAlignesDroite2= self._gloutonRecur(lenHashPos1[posSplit1+1:],lenHashPos2[posSplit2+1:]) 155 156 157 #on concatene les resultat (on ne peut pas faire None.extend() 158 if len(blocAlignesGauche1) == 0 or blocAlignesGauche1 == None: 159 #pas de resultat a gauche 160 if blocAlignesDroite1 == None : blocAlignesDroite1 = [] 161 #on concatene le resultat actuel au resultat de la recherche a droite 162 res1 = [blocSplit1[2]] 163 res1.extend(blocAlignesDroite1) 164 else : 165 if blocAlignesDroite1 == None : blocAlignesDroite1 = [] 166 #concatenation resultat recherche gauche, resultat actuel, resultat recherche droite 167 res1 = blocAlignesGauche1 168 res1.extend([blocSplit1[2]]) 169 res1.extend(blocAlignesDroite1) 170 171 172 if len(blocAlignesGauche2) == 0 or blocAlignesGauche2 == None: 173 #pas de resultat a gauche 174 if blocAlignesDroite2 == None : blocAlignesDroite2 = [] 175 #on concatene le resultat actuel au resultat de la recherche a droite 176 res2 = [blocSplit2[2]] 177 res2.extend(blocAlignesDroite2) 178 else : 179 if blocAlignesDroite2 == None : blocAlignesDroite2 = [] 180 #concatenation resultat recherche gauche, resultat actuel, resultat recherche droite 181 res2 = blocAlignesGauche2 182 res2.extend([blocSplit2[2]]) 183 res2.extend(blocAlignesDroite2) 184 185 return res1,res2 186 187 else : 188 return [],[]

189 190

191 -class AlignLIS (Alignement):

192

193 - def _couverture(self,pi):

194 """Calcule la couverture d'une liste d'entiers 195 @type pi: list 196 @param pi: la liste d'entiers dont on veut calculer la couverture 197 @rtype: list of list 198 @return: la couverture de pi 199 """ 200 tailleCouverture = 0 201 couverture=[] 202 couvertureLast=[] 203 for i in xrange(len(pi)): 204 j=0 205 206 while (j < tailleCouverture) and (pi[i][0] > couvertureLast[j]) : 207 #recherche de l'endroit ou il faut inserer l'element 208 j+=1 209 #insertion de l'élément dans la couverture 210 if j == tailleCouverture : 211 #on doit créer une nouvelle sequence dans la couverture 212 tailleCouverture+=1 213 couverture.append([pi[i]]) 214 couvertureLast.append(pi[i][0]) 215 else : 216 couverture[j].append(pi[i]) 217 couvertureLast[j]=pi[i][0] 218 219 return couverture

220

221 - def _lcis(self,couverture):

222 """Calcule la plus longue sous séquence améliorante d'une liste a partir de sa couverture 223 @type couverture: list of list 224 @param couverture: la couverture 225 @rtype: list 226 @return: la plus longue sous séquence améliorante 227 @see: #couverture 228 """ 229 i = len(couverture)-1 230 if i<0 : return [] 231 I = [] 232 # 233 #si on a une couverture de taille i, la plus longue sous sequence comune aura i blocs 234 #si la derniere séquence de la couverture a plusieurs éléments, c'est qu'on peut trouver autant de sous sequences communes aux deux textes qu'il n'y a d'éléments dans cette derniere séquence 235 #on choisit r le plus petit possible afin d'obtenir la sous séquence la plus décalée vers la gauche du texte 236 237 #initialisation 238 #r = random.randint(0,len(couverture[i])-1) 239 r = len(couverture[i])-1 240 #r = 0 241 242 x = couverture[i][r] 243 I.append(x) 244 while (i > 0) : 245 trouve = False 246 j = 0 247 #on cherche l'élément de position maximal précédent le dernier élément placé dans la plus longue sous-séquence commune 248 #(les éléments sont triés par ordre de position décroissante dans les séquences de la couverture) 249 while trouve == False : 250 if couverture[i-1][j][0] < x[0] : 251 y = couverture[i-1][j] 252 trouve = True 253 else : 254 j+=1 255 x = y 256 i-=1 257 I.append(x) 258 259 I.reverse() 260 return I

261 262

263 - def _posOcurrences(self,c,l,posC):

264 """ 265 cherche les positions de c dans la liste l, le resultat est renvoyé dans l'ordre décroissant des indexes 266 @type c: object 267 @param c: l'objet dont on cherche la position des occurences 268 @type l: list 269 @param l: la liste dans laquelle on cherche les positions de c 270 @rtype : list 271 @return: positions auxquelles on a trouvé c dans l 272 """ 273 r = [] 274 for i in xrange(len(l)) : 275 if c == l[i] : 276 r.append((i,posC)) 277 278 r.reverse() 279 return r

280

281 - def _creerPi(self,S1,S2):

282 """Crée la liste PI(S1,S2), liste des positions de chaque élément de S1 dans S2 dans l'ordre décroissant 283 @type S1: list 284 @param S1: liste d'objets 285 @type S2: list 286 @param S2: list d'objets 287 @rtype : list 288 @return : liste des positions de chaque élément de S1 dans S2 dans l'ordre décroissant 289 """ 290 PI = [] 291 for i in xrange(len(S1)) : 292 PI.extend(self._posOcurrences(S1[i],S2,i)) 293 return PI

294 295

296 - def _init_alignement(self,L1,L2,texte1,texte2,lt1):

297 """ Transformation en un alphabet ordonné """ 298 Lkey1 = [] 299 Lkey2 = [] 300 301 #création des listes de hash 302 303 for bloc in L1: 304 cle = hash(texte1[bloc[0]:bloc[1]]) 305 Lkey1.append((cle,0)) 306 307 for bloc in L2: 308 cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1]) 309 Lkey2.append((cle,0)) 310 311 return Lkey1, Lkey2

312

313 - def alignement(self,L1,L2,texte1,texte2,lt1):

314 """ Alignement LIS entre les 2 séquences 315 pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str) 316 post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \ 317 (len(__return__[0])+1==len(__return__[1])) 318 """ 319 Lkey1, Lkey2 = self._init_alignement(L1,L2,texte1,texte2,lt1) 320 #création des listes PI 321 PI = self._creerPi(Lkey2,Lkey1) 322 #recherche de la plus longue sous-sequence améliorante 323 lcis = self._lcis(self._couverture(PI)) 324 325 326 key1=[] 327 key2=[] 328 for i in xrange(len(lcis)) : 329 key2.append(lcis[i][1]) 330 key1.append(lcis[i][0]) 331 332 key1.sort() 333 key2.sort() 334 #on recrée la liste des bloc correspondants 335 res1=[] 336 res2=[] 337 338 lastkey=0 339 for key in key2 : 340 l = [] 341 for i in xrange(lastkey,key): 342 l.append(L2[i]) 343 res1.append((L2[key],l)) 344 lastkey = key+1 345 if lastkey < len(L2) : 346 l = [] 347 for i in xrange(lastkey,len(L2)): 348 l.append(L2[i]) 349 res1.append((None,l)) 350 351 352 lastkey=0 353 for key in key1 : 354 l = [] 355 for i in xrange(lastkey,key): 356 l.append(L1[i]) 357 res2.append((L1[key],l)) 358 lastkey=key+1 359 360 if lastkey < len(L1) : 361 l = [] 362 for i in xrange(lastkey,len(L1)): 363 l.append(L1[i]) 364 res2.append((None,l)) 365 366 #print res2,res1 367 return res2,res1

368

369 -class AlignHIS (AlignLIS):

370 - def _posOcurrences(self,c,l,posC):

371 """ 372 cherche les positions de c dans la liste l, le resultat est renvoyé dans l'ordre décroissant des indexes 373 @type c: object 374 @param c: l'objet dont on cherche la position des occurences 375 @type l: list 376 @param l: la liste dans laquelle on cherche les positions de c 377 @rtype : list 378 @return: positions auxquelles on a trouvé c dans l 379 """ 380 r = [] 381 for i in xrange(len(l)) : 382 if c == l[i] : 383 r.append((i,posC,c)) 384 385 r.reverse() 386 return r

387

388 - def _init_alignement(self,L1,L2,texte1,texte2,lt1):

389 """ Transformation en un alphabet ordonné """ 390 Lkey1 = [] 391 Lkey2 = [] 392 393 #création des listes de hash 394 395 for bloc in L1: 396 cle = hash(texte1[bloc[0]:bloc[1]]) 397 longueur = bloc[1] - bloc[0] 398 Lkey1.append((cle, longueur)) 399 400 for bloc in L2: 401 cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1]) 402 longueur = bloc[1] - bloc[0] 403 Lkey2.append((cle,longueur)) 404 405 return Lkey1, Lkey2

406

407 - def _lcis(self,couverture):

408 """Calcule la plus longue sous séquence améliorante d'une liste a partir de sa couverture 409 @type couverture: list of list 410 @param couverture: la couverture 411 @rtype: list 412 @return: la plus longue sous séquence améliorante 413 @see: #couverture 414 """ 415 i = len(couverture)-1 416 if i<0 : return [] 417 I = [] 418 # 419 #si on a une couverture de taille i, la plus longue sous sequence comune aura i blocs 420 #si la derniere séquence de la couverture a plusieurs éléments, c'est qu'on peut trouver autant de sous sequences communes aux deux textes qu'il n'y a d'éléments dans cette derniere séquence 421 #on choisit r le plus petit possible afin d'obtenir la sous séquence la plus décalée vers la gauche du texte 422 423 #initialisation 424 #r = random.randint(0,len(couverture[i])-1) 425 r = len(couverture[i])-1 426 #r = 0 427 debug = False 428 x = couverture[i][r] 429 if debug: print x 430 I.append(x) 431 while (i > 0) : 432 trouve = False 433 j = 0 434 liste_y = [] 435 #on cherche l'élément de position maximal précédent le dernier élément placé dans la plus longue sous-séquence commune 436 #(les éléments sont triés par ordre de position décroissante dans les séquences de la couverture) 437 if debug: print couverture[i-1] 438 while j < len(couverture[i-1]): #trouve == False : 439 element = couverture[i-1][j] 440 pos = element[0] ; pos2 = element[1] ; poids = element[2][1] 441 if pos < x[0] and pos2 < x[1]: 442 liste_y.append( element) 443 j += 1 444 else : 445 j+=1 446 assert len(liste_y) > 0 447 if debug: print liste_y 448 max_y = 0 449 for candy in liste_y: 450 poids = candy[2][1] 451 if poids > max_y: 452 y = candy 453 max_y = poids 454 x = y 455 i-=1 456 I.append(x) 457 if debug: print x 458 if debug: print '-------------' 459 if debug: print '====================' 460 assert len(I) == len(couverture) 461 I.reverse() 462 if debug: print I 463 return I

464

465 -class AlignHISCont(AlignHIS):

466 """HIS + contraintes de non chevauchement entre blocs de la lcs 467 car recouvrement non résolus précédemment """

468 - def alignement(self,L1,L2,texte1,texte2,lt1):

469 """ Alignement LIS entre les 2 séquences 470 pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str) 471 post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \ 472 (len(__return__[0])+1==len(__return__[1])) 473 """ 474 Lkey1, Lkey2 = self._init_alignement(L1,L2,texte1,texte2,lt1) 475 #création des listes PI 476 PI = self._creerPi(Lkey2,Lkey1) 477 #recherche de la plus longue sous-sequence améliorante 478 lcis = self._lcis(self._couverture(PI)) 479 480 key1=[] 481 key2=[] 482 for i in xrange(len(lcis)) : 483 key2.append((lcis[i][1],L2[i][0],L2[i][1])) 484 key1.append((lcis[i][0],L1[i][0],L1[i][1])) 485 486 key1.sort() 487 key2.sort() 488 #print key1,key2 489 k1 = [] ; k2 = [] 490 end1 = end2 = -1 491 for b1,b2 in zip(key1,key2): 492 c1, d1, f1 = b1 493 c2, d2, f2 = b2 494 if end1 <= d1 and end2 <= d2: 495 k1.append(c1) 496 k2.append(c2) 497 end1 = f1 498 end2 = f2 499 key1 = k1 500 key2 = k2 501 #on recrée la liste des bloc correspondants 502 res1=[] 503 res2=[] 504 505 lastkey=0 506 for key in key2 : 507 l = [] 508 for i in xrange(lastkey,key): 509 l.append(L2[i]) 510 res1.append((L2[key],l)) 511 lastkey = key+1 512 if lastkey < len(L2) : 513 l = [] 514 for i in xrange(lastkey,len(L2)): 515 l.append(L2[i]) 516 res1.append((None,l)) 517 518 519 lastkey=0 520 for key in key1 : 521 l = [] 522 for i in xrange(lastkey,key): 523 l.append(L1[i]) 524 res2.append((L1[key],l)) 525 lastkey=key+1 526 527 if lastkey < len(L1) : 528 l = [] 529 for i in xrange(lastkey,len(L1)): 530 l.append(L1[i]) 531 res2.append((None,l)) 532 533 #print res2,res1 534 return res2,res1

535

536 -class AlignHISVo (AlignHIS):

537 - def _init_alignement(self,L1,L2,texte1,texte2,lt1):

538 """ Transformation en un alphabet ordonné """ 539 Lkey1 = [] 540 Lkey2 = [] 541 dicoKey = {} 542 #création des listes de hash 543 num = 0 544 for bloc in L1: 545 cle = hash(texte1[bloc[0]:bloc[1]]) 546 longueur = bloc[1] - bloc[0] 547 548 if not dicoKey.has_key(cle): 549 dicoKey[cle] = num 550 numero = num 551 num += 1 552 else: 553 numero = dicoKey[cle] 554 Lkey1.append((numero, longueur, cle)) 555 556 j = 0 557 for bloc in L2: 558 cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1]) 559 longueur = bloc[1] - bloc[0] 560 Lkey2.append((dicoKey[cle],j,longueur, cle)) 561 j += 1 562 563 return Lkey1, Lkey2, dicoKey

564

565 - def _lis(self,Lkey1, Lkey2, dicoKey):

566 L = liste_vo() 567 node = {} 568 for i in xrange(len(Lkey2)): 569 car = Lkey2[i] 570 #print car,L.liste 571 pos = L.prev(car) 572 if pos is not None: 573 s = L.liste[pos] 574 else: s = None 575 576 pos = L.next(s) 577 if pos is not None: 578 t = L.liste[pos] 579 else: t = None 580 581 if t is not None: 582 L.delete(pos) 583 L.insert(pos, car) 584 if s is None: val = None 585 else: val = s 586 node[car] = (car, val) 587 #print L.liste 588 #print node 589 590 maxi = 0 591 for car in node.iterkeys(): 592 maxi = max(maxi, car) 593 liste = [] 594 car = maxi 595 while car is not None: 596 liste.append(car) 597 car2, car3 = node[car] 598 assert car2 == car 599 car = car3 600 return liste

601

602 - def _his(self,Lkey1, Lkey2, dicoKey):

603 L = liste_vo() 604 node = {} 605 for i in xrange(len(Lkey2)): 606 car = Lkey2[i] 607 longueur = car[2] 608 #print car,L.liste 609 pos = L.prev(car) 610 if pos is not None: 611 s = L.liste[pos] 612 v = s[2] 613 else: s = None ; v = 0 614 615 pos = L.next(s) 616 if pos is not None: 617 t = L.liste[pos] 618 w = t[2] 619 else: t = None ; w = 0 620 621 while t is not None: 622 if v + longueur < w: 623 break 624 L.delete(pos) 625 pos = L.next(t) 626 if pos is not None: 627 t = L.liste[pos] 628 w = t[2] 629 else: t = None ; w = 0 630 631 if t is None or car[0] < t: 632 car = car[0],car[1] , car[2] + v, car[3] 633 L.insert(pos, car) 634 if s is None: val = None 635 else: val = s 636 node[car] = (car, val) 637 #print L.liste 638 #print node 639 640 maxi = 0 641 for car in node.iterkeys(): 642 maxi = max(maxi, car) 643 liste = [] 644 car = maxi 645 while car is not None: 646 liste.append(car) 647 car2, car3 = node[car] 648 assert car2 == car 649 car = car3 650 return liste 651

652 - def alignement(self,L1,L2,texte1,texte2,lt1):

653 """ Alignement LIS entre les 2 séquences 654 pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str) 655 post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \ 656 (len(__return__[0])+1==len(__return__[1])) 657 """ 658 Lkey1, Lkey2, dicoKey = self._init_alignement(L1,L2,texte1,texte2,lt1) 659 lcis = self._his(Lkey1, Lkey2, dicoKey) 660 #print lcis, len(Lkey1), len(Lkey2) 661 662 key1=[] 663 key2=[] 664 for i in xrange(len(lcis)) : 665 key2.append(lcis[i][1]) 666 key1.append(lcis[i][0]) 667 668 key1.sort() 669 key2.sort() 670 #on recrée la liste des bloc correspondants 671 res1=[] 672 res2=[] 673 674 lastkey=0 675 for key in key2 : 676 l = [] 677 for i in xrange(lastkey,key): 678 l.append(L2[i]) 679 res1.append((L2[key],l)) 680 lastkey = key+1 681 if lastkey < len(L2) : 682 l = [] 683 for i in xrange(lastkey,len(L2)): 684 l.append(L2[i]) 685 res1.append((None,l)) 686 687 688 lastkey=0 689 for key in key1 : 690 l = [] 691 for i in xrange(lastkey,key): 692 l.append(L1[i]) 693 res2.append((L1[key],l)) 694 lastkey=key+1 695 696 if lastkey < len(L1) : 697 l = [] 698 for i in xrange(lastkey,len(L1)): 699 l.append(L1[i]) 700 res2.append((None,l)) 701 702 #print res2,res1 703 return res2,res1

704

705 -class liste_vo(object):

706 - def __init__(self):

707 self.liste = []

708 - def prev(self, car):

709 if len(self.liste) == 0 or car == None: 710 return None 711 else: 712 pos = bisect.bisect_left(self.liste, car) - 1 713 return pos

714 - def next(self, car):

715 if len(self.liste) == 0 or car == None: 716 return None 717 else: 718 pos = bisect.bisect_right(self.liste, car) 719 if pos == len(self.liste): 720 return None 721 else: return pos

722 - def delete(self, pos):

723 assert pos < len(self.liste) 724 del self.liste[pos]

725 - def insert(self, pos,car ):

726 if len(self.liste) > 0: 727 assert pos <= len(self.liste) 728 #assert self.liste[pos-1] <= car <= self.liste[pos], (self.liste[pos-1] , car , self.liste[pos]) 729 else: pos = 0 730 if pos == None: self.liste.append(car) 731 else: self.liste.insert(pos, car)

732 #assert self.liste[pos-1] <= car <= self.liste[pos], (self.liste[pos-1] , car , self.liste[pos]) 733

734 -class Node:

735 - def __init__(self, key):

736 self.key = key 737 self.left = self.right = None

738

739 - def equals(self, node):

740 return self.key == node.key

741

742 -class SplayTree:

743 - def __init__(self):

744 self.root = None 745 self.header = Node(None) #For splay()

746

747 - def insert(self, key):

748 if (self.root == None): 749 self.root = Node(key) 750 return 751 752 self.splay(key) 753 if self.root.key == key: 754 # If the key is already there in the tree, don't do anything. 755 return 756 757 n = Node(key) 758 if key < self.root.key: 759 n.left = self.root.left 760 n.right = self.root 761 self.root.left = None 762 else: 763 n.right = self.root.right 764 n.left = self.root 765 self.root.right = None 766 self.root = n

767

768 - def remove(self, key):

769 self.splay(key) 770 if key != self.root.key: 771 raise 'key not found in tree' 772 773 # Now delete the root. 774 if self.root.left== None: 775 self.root = self.root.right 776 else: 777 x = self.root.right 778 self.root = self.root.left 779 self.splay(key) 780 self.root.right = x

781

782 - def findMin(self):

783 if self.root == None: 784 return None 785 x = self.root 786 while x.left != None: 787 x = x.left 788 self.splay(x.key) 789 return x.key

790

791 - def findMax(self):

792 if self.root == None: 793 return None 794 x = self.root 795 while (x.right != None): 796 x = x.right 797 self.splay(x.key) 798 return x.key

799

800 - def find(self, key):

801 if self.root == None: 802 return None 803 self.splay(key) 804 if self.root.key != key: 805 return None 806 return self.root.key

807

808 - def isEmpty(self):

809 return self.root == None

810

811 - def splay(self, key):

812 l = r = self.header 813 t = self.root 814 self.header.left = self.header.right = None 815 while True: 816 if key < t.key: 817 if t.left == None: 818 break 819 if key < t.left.key: 820 y = t.left 821 t.left = y.right 822 y.right = t 823 t = y 824 if t.left == None: 825 break 826 r.left = t 827 r = t 828 t = t.left 829 elif key > t.key: 830 if t.right == None: 831 break 832 if key > t.right.key: 833 y = t.right 834 t.right = y.left 835 y.left = t 836 t = y 837 if t.right == None: 838 break 839 l.right = t 840 l = t 841 t = t.right 842 else: 843 break 844 l.right = t.left 845 r.left = t.right 846 t.left = self.header.right 847 t.right = self.header.left 848 self.root = t

849 850

851 -class AlignProgDyn (Alignement):

852

853 - def alignement(self,L1,L2,texte1,texte2,lt1):

854 """ Alignement par programmation dynamique entre les 2 séquences 855 pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str) 856 post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \ 857 (len(__return__[0])+1==len(__return__[1])) 858 """ 859 860 logging.log(10, "debut _appelProgDyn") 861 LH1 = [] ; LH2 = [] 862 for bloc in L1: 863 cle = hash(texte1[bloc[0]:bloc[1]]) 864 # print 'hash : ', cle, ' texte : ',texte1[bloc[0]:bloc[1]] 865 LH1.append((cle, bloc[0], bloc[1])) 866 logging.log(10, 'init LH1 done') 867 #print 'taille LH1 : ', len(LH1) 868 for bloc in L2: 869 cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1]) 870 # print 'hash : ', cle, ' texte : ',texte2[bloc[0]-lt1:bloc[1]-lt1] 871 LH2.append((cle, bloc[0], bloc[1])) 872 logging.log(10, 'init LH2 done') 873 #print 'taille LH2 : ', len(LH2) 874 875 876 range_n = xrange(len(LH1)) 877 range_m = xrange(len(LH2)) 878 879 nb1 = 0 880 nb2 = 0 881 882 # Création de la liste des caractères 883 cars = {} 884 for i in xrange(len(L1)) : 885 if not(cars.has_key(LH1[i][0])) : 886 cars[LH1[i][0]] = [] 887 #print "cars : ",cars 888 AIP = [] 889 AP = {} 890 for i in range_n : 891 for j in range_m : 892 # on est sur un appariement ou on est à la fin du texte, dans ce dernier cas on ajoute l'appariement d'office. 893 if LH1[i][0]==LH2[j][0] or (i==len(LH1)-1 and j==len(LH2)-1) : 894 # print "i : ", i 895 # print "\tj : ", j 896 # if i==len(LH1)-1 and j==len(LH2)-1 : 897 # nb1 = i 898 # nb2 = j 899 # else : 900 nb1 = i-1 901 nb2 = j-1 902 903 del AIP[:] 904 905 for c in cars : 906 k = None 907 l = None 908 cout_c = None 909 if len(cars[c])!=0 or c == LH1[i][0] : 910 k_l, k,l = self.lookup_max_kl(cars[c],nb1,nb2) 911 # print "\t\tcars[",c,"] : ", cars[c]," nb1 : ",nb1," nb2 : ",nb2 912 # on a pas de prédécesseur. 913 if k_l == None and k == None and l == None : 914 # soit le caractère courant est le caractère que l'on étudie 915 # on doit donc l'ajouter car c'est un des premiers appariement du texte 916 if c == LH1[i][0] : 917 # print "\t\tPas de prédecesseur." 918 # cout_c = self.calcul_breche(0, 0, LH1[i][1], LH2[j][1]-lt1) 919 # on calcule la breche par rapport au début du texte 920 cout_c = self.calcul_breche2(LH1[0:i-1], LH2[0:j-1]) 921 k = i 922 l = j 923 # Soit ce caractère n'est pas présent avant, on ne l'ajoute pas à la liste. 924 else : 925 continue 926 # on a un prédecesseur 927 else : 928 # print "\t\tPrédecesseur : k : ",k," l : ",l," k_l : ",k_l 929 # cout_c = self.calcul_breche(LH1[k][2], LH2[l][2]-lt1, LH1[i][1], LH2[j][1]-lt1) + AP[(k,l)][0] 930 cout_c = self.calcul_breche2(LH1[k+1:i-1], LH2[l+1:j-1]) + AP[(k,l)][0] 931 bisect.insort_left(AIP,(cout_c,k,l)) 932 #print "\t\tAIP[(",i,",",j,")] : ", AIP 933 cout_c,k,l = AIP[0] 934 AP[(i,j)] = (cout_c,(k,l)) 935 #print "\tAP : ", AP 936 bisect.insort_left(cars[LH1[i][0]], (i+j,i,j)) 937 #print "\tcars i : ",i," j : ",j," : ",cars,"\n" 938 # Fin si 939 # Fin pour 940 # Fin pour 941 942 # Récursion pour le cout minimal 943 index = (len(LH1)-1,len(LH2)-1) 944 945 s1 = [] 946 s2 = [] 947 # print "Construction des liste retournées" 948 moving = True 949 while moving: 950 # print "LH1[",index[0],"] : ",LH1[index[0]][0], "LH2[",index[1],"] : ",LH2[index[1]][0] 951 # si on est pas à la fin du texte ou que les deux blocs courant sont égaux 952 # permet de prendre en compte le dernier appariement que l'on a ajouté d'office, seulement si c'est un vrai appariement 953 if index != (len(LH1)-1,len(LH2)-1) or LH1[index[0]][0] == LH2[index[1]][0] : 954 deplacement1 = [] 955 deplacement2 = [] 956 range1 = 0 957 range2 = 0 958 # on construit les range pour les déplacements. 959 if AP[index][1] != index : 960 range1 = xrange(AP[index][1][0]+1,index[0]) 961 range2 = xrange(AP[index][1][1]+1,index[1]) 962 else : # blocs au début des textes 963 range1 = xrange(0,index[0]) 964 range2 = xrange(0,index[1]) 965 for bloc in range1 : 966 deplacement1.append(L1[bloc]) 967 for bloc in range2 : 968 deplacement2.append(L2[bloc]) 969 s1.append((L1[index[0]], deplacement1)) 970 s2.append((L2[index[1]], deplacement2)) 971 # print 's1 : ',s1 972 # print 's1 : ',s2 973 if AP[index][1] != index : 974 index = AP[index][1] 975 else : 976 moving = False 977 #print "s1 : ", s1 978 #print "s2 : ", s2 979 s1.reverse() 980 s2.reverse() 981 logging.log(10,"Fin _appelProgDyn") 982 return s1,s2

983

984 - def lookup_max_kl(self, liste_couples_anterieurs, nb1, nb2):

985 """ Renvoie le premier couple de valeur compris dans liste_couples_anterieurs tel que leurs composantes soient strictement inférieures à nb1 et nb2 986 @type liste_couples_anterieurs: list 987 @param liste_couples_anterieurs : liste de coordonnées 988 @type nb1: number 989 @param nb1: valeur minimum de la premiere composante du couple étudié 990 @type nb2: number 991 @param nb2: valeur minimum de la deuxieme composante du couple étudié 992 @rtype : list 993 @return : une liste comprenant la somme des composantes du couple de valeur suivis du couple de valeur ou trois fois None si on a pas trouvé de couple strictement inférieur à nb1 et nb2 994 """ 995 k_l = None 996 k = None 997 l = None 998 found = False 999 for i in xrange(len(liste_couples_anterieurs),0,-1): 1000 k_l, k,l = liste_couples_anterieurs[i-1] 1001 if k <= nb1 and l <= nb2: 1002 found = True 1003 break 1004 # on avait des couples antérieurs, mais aucun n'est placé strictement avant (nb1,nb2) 1005 if found == False : 1006 k_l = None 1007 k = None 1008 l = None 1009 return (k_l, k,l)

1010

1011 - def calcul_breche(self, k,l,i,j):

1012 """Calcule la brèche entre deux blocs, se calcule basiquement en faisant i-k+j-l. 1013 @type number 1014 @param k:Coordonée sur le premier texte du premier bloc 1015 @type number 1016 @param l:Coordonée sur le deuxième texte du premier bloc 1017 @type number 1018 @param i:Coordonée sur le premier texte du deuxième bloc 1019 @type number 1020 @param j:Coordonée sur le deuxième texte du deuxième bloc 1021 @rtype : number 1022 @return La valeur de la brèche 1023 """ 1024 # print "calcul de brèche : k , l , i , j : ",k," ",l," ",i," ",j 1025 breche = 0 1026 if k<=i and l<=j: 1027 breche = i-k+j-l 1028 elif k>i and l>j : 1029 breche = k-i+l-j 1030 return breche

1031

1032 - def calcul_breche2(self, l1, l2):

1033 """Calcule la brèche entre deux blocs, 1034 on somme la taille de chaque bloc de l1 1035 on y ajoute ensuite la somme de la taille de chaque bloc de l2 1036 @type list 1037 @param l1: Liste de blocs de la forme (caractère, indice de début, indice de fin) 1038 @type list 1039 @param l2: Liste de blocs de la forme (caractère, indice de début, indice de fin) 1040 @rtype : number 1041 @return La valeur de la brèche 1042 """ 1043 breche = 0 1044 for i in range(len(l1)) : 1045 breche += l1[i][2] - l1[i][1] 1046 for j in range(len(l2)) : 1047 breche += l2[j][2] - l2[j][1] 1048 return breche

1049

1050 -class AlignProgDyn2 (AlignProgDyn):

1051

1052 - def alignement(self,L1,L2,texte1,texte2,lt1):

1053 """ Alignement par programmation dynamique entre les 2 séquences 1054 pre: isinstance(L1,list) and isinstance(L2,list) and isinstance(texte1,str) and isinstance(texte2,str) 1055 post: (len(__return__[0])==len(__return__[1])) or (len(__return__[0])==len(__return__[1])+1) or \ 1056 (len(__return__[0])+1==len(__return__[1])) 1057 """ 1058 1059 logging.log(10, "debut _appelProgDyn") 1060 LH1 = [] ; LH2 = [] 1061 for bloc in L1: 1062 cle = hash(texte1[bloc[0]:bloc[1]]) 1063 # print 'hash : ', cle, ' texte : ',texte1[bloc[0]:bloc[1]] 1064 LH1.append((cle, bloc[0], bloc[1])) 1065 logging.log(10, 'init LH1 done') 1066 #print 'taille LH1 : ', len(LH1) 1067 for bloc in L2: 1068 cle = hash(texte2[bloc[0]-lt1:bloc[1]-lt1]) 1069 # print 'hash : ', cle, ' texte : ',texte2[bloc[0]-lt1:bloc[1]-lt1] 1070 LH2.append((cle, bloc[0], bloc[1])) 1071 logging.log(10, 'init LH2 done') 1072 #print 'taille LH2 : ', len(LH2) 1073 1074 1075 range_n = xrange(len(LH1)) 1076 range_m = xrange(len(LH2)) 1077 1078 nb1 = 0 1079 nb2 = 0 1080 1081 # Création de la liste des caractères 1082 cars = {} 1083 for i in xrange(len(L1)) : 1084 if not(cars.has_key(LH1[i][0])) : 1085 cars[LH1[i][0]] = [] 1086 #print "cars : ",cars 1087 AIP = [] 1088 AP = {} 1089 for i in range_n : 1090 for j in range_m : 1091 if LH1[i][0]==LH2[j][0] or (i==len(LH1)-1 and j==len(LH2)-1) : 1092 if i==len(LH1)-1 and j==len(LH2)-1 : 1093 nb1 = i 1094 nb2 = j 1095 else : 1096 nb1 = i-1 1097 nb2 = j-1 1098 1099 del AIP[:] 1100 1101 for c in cars : 1102 k = None 1103 l = None 1104 min_cout = None 1105 cout_c = None 1106 if len(cars[c])!=0 or c == LH1[i][0] : 1107 if cars[c] != [] : 1108 min_cout, k,l = cars[c][0] 1109 # print "\t\tcars[",c,"] : ", cars[c]," nb1 : ",nb1," nb2 : ",nb2 1110 if min_cout == None and k == None and l == None : # pas de prédecesseurs 1111 if c == LH1[i][0] : 1112 # print "\t\tPas de prédecesseur." 1113 cout_c = self.calcul_breche2(LH1[0:i-1], LH2[0:j-1]) 1114 #cout_c = self.calcul_breche2(0, 0, LH1[i][1], LH2[j][1]-lt1) 1115 k = i 1116 l = j 1117 else : # ce caractère n'est pas présent avant, on ne l'ajoute pas à la liste. 1118 continue 1119 else : 1120 # print "\t\tPrédecesseur : k : ",k," l : ",l," k_l : ",k_l 1121 cout_c = self.calcul_breche2(LH1[k+1:i-1], LH2[l+1:j-1]) + AP[(k,l)][0] 1122 #cout_c = self.calcul_breche2(LH1[k][2], LH2[l][2]-lt1, LH1[i][1], LH2[j][1]-lt1) + AP[(k,l)][0] 1123 bisect.insort_left(AIP,(cout_c,k,l)) 1124 # print "\t\tAIP[(",i,",",j,")] : ", AIP 1125 cout_c,k,l = AIP[0] 1126 AP[(i,j)] = (cout_c,(k,l)) 1127 # print "\tAP : ", AP 1128 bisect.insort_left(cars[LH1[i][0]], (cout_c,i,j)) 1129 # print "\tcars i : ",i," j : ",j," : ",cars,"\n" 1130 # Fin si 1131 # Fin pour 1132 # Fin pour 1133 1134 # Récursion pour le cout minimal 1135 index = (len(LH1)-1,len(LH2)-1) 1136 1137 s1 = [] 1138 s2 = [] 1139 #print "Construction des liste retournées" 1140 moving = True 1141 while moving: 1142 # print "LH1[",index[0],"] : ",LH1[index[0]][0], "LH2[",index[1],"] : ",LH2[index[1]][0] 1143 if index != (len(LH1)-1,len(LH2)-1) or LH1[index[0]][0] == LH2[index[1]][0] : 1144 deplacement1 = [] 1145 deplacement2 = [] 1146 range1 = 0 1147 range2 = 0 1148 if AP[index][1] != index : 1149 range1 = xrange(AP[index][1][0]+1,index[0]) 1150 range2 = xrange(AP[index][1][1]+1,index[1]) 1151 else : 1152 range1 = xrange(0,index[0]) 1153 range2 = xrange(0,index[1]) 1154 for bloc in range1 : 1155 deplacement1.append(L1[bloc]) 1156 for bloc in range2 : 1157 deplacement2.append(L2[bloc]) 1158 s1.append((L1[index[0]], deplacement1)) 1159 s2.append((L2[index[1]], deplacement2)) 1160 # print 's1 : ',s1 1161 # print 's1 : ',s2 1162 if AP[index][1] != index : 1163 index = AP[index][1] 1164 else : 1165 moving = False 1166 #print "s1 : ", s1 1167 #print "s2 : ", s2 1168 s1.reverse() 1169 s2.reverse() 1170 logging.log(10,"Fin _appelProgDyn") 1171 return s1,s2

1172 1173 import unittest, random 1174

1175 -class TestCase(unittest.TestCase):

1176 - def setUp(self):

1177 self.liste = liste_vo()

1178

1179 - def testInsert(self):

1180 self.liste.insert(0, 5) 1181 1182 nb = 7 1183 pos = self.liste.next(nb) 1184 self.liste.insert(pos, nb) 1185 1186 nb = 8 1187 pos = self.liste.next(nb) 1188 self.liste.insert(pos, nb) 1189 1190 taille = 20 1191 random.seed(10) 1192 for id in xrange(taille): 1193 nb = random.randint(1,10) 1194 if nb % 2 == 0: 1195 pos = self.liste.next(nb) 1196 else: pos = self.liste.prev(nb) 1197 1198 self.liste.insert(pos, nb) 1199 1200 print self.liste.liste 1201 for i in xrange(len(self.liste.liste)-2): 1202 assert self.liste.liste[i] <= self.liste.liste[i+1]

1203

1204 - def test2(self):

1205 a = AlignHISVo() 1206 L1 = [()]

1207

1208 -class TestCase__(unittest.TestCase):

1209 - def setUp(self):

1210 self.keys = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 1211 self.t = SplayTree() 1212 for key in self.keys: 1213 self.t.insert(key)

1214

1215 - def testInsert(self):

1216 for key in self.keys: 1217 self.assertEquals(key, self.t.find(key))

1218

1219 - def testRemove(self):

1220 for key in self.keys: 1221 self.t.remove(key) 1222 self.assertEquals(self.t.find(key), None)

1223

1224 - def testLargeInserts(self):

1225 t = SplayTree() 1226 nums = 40#000 1227 gap = 307 1228 i = gap 1229 while i != 0: 1230 t.insert(i) 1231 i = (i + gap) % nums

1232

1233 - def testIsEmpty(self):

1234 self.assertFalse(self.t.isEmpty()) 1235 t = SplayTree() 1236 self.assertTrue(t.isEmpty())

1237

1238 - def testMinMax(self):

1239 self.assertEquals(self.t.findMin(), 0) 1240 self.assertEquals(self.t.findMax(), 9)

1241 1242

1243 - def testFind(self):

1244 print self.t.find(5)

1245 1246 if __name__ == "__main__": 1247 unittest.main() 1248

Source Code for Module medite.MediteAppli.aligne