medite.MediteAppli.feng

31 """Classe effectuant la comparaison des textes en utilisant la methode définie par S. Feng et R. Manmatha 32 """

33 - def __init__(self, txt1, txt2, ignorerSeparateurs=False, ignorerCase=True, ignorerDiacritiques=False, p2=2, calculDep=True , lenMinBlocDep=4, debugLevel = 4):

34 """Constructeur de l'objet 35 36 @param txt1: la premiere version du texte a comparer 37 @type txt1: String 38 @param txt1: la premiere version du texte a comparer 39 @type txt1: String 40 @param ignorerSeparateurs: Optionnel,Définit si l'on souhaite ou non ignorer les separateurs (ponctuations etc..), Faux par defaut 41 @type ignorerSeparateurs: Bool 42 @param ignorerCase: ignore la casse 43 @type ignorerCase: bool 44 @param ignorerDiacritiques: sensibilité aux accents 45 @type ignorerDiacritiques: bool 46 @param p2: paramètre ratio des remplacements pour insertions/suppressions 47 @type p2: integer 48 @param calculDep: Optionnel, defininit si l'on souhaite ou non calculer les deplacements 49 @type calculDep: Bool 50 @param lenMinBlocDep: longueue minimale bloc déplacé 51 @type lenMinBlocDep: integer 52 @param debugLevel: Optionnel,definit le niveau de log, les valeurs suivantes sont utilisées : 53 logging.INFO = tres peu verbeux (affichage du debut et fin de l'algo seulement) 54 logging.DEBUG = peu verbeux 55 4 verbeux (affichage de certaines variables, affichage des textes, affichage de la progression générale du hmm) 56 3 tres verbeux (affichage dans les boucles / methodes) 57 2 tres tres verbeux (affichage des tableaux etc...), tres peu lisible 58 1 maxi debug (affichage de tous les contenus des appels du fichier HMM.py) /!\ les dictionaires de 150 termes c'est pas joli a voir, ne pas utiliser !! 59 @type debugLevel: Integer 60 """ 61 self.texte1 = txt1 62 self.texte2 = txt2 63 self.ignorerSeparateurs = ignorerSeparateurs 64 self.ignorerCase = ignorerCase 65 self.ignorerDiacritiques = ignorerDiacritiques 66 self.calculDep = calculDep 67 self.lenMinBlocDep = lenMinBlocDep 68 self.p2 = p2 69 #config des logs 70 #level logging.INFO = tres peu verbeux (affichage du debut et fin de l'algo seulement) 71 #level logging.DEBUG = peu verbeux 72 #level 4 verbeux (affichage de certaines variables, affichage des textes, affichage de la progression générale du hmm) 73 #level 3 tres verbeux (affichage dans les boucles / methodes) 74 #level 2 tres tres verbeux (affichage des tableaux etc...), tres peu lisible 75 #level 1 maxi debug (affichage de tous les contenus des appels du fichier HMM.py) /!\ les dictionaires de 150 termes c'est pas joli a voir, ne pas utiliser !! 76 logging.basicConfig(level=debugLevel,datefmt='%a, %d %b %Y %H:%M:%S',format='%(asctime)s %(levelname)s %(message)s')#,filename='hmm.log',filemode='w') 77 logging.info("algoFeng initialisé, separateurs ignorés : %s, loglevel : %s", ignorerSeparateurs,debugLevel) 78 if __debug__ : 79 logging.log(4,"texte1 :\n%s",self.texte1) 80 logging.log(4,"texte2 :\n%s",self.texte2) 81 82 if self.ignorerDiacritiques: 83 #self.sepTable = string.maketrans('çéèàùâêîôûäëïöüÿÇÉÈÀÙÂÊÎÔÛÄËÏÖÜ','ceeauaeiouaeiouyCEEAUAEIOUAEIOU') 84 #self.texte1 = self.texte1.translate(self.sepTable) 85 #self.texte2 = self.texte2.translate(self.sepTable) 86 # fait la conversion pour les chaine unicode 87 # self.texte1 = unicodedata.normalize('NFKD', unicode(self.texte1,'ascii')).encode('ASCII', 'ignore') 88 # self.texte2 = unicodedata.normalize('NFKD', unicode(self.texte2,'ascii')).encode('ASCII', 'ignore') 89 self.texte1 = transDiacritic(self.texte1) 90 self.texte2 = transDiacritic(self.texte2) 91 92 if self.ignorerCase: 93 # si comparaison insensible à la casse, on convertit les 2 chaines en minuscule 94 self.texte1 = self.texte1.lower() 95 self.texte2 = self.texte2.lower()

96 97 98 99 # self.prof = hotshot.Profile("./statFile") 100 101

102 - def aligne(self):

103 """ 104 Effectue la comparaison des textes, fonction principale 105 106 Renvoie un tuplet ((blocsAlignes1,blocsAlignes2),(blocsSupprimés Texte1,blocs Ajouté Texte 2), 107 (dep1,dep2),(corespondances entre Dep),(remp1,remp2)) 108 109 @return: blocs sur lesquels on aligne pour le texte1 et texte2, blocs supprimés, blocs ajoutés, blocs deplacés du texte1, blocs deplacés du texte2 110 @type: ([(posAligneTxt1Debut,posAligneTxt1Fin),...],[(posAligneTxt2Debut,posAligneTxt2Fin),...]),([(posSupprTxt1Debut,posSupprTxt1Fin),...],[(posAjoutTxt2Debut,posAjoutTxt2Fin),...]),([(posDepTxt1Debut,posDepTxt1Fin),...],[(posDepTxt2Debut,posDepTxt2Fin),...]),([(paires de blocs déplacés)]), ([(posRempTxt1Debut,posRempTxt1Fin),...],[(posRempTxt2Debut,posRempTxt2Fin),...]) avec pos des Integers 111 """ 112 #PHASE 1 113 logging.info("debut algoFeng.aligne") 114 #split des textes 1 et 2 => liste de (hash, poslistemots, posdebut,posfin+1) => texte[posdebut:posfin] donne le mot et posfin - posdebut la taille 115 # crée des listes de blocs 116 listeMots1 = self.__creerListeMots(self.texte1) 117 listeMots2 = self.__creerListeMots(self.texte2) 118 logging.debug("listeMots crées") 119 logging.log(2,"listeMots1 : %s",listeMots1) 120 logging.log(2,"listeMots2 : %s", listeMots2) 121 #création des dictionaires: pour chaque mot, ses positions et ses occurrences 122 dicoTexte1 = self.__creerDico(listeMots1) 123 dicoTexte2 = self.__creerDico(listeMots2) 124 logging.debug("dicoTexte crées") 125 logging.log(2,"dicoTexte1 : %s",dicoTexte1) 126 logging.log(2,"dicoTexte2 : %s", dicoTexte2) 127 #pour tous les mots de dicoTexte1 occurent une fois dans le texte on crée la liste A 128 129 # ancienne méthode avec des voisins identiques, et occurrences pouvant plusieurs 130 # fois dans le texte 2, tel que dans le papier de Feng 131 # donnait des listes avec moins d'apax car les contextes des hapax devait être identiques également 132 # et non seulement les apax 133 # A,B = self.__creerListesFeng(dicoTexte1,dicoTexte2,listeMots1,listeMots2) 134 135 136 ################################################################################################# 137 #PHASE 1.(a) et 1.(b) 138 #On crée les listes des mots présents une seul fois dans le texte et commun aux deux textes 139 # cad les listes d'apax 140 ################################################################################################# 141 A,B = self.__creerListes(dicoTexte1,dicoTexte2) 142 logging.debug("listes A et B crées") 143 logging.debug("(nbBlocsListe / nbBlocsTexte) : texte1 -> %d / %d , texte2 -> %d / %d",len(A),len(listeMots1),len(B),len(listeMots2)) 144 logging.log(2,"liste A : %s",A) 145 logging.log(2,"liste B : %s",B) 146 if __debug__ : 147 setA = set(x.val for x in A) 148 setB = set(x.val for x in B) 149 assert setA.symmetric_difference(setB) == set([]) #il n'y a pas d'element qui ne soit pas commun aux deux liste 150 151 152 ################################################################################################# 153 #PHASE1.(c) 154 #On aligne les mots présents une seul fois dans le texte et commun aux deux textes 155 #C'est sur le resultat de cet alignement que l'on va déterminer les bornes pour la phase 2 156 ################################################################################################# 157 hmmPhase1 = algoHMM(A, B) 158 159 logging.debug("Debut calcul hmm phase1 (mot ancres)") 160 161 # motAncres = apax alignés conformément au papier de Feng 162 motAncres = hmmPhase1.calculeAlignement() 163 164 logging.debug("Fin calcul hmm phase1") 165 166 blocsAjoutes1 = [] # cad blocs supprimés dans le texte1 167 blocsAjoutes2 = [] # cad blocs insérés dans le texte2 168 blocsAlignes1 = [] # blocs invariants texte 1 169 blocsAlignes2 = [] # blocs invariants texte 2 170 logging.debug("Debut postprocessing Phase1") 171 # filtre et garde uniquement les paires effectivement identiques 172 (blocsAlignes1,blocsAlignes2) = self.__filtrageApareillementsIdentiques(motAncres,listeMots1,listeMots2) 173 logging.log(2,"motAncres : %s",motAncres) 174 175 if __debug__ : 176 logging.log(3,"Liste des mots ancrés (mot texte1 | mot texte2):") 177 for blocs in motAncres : 178 #on a des mots identiques 179 assert listeMots1[blocs[0]].val == listeMots2[blocs[1]].val 180 logging.log(3,"(%s | %s)",self.texte1[listeMots1[blocs[0]].debut:listeMots1[blocs[0]].fin], self.texte2[listeMots2[blocs[1]].debut:listeMots2[blocs[1]].fin]) 181 182 assert len(blocsAlignes1) == len(blocsAlignes2) 183 for i in xrange(len(blocsAlignes1)): 184 #les indices des blocsAlignes sont corrects 185 assert hash(self.texte1[blocsAlignes1[i][0]:blocsAlignes1[i][1]]) == hash(self.texte2[blocsAlignes2[i][0]:blocsAlignes2[i][1]]) 186 logging.debug("Fin postrpoc Phase1") 187 logging.log(2,"blocsAlignes1 : %s",blocsAlignes1) 188 logging.log(2,"blocsAlignes2 : %s",blocsAlignes2) 189 190 191 ################################################################################################## 192 #PHASE 2 193 #On lance le hmm entre les bornes definies par les mots ancrés 194 # et récursivement, la phase 3 et lancée à chaque phase 2 195 ################################################################################################# 196 197 logging.debug("Debut Phase2") 198 ancreGauche1 = -1 199 ancreGauche2 = -1 200 if __debug__ : 201 lAncre = len(listeMots2) 202 for i in xrange(len(motAncres)): 203 ancreDroit1 = motAncres[i][0] 204 ancreDroit2 = motAncres[i][1] 205 #on selectionne les mots compris entre les deux mots ancrés exclus 206 (retAlignes1,retAlignes2),(retAjoutes1,retAjoutes2) = self.__lanceHMMPhase2([(ancreGauche1,ancreGauche2),(ancreDroit1,ancreDroit2)],listeMots1,listeMots2) 207 208 blocsAlignes1.extend(retAlignes1) 209 blocsAlignes2.extend(retAlignes2) 210 blocsAjoutes1.extend(retAjoutes1) 211 blocsAjoutes2.extend(retAjoutes2) 212 213 #traitement blocAlignes 214 ancreGauche1 = ancreDroit1 215 ancreGauche2 = ancreDroit2 216 if __debug__: 217 logging.log(4,"Phase2 : %0.0f %% Done",float((ancreGauche2*lAncre**-1)*100)) 218 219 #dernier traitement pour la partie a droite du dernier mot ancré 220 logging.log(4,"Phase2 : traitement partie droite finale : longueur liste1 : %s, longueur liste2 : %s", len(listeMots1)-1-ancreGauche1,len(listeMots2)-1-ancreGauche2) 221 if ancreGauche1 < len(listeMots1)-1 and ancreGauche2 < len(listeMots2)-1: 222 (retAlignes1,retAlignes2),(retAjoutes1,retAjoutes2) = self.__lanceHMMPhase2([(ancreGauche1,ancreGauche2),(len(listeMots1),len(listeMots2))],listeMots1,listeMots2) 223 #postprocessing repetitions ?? 224 #traitement blocs alignés 225 blocsAlignes1.extend(retAlignes1) 226 blocsAlignes2.extend(retAlignes2) 227 blocsAjoutes1.extend(retAjoutes1) 228 blocsAjoutes2.extend(retAjoutes2) 229 230 #comme on a mis les mots ancrés d'abord, les listes de blocs alignés ne sont pas triées 231 # car on a en premier ajouté les blocs invariants qui étaient les anchors 232 # et ensuite les invariants entre les anchors 233 blocsAlignes1.sort() 234 blocsAlignes2.sort() 235 # blocsAjoutes1.sort() 236 # blocsAjoutes2.sort() 237 238 logging.debug("Fin phase2 et 3") 239 #traitement sur les blocs alignés (regroupement de blocs consecutifs etc..) 240 241 if __debug__ : 242 #les listes de mots ajoutés sont normalement triées en retour de __lanceHMMPhase2 243 bAj1 = blocsAjoutes1[:] 244 bAj1.sort() 245 bAj2 = blocsAjoutes2[:] 246 bAj2.sort() 247 assert blocsAjoutes1 == bAj1 248 assert blocsAjoutes2 == bAj2 249 250 # recherche des blocs déplacés 251 dep1=[] 252 dep2=[] 253 coresDep=[] 254 if self.calculDep: 255 # regroupe les blocs adjacents 256 self.__regrouperBlocs(blocsAjoutes1, self.texte1,True) 257 self.__regrouperBlocs(blocsAjoutes2, self.texte2,True) 258 #recherche des blocs deplacés 259 #(nbocc,len,posListe,posTxt) 260 logging.debug("Debut du calcul des blocs déplacés") 261 # 262 # for k,v in dicoTexte1.iteritems() : 263 # if dicoTexte2.has_key(k) : 264 # depk1 = [] 265 # depk2=[] 266 # for pos1 in v[3]: 267 # if (pos1,pos1+v[1]) in blocsAjoutes1 : 268 # depk1.append((pos1,pos1+v[1])) 269 # 270 # for pos2 in dicoTexte2[k][3]: 271 # if (pos2,pos2+v[1]) in blocsAjoutes2 : 272 # depk2.append((pos2,pos2+v[1])) 273 # for i in xrange(min(len(depk1),len(depk2))): 274 # blocsAjoutes1.pop(blocsAjoutes1.index(depk1[i])) 275 # dep1.append(depk1[i]) 276 # blocsAjoutes2.pop(blocsAjoutes2.index(depk2[i])) 277 # dep2.append(depk2[i]) 278 # hash : nbOcc1,[(posD1,posF2)...],nbOcc2,[(posD2,posF2)..] 279 280 281 # pour calculer les déplacements, on regarde tous les blocs supprimés et insérés 282 # que l'on essaye d'apparier comme déplacements: 283 # on a un dicoDep qui regroupe les positions et occurrences de blocs qui sont 284 # identiques dans texte 1 et 2 285 dicoDep={} 286 # on parcours les suppresisons 287 for posDebut,posFin in blocsAjoutes1 : 288 # on garde celles de taille minimale 289 if posFin-posDebut >= self.lenMinBlocDep: 290 # on les ajoute au dicoDep ou on met à jour les entrées du dico 291 val = hash(self.texte1[posDebut:posFin]) 292 if not dicoDep.has_key(val): 293 dicoDep[val]=(1,[(posDebut,posFin)],0,[]) 294 else : 295 nbOcc1,lPos1,nbOcc2,lPos2 = dicoDep[val] 296 lPos1.append((posDebut,posFin)) 297 lPos1.sort() 298 dicoDep[val] = (nbOcc1+1,lPos1,nbOcc2,lPos2) 299 for posDebut,posFin in blocsAjoutes2 : 300 if posFin-posDebut >= self.lenMinBlocDep: 301 val = hash(self.texte2[posDebut:posFin]) 302 if not dicoDep.has_key(val): 303 dicoDep[val]=(0,[],1,[(posDebut,posFin)]) 304 else : 305 nbOcc1,lPos1,nbOcc2,lPos2 = dicoDep[val] 306 lPos2.append((posDebut,posFin)) 307 lPos2.sort() 308 dicoDep[val] = (nbOcc1,lPos1,nbOcc2+1,lPos2) 309 310 for val,(nbOcc1,lPos1,nbOcc2,lPos2) in dicoDep.iteritems(): 311 # on ne garde que des blocs présents dans les 2 textes 312 for i in xrange(min(nbOcc1,nbOcc2)): 313 dep1.append(lPos1[i]) 314 dep2.append(lPos2[i]) 315 coresDep.append((lPos1[i],lPos2[i])) 316 # paires de blocs déplacés 317 coresDep.sort() 318 # positions des deplacements dans les textes 1 et 2 319 dep1.sort() 320 dep2.sort() 321 #suppression des éléments deplacés des liste des ajoutés 322 for ind in dep1 : 323 blocsAjoutes1.pop(blocsAjoutes1.index(ind)) 324 for ind in dep2 : 325 blocsAjoutes2.pop(blocsAjoutes2.index(ind)) 326 327 logging.log(2,"Blocs déplacés1 : %s",dep1) 328 logging.log(2,"Blocs déplacés2 : %s",dep2) 329 330 assert len(blocsAlignes1)==len(blocsAlignes2) 331 remp1=[] 332 remp2=[] 333 aSupr1=[] 334 aSupr2=[] 335 logging.debug("Debut du regroupage des liste de blocs") 336 # permet de regrouper si on a enlevé des déplacements ou si on ne 337 # recherchait pas les déplacements 338 self.__regrouperBlocs(blocsAjoutes1, self.texte1) 339 self.__regrouperBlocs(blocsAjoutes2, self.texte2) 340 logging.debug("Fin du regroupage des listes de blocs") 341 342 # on parcours les textes 1 et 2 entre les blocs invariants 343 # et on regarde leur ratio de taille pour voir si on peut en faire des remplacements 344 for i in xrange(len(blocsAlignes1)-1): 345 # entre 2 invariants 346 if (blocsAlignes2[i+1][0]-blocsAlignes2[i][1]) != 0: 347 ratio = float(blocsAlignes1[i+1][0]-blocsAlignes1[i][1])/float(blocsAlignes2[i+1][0]-blocsAlignes2[i][1]) 348 if ratio>=float(self.p2**-1) and ratio<=self.p2 and self.texte1[blocsAlignes1[i][1]:blocsAlignes1[i+1][0]]!=" ": 349 remp1.append((blocsAlignes1[i][1],blocsAlignes1[i+1][0])) 350 remp2.append((blocsAlignes2[i][1],blocsAlignes2[i+1][0])) 351 # enlève les blocs remplacés que l'on vient juste de trouver des blocs 352 # insérés et supprimés 353 # PB: on cherche des remplacements dans blocsAlignes sans tenir compte du fait 354 # que certains blocs on put être considérés comme déplacés auparavant car on a 355 # recherché les déplacements uniquement dans blocsAjoutés (et pas dans blocsAlignés) 356 for bloc in remp1: 357 try: 358 blocsAjoutes1.pop(blocsAjoutes1.index(bloc)) 359 except: 360 #bloc déplacé on ne fait rien 361 # a tester: le bloc devrait être dans les déplacés et ou pourrait le 362 # supprimer de remp1 363 pass 364 365 for bloc in remp2: 366 try: 367 blocsAjoutes2.pop(blocsAjoutes2.index(bloc)) 368 except: 369 #c'est un bloc déplacé 370 pass 371 372 remp1.sort() 373 remp2.sort() 374 375 #self.__regrouperBlocs(blocsAlignes1,self.texte1) 376 #self.__regrouperBlocs(blocsAlignes2,self.texte2) 377 self.__regrouperBlocs(remp1, self.texte1,False) 378 self.__regrouperBlocs(remp2, self.texte2,False) 379 380 381 382 if __debug__ : 383 #affichage du texte aligné 384 385 res = "" 386 for deb,fin in blocsAlignes1 : 387 res += self.texte1[deb:fin] +" " 388 res+="\n============\n" 389 for deb,fin in blocsAlignes2 : 390 res += self.texte2[deb:fin] + " " 391 logging.log(4,"Texte aligné :\n%s",res) 392 393 logging.info("fin algoFeng.aligne") 394 395 # self.prof.close() 396 # stats = hotshot.stats.load("./statFile") 397 # stats.sort_stats('time','calls') 398 # stats.print_stats(50) 399 return (blocsAlignes1,blocsAlignes2),(blocsAjoutes1,blocsAjoutes2),(dep1,dep2),(coresDep),(remp1,remp2)

400 401 402 403 404 ############################### 405 #Definition des methodes privées 406 ############################## 407

408 - def __lanceHMMPhase2(self,bornesAncres,listeMots1,listeMots2):

409 """Lance la phase 2 de l'algo. 410 411 Ici on lance la comparaison HMM au niveau des MOTS 412 413 @param listeMots1: la liste de blocs pour le texte1 414 @param listeMots2: la liste de blocs pour le texte2 415 @param bornesAncres: les bornes pour l'alignement, sur lequel on va couper les listeMots 416 @type liste1,liste2,listeMots1,listeMots2 : liste de blocs ou les champs val, posDebut, posFin et index sont renseignés 417 @type bornesAncres: [(borneGaucheListeMots1,borneGaucheListeMots2),(borneDroiteListeMots1,borneDroiteListeMots2)] 418 @return: liste des blocs alignes, liste des blocs ajoutes 419 @type: ([(DebutBlocTxt1,FinBlocTxt1)...],[(DebutBlocTxt2,FinBlocTxt2)...]),([(DebutBlocTxt1,FinBlocTxt1)...],[(DebutBlocTxt2,FinBlocTxt2)...]) 420 """ 421 #partie du texte sur laquelle on cherche a aligner 422 liste1 = listeMots1[bornesAncres[0][0]+1:bornesAncres[1][0]] 423 liste2 = listeMots2[bornesAncres[0][1]+1:bornesAncres[1][1]] 424 425 logging.log(3,"Fonction __lanceHMMPhase2 invoquée bornes listeMots1 :[%s;%s] bornes listeMots2 :[%s;%s]",bornesAncres[0][0],bornesAncres[1][0],bornesAncres[0][1],bornesAncres[1][1]) 426 hmmPhase2 = algoHMM(liste1,liste2) 427 # self.prof.runctx("motAlignes = hmmPhase2.calculeAlignement()",globals(),locals()) 428 motAlignes = hmmPhase2.calculeAlignement() 429 430 #postprocessing apareillements 431 blocsAjoutes1 = [] 432 blocsAjoutes2 = [] 433 blocAlignes1 = [] 434 blocAlignes2 = [] 435 (blocAlignes1,blocAlignes2) = self.__filtrageApareillementsIdentiques(motAlignes,listeMots1,listeMots2) 436 437 438 if __debug__ : 439 logging.log(3,"Mots Alignés phase2 : (texte1 | texte2)") 440 441 #les mots alignés sont bien identiques 442 for blocs in motAlignes : 443 assert listeMots1[blocs[0]].val == listeMots2[blocs[1]].val 444 logging.log(3,"(%s | %s)",self.texte1[listeMots1[blocs[0]].debut:listeMots1[blocs[0]].fin], self.texte2[listeMots2[blocs[1]].debut:listeMots2[blocs[1]].fin]) 445 446 #on a autant de blocs alignés pour les 2 textes 447 assert len(blocAlignes1) == len(blocAlignes2) 448 for i in xrange(len(blocAlignes1)): 449 #les indices des blocsAlignes sont corrects 450 assert hash(self.texte1[blocAlignes1[i][0]:blocAlignes1[i][1]]) == hash(self.texte2[blocAlignes2[i][0]:blocAlignes2[i][1]]) 451 452 453 logging.log(2,"blocsAlignés1 : %s",blocAlignes1) 454 logging.log(2,"blocsAlignés2 : %s",blocAlignes2) 455 456 ########################################################################################## 457 #PHASE3 458 #Alignement au niveau des caracteres entre chaque mot aligné dans la phase 2 459 ########################################################################################## 460 logging.log(3,"Debut phase 3") 461 (retAlignes1,retAlignes2),(retAjoutes1,retAjoutes2) = self.__alignePhase3(motAlignes, bornesAncres,listeMots1,listeMots2) 462 463 464 blocAlignes1.extend(retAlignes1) 465 blocAlignes2.extend(retAlignes2) 466 blocsAjoutes1.extend(retAjoutes1) 467 blocsAjoutes2.extend(retAjoutes2) 468 #bien que blocAlignes et retAlignes soit triés, leur concaténation ne l'est pas necessairement puisque la phase 3 aligne entre les mots de la phase2 469 blocAlignes1.sort() 470 blocAlignes2.sort() 471 blocsAjoutes1.sort() 472 blocsAjoutes2.sort() 473 logging.log(3,"Fin phase3") 474 logging.log(3,"Fin __lanceHMMPhase2") 475 #print "fin __lanceHMMPhase2 : ",blocAlignes1,blocAlignes2 476 return (blocAlignes1,blocAlignes2),(blocsAjoutes1,blocsAjoutes2)

477 478

479 - def __alignePhase3(self,motsAlignes, bornesAncres,listeMots1, listeMots2):

480 """Lance la Phase 3 de l'algo 481 482 Alignement au niveau des caracteres 483 @param motsAlignes: la liste des mots alignés en phase 2 484 @param bornesAncres: les bornes entre lesquelles on travaille 485 @param listeMots1: la liste des blocs du texte 1 486 @param listeMots2: la liste des blocs du texte 2 487 @type motsAlignes: [(posListeMots1,posListeMots2)...] 488 @type bornesAncres: [(borneGaucheListeMots1,borneGaucheListeMots2),(borneDroiteListeMots1,borneDroiteListeMots2)] 489 @type liste1,liste2,listeMots1,listeMots2 : liste de blocs ou les champs val, posDebut, posFin et index sont renseignés 490 @return: liste de blocs alignés, liste des blocs ajoutes 491 @rtype: ([(DebutBlocTxt1,FinBlocTxt1)...],[(DebutBlocTxt2,FinBlocTxt2)...]),([(DebutBlocTxt1,FinBlocTxt1)...],[(DebutBlocTxt2,FinBlocTxt2)...]) 492 """ 493 #print "Debut __alignePhase3 : ",bornesAncres,motsAlignes 494 #concaténation des liste de mots alignés et mots ancrés, trié par ordre de position dans les textes 495 496 497 logging.log(3,"Fonction __alignePhase3 invoquée, bornes liste1 :[%s %s] liste2:[%s %s]",bornesAncres[0][0],bornesAncres[1][0],bornesAncres[0][1],bornesAncres[1][1]) 498 borneGauche1 = bornesAncres[0][0] 499 borneGauche2 = bornesAncres[0][1] 500 blocAlignes1 = [] 501 blocAlignes2 = [] 502 blocAjoutes1 = [] 503 blocAjoutes2 = [] 504 505 for i in xrange(len(motsAlignes)): 506 borneDroite1 = motsAlignes[i][0] 507 borneDroite2 = motsAlignes[i][1] 508 (retAlignes1,retAlignes2),(retAjoutes1,retAjoutes2) = self.__lanceHMMPhase3(listeMots1[borneGauche1+1:borneDroite1],listeMots2[borneGauche2+1:borneDroite2]) 509 510 if __debug__ : 511 #on verifie que les car alignés soient bien situés dans les bornes 512 for pos in retAlignes1+retAjoutes1: 513 for subPos in pos : 514 assert listeMots1[borneGauche1+1].debut <= subPos #le bloc commence ou termine apres la borne de gauche 515 assert listeMots1[borneDroite1].fin >= subPos #le bloc commence ou termine avant la borne droite 516 for pos in retAlignes2+retAjoutes2: 517 for subPos in pos : 518 assert listeMots2[borneGauche2+1].debut <= subPos #le bloc commence ou termine apres la borne de gauche 519 assert listeMots2[borneDroite2].fin >= subPos #le bloc commence ou termine avant la borne droite 520 521 blocAlignes1.extend(retAlignes1) 522 blocAlignes2.extend(retAlignes2) 523 blocAjoutes1.extend(retAjoutes1) 524 blocAjoutes2.extend(retAjoutes2) 525 if __debug__ : 526 #les liste sont normalement triées en retour de __lanceHMMPhase3 527 bAl1 = blocAlignes1[:] 528 bAl1.sort() 529 bAl2 = blocAlignes2[:] 530 bAl2.sort() 531 bAj1 = blocAjoutes1[:] 532 bAj1.sort() 533 bAj2 = blocAjoutes2[:] 534 bAj2.sort() 535 assert blocAlignes1 == bAl1 536 assert blocAlignes2 == bAl2 537 assert blocAjoutes1 == bAj1 538 assert blocAjoutes2 == bAj2 539 540 borneGauche1 = borneDroite1 541 borneGauche2 = borneDroite2 542 543 #traitement pour la partie a droite du dernier mot aligne 544 if borneGauche1 < len(listeMots1)-1 and borneGauche2 < len(listeMots2)-1: 545 (retAlignes1,retAlignes2),(retAjoutes1,retAjoutes2) = self.__lanceHMMPhase3(listeMots1[borneGauche1+1:bornesAncres[1][0]], listeMots2[borneGauche2+1:bornesAncres[1][1]]) 546 #blocAlignes = ... 547 if __debug__ : 548 #on verifie que les car alignés soient bien situés dans les bornes 549 for pos in retAlignes1+retAjoutes1: 550 for subPos in pos : 551 assert listeMots1[borneGauche1+1].debut <= subPos #le bloc commence ou termine apres la borne de gauche 552 assert listeMots1[bornesAncres[1][0]-1].fin >= subPos #le bloc commence ou termine avant la borne droite 553 for pos in retAlignes2+retAjoutes2: 554 for subPos in pos : 555 assert listeMots2[borneGauche2+1].debut <= subPos #le bloc commence ou termine apres la borne de gauche 556 assert listeMots2[bornesAncres[1][1]-1].fin >= subPos #le bloc commence ou termine avant la borne droite 557 blocAlignes1.extend(retAlignes1) 558 blocAlignes2.extend(retAlignes2) 559 blocAjoutes1.extend(retAjoutes1) 560 blocAjoutes2.extend(retAjoutes2) 561 if __debug__ : 562 #les liste sont normalement triées en retour de __lanceHMMPhase3 563 bAl1 = blocAlignes1[:] 564 bAl1.sort() 565 bAl2 = blocAlignes2[:] 566 bAl2.sort() 567 bAj1 = blocAjoutes1[:] 568 bAj1.sort() 569 bAj2 = blocAjoutes2[:] 570 bAj2.sort() 571 assert blocAlignes1 == bAl1 572 assert blocAlignes2 == bAl2 573 assert blocAjoutes1 == bAj1 574 assert blocAjoutes2 == bAj2 575 576 logging.log(3,"Fin __alignePhase3") 577 #print "fin __alignePhase3 : ",blocAlignes1,blocAlignes2 578 return (blocAlignes1,blocAlignes2),(blocAjoutes1,blocAjoutes2)

579 580 581

582 - def __lanceHMMPhase3(self,liste1,liste2):

583 """Crée les listes de caracteres et effectue la comparaison HMM sur ces 2 listes 584 585 recherche les blocs ajoutes / supprimes 586 @param liste1: les elements du texte1 que l'on souhaite aligner 587 @param liste2: les elements du texte2 que l'on souhaite aligner 588 @type liste1,liste2: liste de blocs ou les champs val, posDebut, posFin et index sont renseignés 589 @return: liste de blocs alignés, liste des blocs ajoutes 590 @rtype: ([(DebutBlocTxt1,FinBlocTxt1)...],[(DebutBlocTxt2,FinBlocTxt2)...]),([(DebutBlocTxt1,FinBlocTxt1)...],[(DebutBlocTxt2,FinBlocTxt2)...]) 591 """ 592 #on créer une liste de blocs pour chaque texte ou un bloc est un caractere 593 594 logging.log(3,"Fonction __lanceHMMPhase3 invoquée") 595 listeCar1 = [] 596 listeCar2 = [] 597 598 # print "debut __lanceHMMPhase3:\n" 599 logging.log(3,"Création des listes de caracteres") 600 index = 0 601 for bloc in liste1 : 602 for i in xrange(bloc.fin-bloc.debut) : 603 listeCar1.append(bloc(self.texte1[i+bloc.debut],bloc.debut+i,bloc.debut+i+1,index)) 604 index += 1 605 606 607 index = 0 608 for bloc in liste2: 609 for i in xrange(bloc.fin-bloc.debut) : 610 listeCar2.append(bloc(self.texte2[i+bloc.debut],bloc.debut+i,bloc.debut+i+1,index)) 611 index += 1 612 logging.log(2,"listeCar1 : %s",listeCar1) 613 logging.log(2,"listeCar2 : %s",listeCar2) 614 615 hmmPhase3 = algoHMM(listeCar1,listeCar2) 616 # self.prof.runctx("carAlignes = hmmPhase3.calculeAlignement()",globals(),locals()) 617 carAlignes = hmmPhase3.calculeAlignement() 618 (blocAlignes1,blocAlignes2) = self.__filtrageApareillementsIdentiques(carAlignes, listeCar1, listeCar2) 619 if __debug__ : 620 logging.log(2,"Resultat HMM (apres postprocessing): %s",carAlignes) 621 logging.log(2,"Caracteres alignés : (texte1 | texte2)") 622 for bloc in carAlignes : 623 assert listeCar1[bloc[0]].val == listeCar2[bloc[1]].val 624 logging.log(2,"(%s | %s)",listeCar1[bloc[0]].val, listeCar2[bloc[1]].val) 625 assert len(blocAlignes1) == len(blocAlignes2) 626 for i in xrange(len(blocAlignes1)): 627 #les indices des blocsAlignes sont corrects 628 assert hash(self.texte1[blocAlignes1[i][0]:blocAlignes1[i][1]]) == hash(self.texte2[blocAlignes2[i][0]:blocAlignes2[i][1]]) 629 630 i = 0 631 632 #calcul des blocs ajoutes / supprimes : bloc non aligne de txt1 => supr, txt2 => ajout 633 logging.log(3,"Debut du calcul des blocs supprimés / ajoutés") 634 635 for bloc1,bloc2 in carAlignes: 636 #on supprime les blocs alignés des listes de blocs 637 listeCar1.pop(bloc1-i) 638 listeCar2.pop(bloc2-i) 639 i+=1 640 blocAjoutes1 = [] 641 blocAjoutes2 =[] 642 for bloc in listeCar1: 643 blocAjoutes1.append((bloc.debut,bloc.fin)) 644 for bloc in listeCar2: 645 blocAjoutes2.append((bloc.debut,bloc.fin)) 646 logging.log(2,"BlocAjoutes1 : %s",blocAjoutes1) 647 logging.log(2,"BlocAjoutes2 : %s", blocAjoutes2) 648 logging.log(3,"fin __lanceHMMPhase3") 649 return (blocAlignes1,blocAlignes2),(blocAjoutes1,blocAjoutes2)

650 651

652 - def __creerListeMots(self,texte):

653 """effectue la séparation des mots du texte 654 655 @param texte: le texte que l'on souhaite separer 656 @type texte: String 657 @return: liste de bloc(hash,posdebut,posfin+1,posListeMots) 658 """ 659 if self.ignorerSeparateurs : 660 #si on ignore les separateurs, on va tous les remplacer par le caractere " " 661 #separateurs : !"#$%&'()*+, -./:;<=>?@[\]^_`{|}~\n\r\t 662 #separateurs = string.punctuation+"\n\r\t " 663 separateurs = """!\r,\n:\t;-?"'`’()""" 664 665 sepTable = string.maketrans(separateurs," "*len(separateurs)) 666 texte = texte.translate(sepTable) 667 668 texteSplit = texte.split(" ") 669 pos = -1 670 posListe = 0 671 listeMots = [] 672 for mot in texteSplit: 673 if len(mot) == 0 : 674 #on a splité entre 2 separateurs 675 pos+=1 676 else: 677 pos+=1 678 listeMots.append( bloc(hash(mot), pos, pos+len(mot), posListe) ) #(hash,posDebut,posFin+1,index) 679 pos+=len(mot) 680 posListe+=1 681 682 return listeMots

683

684 - def __creerDico(self,liste):

685 """Crée pour chaque mot un dictionnaire comportant son nombre d'occurences 686 et ses positions 687 688 @param liste: la liste a traiter 689 @type liste: liste de bloc(hash,posdebut,posfin+1,posListeMots) 690 @return: le dictionnaire des mots présentds dans la liste 691 @type dico de (hash : (nbOccurences,len,[posOccListe,...],[posOccTxt...]) 692 """ 693 #index = 0 694 dico = {} 695 for mot in liste : 696 #si le hash n'est pas déja indexé dans le dictionnaire 697 hashMot=mot.val 698 if not(dico.has_key(hashMot)): 699 #ajout du mot au dictionnaire 700 dico[hashMot] = (1,mot.fin-mot.debut,[mot.index],[mot.debut]) #(nbocc,len,posListe,posTxt) 701 else: 702 #modification des valeurs associées au mot dans le dictionnaire 703 (nbOcc,lenMot,posListe,posTexte) = dico[hashMot] 704 posListe.append(mot.index) 705 posTexte.append(mot.debut) 706 707 dico[hashMot] = (nbOcc+1,lenMot,posListe,posTexte) 708 #index+=1 709 710 return dico

711 712

713 - def __creerListes(self,dicoTexte1,dicoTexte2):

714 """Cree les listes de la phase 1.(a) et 1.(b) de l'algo 715 716 liste des apax : termes uniques dans chaque texte et communs aux 2 textes 717 718 @param dicoTexte1,dicoTexte2 : les dictionnaires pour les deux textes 719 @type dicoTexte1,dicoTexte2: dico de (hash : (nbOccurences,len,[posOccListe,...],[posOccTxt...]) 720 @return les listes A,B des apax dans les textes 1 et 2 721 @type: listes de bloc(val,index) 722 """ 723 724 #PHASE 1.(a) 725 726 A = [] # liste apax texte 1 727 for key,v in dicoTexte1.iteritems(): 728 if v[0]==1 : 729 A.append(bloc(key , index=v[2][0])) #sa position dans listeMots1 730 731 #tri de la liste a dans l'ordre d'apparition des mots dans le texte1 732 A.sort(cmp=lambda x,y: cmp(x.index,y.index)) 733 #PHASE 1.(b) 734 #filtrer la liste 735 736 #print self.texte1,"\n",self.texte2,"\n",A,"\n=========================" 737 738 #création de la liste B : liste des mots correspondants a la liste A dans le texte2, et filtrage de la liste 1 de telle sorte que chaque éléement de A aparaisse dans B 739 B=[] # liste apax texte 2 740 aSupprimer=[] 741 # cpt = 1 742 for mot in A: 743 if not dicoTexte2.has_key(mot.val): 744 aSupprimer.append(mot) 745 elif dicoTexte2[mot.val][0]>1 : 746 aSupprimer.append(mot) 747 else : 748 listeIndex = dicoTexte2[mot.val][2] 749 for index in listeIndex: 750 B.append(bloc(mot.val,index=index)) 751 for mot in aSupprimer : 752 A.pop(A.index(mot)) 753 754 #tri de la liste B dans l'ordre d'apparition des mots dans le texte2 755 B.sort(cmp=lambda x,y: cmp(x.index,y.index)) 756 757 #TODO : créer la liste B 758 return A,B

759 760 761 762

763 - def __filtrageApareillementsIdentiques(self,aligneHMM,listeMots1,listeMots2):

764 """determine l'alignement une fois que le HMM a renvoyé les blocs considérés comme alignés 765 766 /!\ EFFECTUE DES EFFETS DE BORD SUR aligneHMM /!\ 767 renvoie la liste des blocs alignés, et le cas échéant la liste des blocs insérés sous forme de liste de (posDeb,posFin) 768 769 @param aligneHMM: le resultat de l'alignement HMM */!\_MODIFIE EN RETOUR PAR CETTE METHODE_/!\* 770 @type aligneHMM: [(posBlocAligné1,posBlocAligné2)...] 771 @param listeMots1,listeMots2: les listes de mots pour les textes 772 @type listeMots1,listeMots2: liste de blocs ou les champs val, posDebut, posFin et index sont renseignés 773 """ 774 aSupprimer = [] 775 blocsAlignes1 = [] 776 blocsAlignes2 = [] 777 aligneHMM.sort() 778 for pos1,pos2 in aligneHMM : 779 780 if listeMots1[pos1].val != listeMots2[pos2].val : 781 #on ajoute le couple a la liste des couples a supprimer car les mots ne correspondent pas 782 aSupprimer.append((pos1,pos2)) 783 for pos in aSupprimer : 784 aligneHMM.pop(aligneHMM.index(pos)) 785 786 #on a filtré tous les éléments dont le hash / valeur ne correspondent pas 787 #si on a plusieurs correspondances pour un bloc, on prend le premier 788 # cad qu'un état à émis plusieurs mots dans le texte 2 789 aSupprimer = [] 790 posActuelle=-1 791 for pos1,pos2 in aligneHMM : 792 if pos1 != posActuelle : 793 posActuelle = pos1 794 blocsAlignes1.append((listeMots1[pos1].debut,listeMots1[pos1].fin)) #(blocDebut,blocFin) 795 blocsAlignes2.append((listeMots2[pos2].debut,listeMots2[pos2].fin)) #(blocDebut,blocFin) 796 else : 797 aSupprimer.append((pos1,pos2)) 798 799 for pos in aSupprimer : 800 aligneHMM.pop(aligneHMM.index(pos)) 801 return (blocsAlignes1,blocsAlignes2)

802 803 804

805 - def __regrouperBlocs(self,listeBlocs,txt,ignorerPonctuation=False):

806 """regroupe les blocs adjacents d'une liste de blocs 807 808 /!\ EFFECTUE UN EFFET DE BORD SUR listeBlocs /!\ 809 810 811 @param listeBlocs: la liste des blocs 812 @type listeBlocs: [(posDebut,posFin+1)] 813 @param txt: le texte correspondant 814 @type txt: String 815 """ 816 817 separateurs = " " 818 if self.ignorerSeparateurs : 819 #si on ignore les separateurs, on va tous les remplacer par le caractere " " 820 #separateurs : !"#$%&'()*+, -./:;<=>?@[\]^_`{|}~\n\r\t 821 separateurs = """!\r,\n:\t;-?"'`’()""" 822 i=0 823 while i != len(listeBlocs)-1: 824 if listeBlocs[i][1] == listeBlocs[i+1][0] : 825 listeBlocs[i] = (listeBlocs[i][0],listeBlocs[i+1][1]) 826 del listeBlocs[i+1] 827 # à priori à enlever, mais ne change pas les résultats pour les XP 828 # en ignorer ponctuation 829 elif (not ignorerPonctuation) and txt[listeBlocs[i][1]] in separateurs: 830 listeBlocs[i] = (listeBlocs[i][0],listeBlocs[i][1]+1) 831 else : 832 i += 1

833 834 835 ####################################################################################################### 836 #Depracated 837 #######################################################################################################

838 - def __creerListesFeng(self,dicoTexte1,dicoTexte2,listeMots1,listeMots2):

839 """ 840 841 @deprecated: nous n'utilisons pas les methodes definies dans le papier de Feng & Manmatha, qui s'averent tres contraignantes sur les HMM 842 @see: __creerListes 843 """ 844 845 #PHASE 1.(a) 846 847 A = [] 848 for key,v in dicoTexte1.iteritems(): 849 if v[0]==1 : 850 A.append(bloc(key , index=v[2][0])) #sa position dans listeMots1 851 852 #tri de la liste a dans l'ordre d'apparition des mots dans le texte1 853 A.sort(cmp=lambda x,y: cmp(x.index,y.index)) 854 #PHASE 1.(b) 855 #filtrer la liste 856 857 #print self.texte1,"\n",self.texte2,"\n",A,"\n=========================" 858 859 self.__filtrerListe(A,dicoTexte1,dicoTexte2,listeMots1,listeMots2) 860 861 #print A,"\n==================" 862 863 #création de la liste B : liste des mots correspondants a la liste A dans le texte2 864 B=[] 865 # cpt = 1 866 for mot in A: 867 for index in dicoTexte2[mot.val][2]: 868 B.append(bloc(mot.val,index=index)) 869 870 #tri de la liste B dans l'ordre d'apparition des mots dans le texte2 871 B.sort(cmp=lambda x,y: cmp(x.index,y.index)) 872 873 #TODO : créer la liste B 874 return A,B

875

876 - def __filtrerListe(self,liste,dicoTexte1,dicoTexte2,listeMots1,listeMots2):

877 """ 878 """ 879 aSupprimmer = [] 880 for element in liste: 881 #suppression des éléments n'aparaissant pas dans le texte2 882 mot = element.val 883 if not dicoTexte2.has_key(mot) : 884 aSupprimmer.append(element) 885 else: 886 #suppresion des mots dont les voisins immédiats ne sont pas identiques 887 pos1 = dicoTexte1[mot][2][0] #position du mot dans listeMots1 888 suivant1 = None 889 precedant1 = None 890 if pos1 > 0 : 891 precedant1 = listeMots1[pos1-1].val #mot précédent le mot actuel 892 if pos1 < len(listeMots1)-1: 893 suivant1 = listeMots1[pos1+1].val #mot suivant le mot actuel 894 895 motTrouveDansTexte2 = False 896 for pos2 in dicoTexte2[mot][2]: 897 #pos2 position du mot dans listeMots2 898 identique = True 899 if pos2 > 0 and precedant1 != None : 900 precedant2 = listeMots2[pos2-1].val #mot précédent le mot correspondant dans le texte2 901 if precedant1 != precedant2 : 902 identique = False 903 if pos2 < len(listeMots1)-1 and suivant1 != None: 904 suivant2 = listeMots2[pos2+1].val #mot suivant le mot correspondant dans le texte2 905 if suivant1 != suivant2: 906 identique = False 907 if identique : 908 motTrouveDansTexte2 = True 909 if not motTrouveDansTexte2: 910 #on n'a pas trouvé de mot ayant des voisins immédiats identiques dans le texte2 911 aSupprimmer.append(element) 912 for elem in aSupprimmer : 913 liste.pop(liste.index(elem))

914

915 - def __filtrageApareillementsIdentiquesOld(self,aligneHMM,listeMots1,listeMots2):

916 """determine l'alignement une fois que le HMM a renvoyé les blocs considérés comme alignés 917 /!\ EFFECTUE DES EFFETS DE BORD SUR aligneHMM /!\ 918 renvoie la liste des blocs alignés, et le cas échéant la liste des blocs insérés sous forme de liste de (posDeb,posFin) 919 @deprecated: cette fonction est moche (mais vraiment tres moche en fait) :( 920 @see: __filtrageApareillementsIdentiques 921 """ 922 #print "debut __filtrageApareillementsIdentiques" 923 aligne = {} 924 blocsAlignes1 = [] 925 blocsAlignes2 = [] 926 blocsAjoutes1 = [] 927 blocsAjoutes2 = [] 928 929 aSupprimer = [] 930 931 for pos in aligneHMM : 932 pos1 = pos[0] 933 pos2 = pos[1] 934 935 hashMot = listeMots1[pos1].val 936 if hashMot == listeMots2[pos2].val : 937 #le mot est identique 938 if not aligne.has_key(hashMot): 939 #on n'a pas encore mis ce mot ds le dico des mots alignés 940 aligne[hashMot] = (1,[(pos1,pos2)]) 941 else : 942 #on a deja mis ce mot ds le dico des mots alignés 943 (cpt,listePos) = aligne[hashMot] 944 cpt += 1 945 listePos.append((pos1,pos2)) 946 aligne[hashMot] = (cpt,listePos) 947 else : 948 #on ajoute le couple a la liste des couples a supprimer car les mots ne correspondent pas 949 aSupprimer.append(pos) 950 # for pos in aSupprimer : 951 # #le mot n'est pas identique, on l'enleve de la liste des mots alignés par les HMM 952 # #/!\ LA LISTE EST MODIFIEE EN RETOUR 953 # del aligneHMM[aligneHMM.index(pos)] 954 955 #traitement du dico des mots alignes 956 for mot, (cpt,listePos) in aligne.iteritems(): 957 if cpt == 1 : 958 #il n'y a qu'un seul alignement possible 959 blocsAlignes1.append((listeMots1[listePos[0][0]].debut,listeMots1[listePos[0][0]].fin)) #(blocDebut,blocFin) 960 blocsAlignes2.append((listeMots2[listePos[0][1]].debut,listeMots2[listePos[0][1]].fin)) #(blocDebut,blocFin) 961 #sort sur le premier element des tuples par defaut 962 blocsAlignes1.sort() 963 blocsAlignes2.sort() 964 #A FAIRE §§§§§§ 965 966 else : 967 # print mot, (cpt,listePos) 968 969 #plus d'un alignement possible 970 #plusieurs cas : [a,b] [c,d] .... les couples n'ont aucun élément commun : ils sont tous ok 971 #[a,b][a,c][c,d].... les couples ont des éléments communs : on doit choisir les meilleurs couples, les mots restant sont des insertions / suppresions 972 # => on va créer un dictionnaire par texte afin de determiner l'unicité des index 973 #on ne peut pas utiliser les dictionnaires principaux car il est posible que l'on ne travaille que sur une sous-liste de listeMots 974 dicoPos1={} 975 dicoPos2={} 976 977 for pos in listePos : 978 pos1=pos[0] 979 pos2=pos[1] 980 if not dicoPos1.has_key(pos1): 981 dicoPos1[pos1] = (1,[pos2]) #nbOcc,liste des positions des termes alignés dans le texte2 982 else : 983 #plus d'une occurence de cette position 984 nbOcc,listeAlignement = dicoPos1[pos1] 985 nbOcc += 1 986 listeAlignement.append(pos2) 987 dicoPos1[pos1] = (nbOcc,listeAlignement) 988 #de meme pour pos2 989 if not dicoPos2.has_key(pos2): 990 dicoPos2[pos2] = (1,[pos1]) #nbOcc,liste des positions des termes alignés dans le texte1 991 else : 992 #plus d'une occurence de cette position 993 nbOcc,listeAlignement = dicoPos2[pos2] 994 nbOcc += 1 995 listeAlignement.append(pos1) 996 dicoPos2[pos2] = (nbOcc,listeAlignement) 997 # print "dico1: ",dicoPos1 998 # print "dico2: ",dicoPos2 999 1000 for pos1,(nbOcc1,listeLies1) in dicoPos1.iteritems(): 1001 if nbOcc1 == 1 and len(listeLies1) == 1: 1002 #une seule occurence de ce terme 1003 #on a un seul terme aligné avec celui ci dans le texte2 1004 blocsAlignes1.append((listeMots1[pos1].debut,listeMots1[pos1].fin)) 1005 blocsAlignes2.append((listeMots2[listeLies1[0]].debut,listeMots2[listeLies1[0]].fin)) 1006 else : 1007 #plus d'un terme possible 1008 listeLies1.sort() 1009 # print ">",listeLies1 1010 bons=[] #liste des positions n'etant liées qu'a pos1 1011 autres=[] #liste des positions auant plus d'un alignement possible 1012 for pos2 in listeLies1: 1013 if dicoPos2[pos2][0]==1 : 1014 bons.append(pos2) 1015 else : 1016 autres.append(pos2) 1017 # print "bons :",bons 1018 # print "autres; ",autres 1019 1020 if len(bons)>0: 1021 # 1022 # /§\ ON PEUT MODIFIER ICI 1023 # 1024 #on prend le premier element 1025 blocsAlignes1.append((listeMots1[pos1].debut,listeMots1[pos1].fin)) 1026 blocsAlignes2.append((listeMots2[bons[0]].debut,listeMots2[bons[0]].fin)) 1027 bons.pop(0) 1028 for pos2 in bons : 1029 aSupprimer.append((pos1,pos2)) 1030 # else : 1031 # #il faut trouver le meilleur des autres alignements 1032 # on ne peut normalement pas rentrer dans ce bloc 1033 for pos in aSupprimer : 1034 #le mot n'est pas identique, on l'enleve de la liste des mots alignés par les HMM 1035 #/!\ LA LISTE EST MODIFIEE EN RETOUR 1036 del aligneHMM[aligneHMM.index(pos)] 1037 1038 #tri des listes 1039 blocsAlignes1.sort() 1040 blocsAlignes2.sort() 1041 return (blocsAlignes1,blocsAlignes2),(blocsAjoutes1,blocsAjoutes2)

Source Code for Module medite.MediteAppli.feng