# -*- coding: iso-8859-1 -*- # Copyright 20003 - 2008: Julien Bourdaillet (julien.bourdaillet@lip6.fr), Jean-Gabriel Ganascia (jean-gabriel.ganascia@lip6.fr) # This file is part of MEDITE. # # MEDITE is free software; you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation; either version 2 of the License, or # (at your option) any later version. # # MEDITE is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with Foobar; if not, write to the Free Software # Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA import logging, heapq, bisect, sys, random import numpy.oldnumeric as Numeric import utile class Recouvrement(object): """ Classe gérant et résolvant les recouvrements """ def __init__(self,texte,blocs_texte,lg_texte1, min_size=1): self.texte = texte self.blocs_texte = blocs_texte self.lg_texte1 = lg_texte1 self.lg_texte2 = len(self.texte)-self.lg_texte1 self.min_size = min_size self.tool = utile.Utile() def couverture(self): """ Renvoie sous forme d'une liste croissante d'intervalles tous les segments couverts dans "blocs_texte"; cette fonction permet ensuite determiner les recouvrements """ #logging.debug("debut couverture") L = [] for chaine,liste_pos in self.blocs_texte.iteritems(): ln = len(chaine) for occ in liste_pos: L = self.tool.addition_intervalle(L, [occ, occ + ln]) #logging.debug("fin couverture") return L def recouvrements__(self, couv): """ Cette fonction prends en entree la couverture, c'est-a-dire la liste des intervalles couverts par les chaines de "blocs_texte" Elle renvoie les zones de recouvrement sous forme quadruplets: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] """ logging.debug("debut recouvrements") L = [] while len(couv)>1: if couv[0][-1] > couv[1][0]: L = self.tool.addition_intervalle(L, [couv[1][0], couv[0][-1], couv[0], couv[1]]) couv = couv[1:] logging.debug("fin recouvrements") return L def recouvrements(self, couv): """ Cette fonction prend en entree la couverture, c'est-a-dire la liste des intervalles couverts par les chaines de "blocs_texte" Elle renvoie les zones de recouvrement sous forme quadruplets: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] """ #logging.debug("debut recouvrements") L = [] i = 0 while i < len(couv)-1: if couv[i][-1] > couv[i+1][0]: L = self.tool.addition_intervalle(L, [couv[i+1][0], couv[i][-1], couv[i], couv[i+1]]) i += 1 #logging.debug("fin recouvrements") return L def resoudre_recouvrement_(self, I): """ part d'un intervalle qui corresponds a un recouvrement et trouve une cesure judicieuse (par exemple un blanc) On coupera sur cette cesure I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] """ #sys.stderr.write(str(I)) #logging.debug(self.texte[I[2][0]:I[2][1]]+' / ' +self.texte[I[3][0]:I[3][1]] + # ' / ' + self.texte[I[0]:I[1]]) if (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in [' ', '.', '-', ',', '!', '?', ':', ';']): return I[0] if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or self.texte[I[1]] in [' ', '.', '-', ',', '!', '?', ':', ';']): return I[1] #taillech1=I[2][1]-I[2][0] #taillech2=I[3][1]-I[3][0] #if taillech1<=taillech2: L = range(I[0], I[1] + 1) #else: L = range(I[1], I[0]-1, -1) L = range(I[0], I[1]+1) for x in L: if self.texte[x] == ' ': return x for x in L: if self.texte[x] in ['.', '-', ',', '!', '?', ':', ';']: return x return L[0] def resoudre_recouvrement____(self, I): """ part d'un intervalle qui corresponds a un recouvrement et trouve une cesure judicieuse (par exemple un blanc) On coupera sur cette cesure I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] """ #sys.stderr.write(str(I)) res = I[0] if (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in [' ', '.', '-', ',', '!', '?', ':', ';']): res = I[0] elif (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or self.texte[I[1]] in [' ', '.', '-', ',', '!', '?', ':', ';']): res = I[1] else: #L = range(I[0], I[1]+1) taillech1=I[2][1]-I[2][0] taillech2=I[3][1]-I[3][0] if taillech1<=taillech2: L = range(I[0], I[1] + 1) else: L = range(I[1], I[0]-1, -1) res = L[0] #for x in L: # if self.texte[x] == ' ': # res = x # break #else: for x in L: if self.texte[x] in [' ', '.', '-', ',', '!', '?', ':', ';']: res = x break logging.debug(self.texte[I[2][0]:I[2][1]]+' / ' +self.texte[I[3][0]:I[3][1]] + ' / ' + self.texte[I[0]:I[1]] + ' / res='+self.texte[res-1:res+2] ) return res def resoudre_recouvrement(self, I): """ part d'un intervalle qui correspond à un recouvrement et trouve une cesure judicieuse (par exemple un blanc) On coupera sur cette cesure I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] Attention !! pb dans BBL.extractDeplacements(), ne respecte plus l'assertion d'ordre si on utilise cette fonction""" sep = " .-,!?:;\r\n\t" tailleChAnt=I[2][1]-I[2][0] tailleChPost=I[3][1]-I[3][0] res = I[0] match = False #print 'ant:'+self.texte[I[2][0]:I[2][1]]+':'+str(I[2]) #print 'post:'+self.texte[I[3][0]:I[3][1]]+':'+str(I[3]) if tailleChAnt < tailleChPost: #si la chaine antérieure est + petite, on privilégie une coupure dans cettte chaine if (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in sep): res = I[0] match = True elif (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or self.texte[I[1]] in sep): res = I[1] match = True else: # sinon dans l'autre if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or self.texte[I[1]] in sep): res = I[1] match = True elif (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in sep): res = I[0] match = True if not match: #sinon, on parcours tout le recouvrement dans un sens ou l'autre if tailleChAnt <= tailleChPost: L = range(I[0], I[1] + 1) else: L = range(I[1], I[0]-1, -1) res = L[0] #L = range(I[0], I[1]+1) #for x in L: # if self.texte[x] == ' ': # res = x # match = True if not match: for x in L: if self.texte[x] in sep: res = x if tailleChAnt <= tailleChPost: pass#res = max(L[0],res-1) else: res = max(res+1,L[0]) break #logging.debug(self.texte[I[2][0]:I[2][1]]+' / ' +self.texte[I[3][0]:I[3][1]] + # ' / ' + self.texte[I[0]:I[1]] + ' / res='+self.texte[res-1:res+2] ) if res < 0: res = 0 elif res > self.lg_texte1 + self.lg_texte2: res = self.lg_texte1 + self.lg_texte2 assert 0 <= res <= self.lg_texte1 + self.lg_texte2 return res def adapter_cesure(self, cesure, seg_anterieur, seg_posterieur): """ Une cesure etant donnee, cette fonction rogne les blocs de textes qui recouvrent cette cesure, a savoir les segments anterieur et posterieur qui sont donnes comme argument """ chaine_anterieure = self.texte[seg_anterieur[0]: seg_anterieur[1]] chaine_posterieure = self.texte[seg_posterieur[0]: seg_posterieur[1]] #print "Appel adapter cesure - cesure: ", cesure, " ch1: ", chaine_anterieure, " ch2: ", chaine_posterieure #print "\t\tOccs ch1:", seg_anterieur, " occs ch2: ", seg_posterieur Nouv_chaine_anterieure = self.texte[seg_anterieur[0]: cesure] Nouv_chaine_posterieure = self.texte[cesure:seg_posterieur[1]] decalage_ant = seg_anterieur[1] - cesure decalage_post = cesure - seg_posterieur[0] min_size = self.min_size if decalage_ant != 0: #print "A ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] if len(self.blocs_texte[chaine_anterieure]) <= 2: if len(Nouv_chaine_anterieure) >= min_size: self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] del self.blocs_texte[chaine_anterieure] else: #try: assert len(self.blocs_texte[chaine_anterieure]) > 2 self.blocs_texte[chaine_anterieure].remove(seg_anterieur[0]) #except ValueError,e: # print (e,self.blocs_texte[chaine_anterieure],seg_anterieur[0],chaine_anterieure) if len(Nouv_chaine_anterieure) >= min_size: try: #if not self.blocs_texte.has_key(Nouv_chaine_anterieure): bisect.insort_right(self.blocs_texte[Nouv_chaine_anterieure],seg_anterieur[0]) except KeyError: self.blocs_texte[Nouv_chaine_anterieure] = [seg_anterieur[0]] if __debug__: if self.blocs_texte.has_key(chaine_anterieure): assert len(self.blocs_texte[chaine_anterieure]) >= 2 if decalage_post != 0: #print "P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] if len(self.blocs_texte[chaine_posterieure]) <= 2: NL = [occ + decalage_post for occ in self.blocs_texte[chaine_posterieure]] if len(Nouv_chaine_posterieure) >= min_size: self.blocs_texte[Nouv_chaine_posterieure] = NL del self.blocs_texte[chaine_posterieure] else: assert len(self.blocs_texte[chaine_posterieure]) > 2 self.blocs_texte[chaine_posterieure].remove(seg_posterieur[0]) if len(Nouv_chaine_posterieure) >= min_size: try: bisect.bisect_right(self.blocs_texte[Nouv_chaine_posterieure], cesure) except KeyError: self.blocs_texte[Nouv_chaine_posterieure] = [cesure] if __debug__: if self.blocs_texte.has_key(chaine_posterieure): assert len(self.blocs_texte[chaine_posterieure]) >= 2 #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) #print "Sortie adapter cesure Nouv ch1: ", Nouv_chaine_anterieure, " Nouv ch2: ", Nouv_chaine_posterieure #print "\t\tOccs nouv ch1:", [seg_anterieur[0], cesure], " nouv occs ch2: ", [cesure, seg_posterieur[1]] def adapter_cesure2(self, cesure, seg_anterieur, seg_posterieur): """ Une cesure etant donnee, cette fonction rogne les blocs de textes qui recouvrent cette cesure, a savoir les segments anterieur et posterieur qui sont donnes comme argument """ chaine_anterieure = self.texte[seg_anterieur[0]: seg_anterieur[1]] chaine_posterieure = self.texte[seg_posterieur[0]: seg_posterieur[1]] #print "\nAppel adapter cesure - cesure: ", cesure, " ch1: ", chaine_anterieure, " ch2: ", chaine_posterieure #print "\t\tOccs ch1:", seg_anterieur, " occs ch2: ", seg_posterieur Nouv_chaine_anterieure = self.texte[seg_anterieur[0]: cesure] Nouv_chaine_posterieure = self.texte[cesure:seg_posterieur[1]] decalage_ant = seg_anterieur[1] - cesure decalage_post = cesure - seg_posterieur[0] if decalage_ant != 0: #print "A ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] if len(self.blocs_texte[chaine_anterieure])==2: self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] #self.blocs_texte[chaine_anterieure] = [] del self.blocs_texte[chaine_anterieure] else: try: self.blocs_texte[chaine_anterieure].remove(seg_anterieur[0]) if not self.blocs_texte.has_key(Nouv_chaine_anterieure): self.blocs_texte[Nouv_chaine_anterieure]=[] self.blocs_texte[Nouv_chaine_anterieure].append(seg_anterieur[0]) except Exception: #print "EEEA ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] pass self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] del self.blocs_texte[chaine_anterieure] #= [] if decalage_post != 0: #print "P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] if len(self.blocs_texte[chaine_posterieure])==2: NL = [] for occ in self.blocs_texte[chaine_posterieure]: NL.append(occ + decalage_post) self.blocs_texte[Nouv_chaine_posterieure] = NL #self.blocs_texte[chaine_posterieure] = [] del self.blocs_texte[chaine_posterieure] else: if not self.blocs_texte.has_key(Nouv_chaine_posterieure): self.blocs_texte[Nouv_chaine_posterieure]=[] self.blocs_texte[Nouv_chaine_posterieure].append(cesure) try: self.blocs_texte[chaine_posterieure].remove(seg_posterieur[0]) except Exception: # #print "EEE P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] pass NL = [] for occ in self.blocs_texte[chaine_posterieure]: NL.append(occ + decalage_post) self.blocs_texte[Nouv_chaine_posterieure] = NL del self.blocs_texte[chaine_posterieure] #= [] #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) #print "Sortie adapter cesure Nouv ch1: ", Nouv_chaine_anterieure, " Nouv ch2: ", Nouv_chaine_posterieure #print "\t\tOccs nouv ch1:", [seg_anterieur[0], cesure], " nouv occs ch2: ", [cesure, seg_posterieur[1]] def adapter_cesure1(self, cesure, seg_anterieur, seg_posterieur): """ Une cesure etant donnee, cette fonction rogne les blocs de textes qui recouvrent cette cesure, a savoir les segments anterieur et posterieur qui sont donnes comme argument """ chaine_anterieure = self.texte[seg_anterieur[0]: seg_anterieur[1]] chaine_posterieure = self.texte[seg_posterieur[0]: seg_posterieur[1]] #print "\nAppel adapter cesure - cesure: ", cesure, " ch1: ", chaine_anterieure, " ch2: ", chaine_posterieure #print "\t\tOccs ch1:", seg_anterieur, " occs ch2: ", seg_posterieur Nouv_chaine_anterieure = self.texte[seg_anterieur[0]: cesure] Nouv_chaine_posterieure = self.texte[cesure:seg_posterieur[1]] decalage_ant = seg_anterieur[1] - cesure decalage_post = cesure - seg_posterieur[0] if decalage_ant != 0: #print "A ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] #if len(self.blocs_texte[chaine_anterieure])==2: try: self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] #self.blocs_texte[chaine_anterieure] = [] del self.blocs_texte[chaine_anterieure] except KeyError: pass #else: # try: # self.blocs_texte[chaine_anterieure].remove(seg_anterieur[0]) # if not self.blocs_texte.has_key(Nouv_chaine_anterieure): # self.blocs_texte[Nouv_chaine_anterieure]=[] # self.blocs_texte[Nouv_chaine_anterieure].append(seg_anterieur[0]) # except Exception: # #print "EEEA ",self.blocs_texte[chaine_anterieure]," sega0 ",seg_anterieur[0] # pass # self.blocs_texte[Nouv_chaine_anterieure] = self.blocs_texte[chaine_anterieure] # del self.blocs_texte[chaine_anterieure] #= [] if decalage_post != 0: #print "P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] #if len(self.blocs_texte[chaine_posterieure])==2: try: NL = [] for occ in self.blocs_texte[chaine_posterieure]: NL.append(occ + decalage_post) self.blocs_texte[Nouv_chaine_posterieure] = NL #self.blocs_texte[chaine_posterieure] = [] del self.blocs_texte[chaine_posterieure] except KeyError: pass #else: # if not self.blocs_texte.has_key(Nouv_chaine_posterieure): # self.blocs_texte[Nouv_chaine_posterieure]=[] # self.blocs_texte[Nouv_chaine_posterieure].append(cesure) # try: # self.blocs_texte[chaine_posterieure].remove(seg_posterieur[0]) # except Exception: # #print "EEE P ",self.blocs_texte[chaine_posterieure]," segp0 ",seg_posterieur[0] # pass # NL = [] # for occ in self.blocs_texte[chaine_posterieure]: # NL.append(occ + decalage_post) # self.blocs_texte[Nouv_chaine_posterieure] = NL # del self.blocs_texte[chaine_posterieure] #= [] #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) #print "Sortie adapter cesure Nouv ch1: ", Nouv_chaine_anterieure, " Nouv ch2: ", Nouv_chaine_posterieure #print "\t\tOccs nouv ch1:", [seg_anterieur[0], cesure], " nouv occs ch2: ", [cesure, seg_posterieur[1]] def adapter_cesure_nocoordo(self, cesure, seg_anterieur, seg_posterieur): """ Une cesure etant donnee, cette fonction rogne les blocs de textes qui recouvrent cette cesure, a savoir les segments anterieur et posterieur qui sont donnes comme argument """ chaine_anterieure = self.texte[seg_anterieur[0]: seg_anterieur[1]] chaine_posterieure = self.texte[seg_posterieur[0]: seg_posterieur[1]] #print "\nAppel adapter cesure - cesure: ", cesure, " ch1: ", chaine_anterieure, " ch2: ", chaine_posterieure #print "\t\tOccs ch1:", seg_anterieur, " occs ch2: ", seg_posterieur Nouv_chaine_anterieure = self.texte[seg_anterieur[0]: cesure] Nouv_chaine_posterieure = self.texte[cesure:seg_posterieur[1]] decalage_ant = seg_anterieur[1] - cesure decalage_post = cesure - seg_posterieur[0] if decalage_ant != 0: if not self.blocs_texte.has_key(Nouv_chaine_anterieure): self.blocs_texte[Nouv_chaine_anterieure] = [] self.blocs_texte[Nouv_chaine_anterieure].append(seg_anterieur[0]) try: self.blocs_texte[chaine_anterieure].remove(seg_anterieur[0]) except ValueError: pass if len(self.blocs_texte[chaine_anterieure]) == 0: del self.blocs_texte[chaine_anterieure] if decalage_post != 0: if not self.blocs_texte.has_key(Nouv_chaine_posterieure): self.blocs_texte[Nouv_chaine_posterieure] = [] self.blocs_texte[Nouv_chaine_posterieure].append(cesure) try: self.blocs_texte[chaine_posterieure].remove(seg_posterieur[0]) except ValueError: pass if len(self.blocs_texte[chaine_posterieure]) == 0: del self.blocs_texte[chaine_posterieure] def eliminer_recouvrements__(self): a = True if a: print 'self.min_size=',self.min_size tot = sum([len(chaine)*len(locc) for chaine,locc in self.blocs_texte.iteritems()]) logging.debug("debut eliminer_recouvrements len(chaines dic)=%d",tot) #print "Appel eliminer recouvrements" Recouvre = self.recouvrements(self.couverture()) i=0 while Recouvre != []: #logging.debug("debut itération "+str(i)) ; i += 1 #print "Recouvre=",Recouvre for Int in Recouvre: if a: print '----------------------------------------------------------' assert Int[2][1]-Int[2][0] >= self.min_size assert Int[3][1]-Int[3][0] >= self.min_size # Int: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] # Clefs_actives = non_nul_keys(self.blocs_texte) if ( self.blocs_texte.has_key(self.texte[Int[2][0]:Int[2][1]]) and self.blocs_texte.has_key(self.texte[Int[3][0]:Int[3][1]])): if self.tool.inclus_(Int[2], Int[3]): ch = self.texte[Int[2][0]:Int[2][1]] if a: print '*',ch,'* inclus dans *', self.texte[Int[3][0]:Int[3][1]],'*' pos = bisect.bisect_right(self.blocs_texte[ch], Int[2][0]) if a: print pos, Int[2][0], self.blocs_texte[ch] if Int[2][0] == self.blocs_texte[ch][pos-1]: #if Int[2][0] in self.blocs_texte[ch]: if a: print 'occ ',Int[2][0],' removed' self.blocs_texte[ch].remove(Int[2][0]) if len(self.blocs_texte[ch]) == 0: del self.blocs_texte[ch] elif self.tool.inclus_(Int[3], Int[2]): ch = self.texte[Int[3][0]:Int[3][1]] if a: print '*',ch,'* inclus dans *',self.texte[Int[2][0]:Int[2][1]],'*' pos = bisect.bisect_right(self.blocs_texte[ch], Int[3][0]) if a: print pos, Int[3][0], self.blocs_texte[ch] if Int[3][0] == self.blocs_texte[ch][pos-1]: #if Int[3][0] in self.blocs_texte[ch]: if a: print 'occ ',Int[3][0],' removed' self.blocs_texte[ch].remove(Int[3][0]) if len(self.blocs_texte[ch]) == 0: del self.blocs_texte[ch] else: ch1 = self.texte[Int[2][0]:Int[2][1]] ch2 = self.texte[Int[3][0]:Int[3][1]] if a: print 'chevauchement entre *',ch1,'* et *',ch2,'*' #if len(self.blocs_texte[ch1]) > 0 and len(self.blocs_texte[ch2]) > 0: if self.blocs_texte.has_key(ch1) and self.blocs_texte.has_key(ch2): pos1 = bisect.bisect_right(self.blocs_texte[ch1], Int[2][0]) pos2 = bisect.bisect_right(self.blocs_texte[ch2], Int[3][0]) if a: print pos1, Int[2][0], self.blocs_texte[ch1] if a: print pos2, Int[3][0], self.blocs_texte[ch2] if (Int[2][0] == self.blocs_texte[ch1][pos1-1] and Int[3][0] == self.blocs_texte[ch2][pos2-1]): #if Int[2][0] in self.blocs_texte[ch1] and Int[3][0] in self.blocs_texte[ch2]: self.adapter_cesure2(self.resoudre_recouvrement(Int), Int[2], Int[3]) if a: print 'cesure adapted' #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) Recouvre = self.recouvrements(self.couverture()) #print "sortie eliminer recouvrements" tot = sum([len(chaine)*len(locc) for chaine,locc in self.blocs_texte.iteritems()]) logging.debug("fin eliminer_recouvrements len(chaines dic)=%d",tot) return self.blocs_texte def eliminer_recouvrements(self, cesureRandom=True): tot = sum([len(chaine)*len(locc) for chaine,locc in self.blocs_texte.iteritems()]) #logging.debug("debut eliminer_recouvrements len(chaines dic)=%d",tot) #print "Appel eliminer recouvrements" Recouvre = self.recouvrements(self.couverture()) i=0 while Recouvre != []: #logging.debug("debut itération "+str(i)) ; i += 1 #print "Recouvre=",Recouvre for Int in Recouvre: # Int: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] # Clefs_actives = non_nul_keys(self.blocs_texte) if ( self.blocs_texte.has_key(self.texte[Int[2][0]:Int[2][1]]) and self.blocs_texte.has_key(self.texte[Int[3][0]:Int[3][1]])): if self.tool.inclus_(Int[2], Int[3]): ch = self.texte[Int[2][0]:Int[2][1]] if Int[2][0] in self.blocs_texte[ch]: self.blocs_texte[ch].remove(Int[2][0]) if len(self.blocs_texte[ch]) == 0: del self.blocs_texte[ch] elif self.tool.inclus_(Int[3], Int[2]): ch = self.texte[Int[3][0]:Int[3][1]] if Int[3][0] in self.blocs_texte[ch]: self.blocs_texte[ch].remove(Int[3][0]) if len(self.blocs_texte[ch]) == 0: del self.blocs_texte[ch] else: if cesureRandom: self.adapter_cesure_nocoordo(random.randint(Int[0],Int[1]), Int[2], Int[3]) else: self.adapter_cesure_nocoordo(self.resoudre_recouvrement(Int), Int[2], Int[3]) #self.blocs_texte = self.tool.nettoyer_dict(self.blocs_texte) Recouvre = self.recouvrements(self.couverture()) #print "sortie eliminer recouvrements" #tot = sum([len(chaine)*len(locc) for chaine,locc in self.blocs_texte.iteritems()]) #logging.debug("fin eliminer_recouvrements len(chaines dic)=%d",tot) return self.blocs_texte class Recouvrement2(Recouvrement): def resoudre_recouvrement__(self, I): """ part d'un intervalle qui correspond à un recouvrement et trouve une cesure judicieuse (par exemple un blanc) On coupera sur cette cesure I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] Attention !! pb dans BBL.extractDeplacements(), ne respecte plus l'assertion d'ordre si on utilise cette fonction""" sep = " .-,!?:;" tailleChAnt=I[2][1]-I[2][0] tailleChPost=I[3][1]-I[3][0] #print 'ant:'+self.texte[I[2][0]:I[2][1]]+':'+str(I[2]) #print 'post:'+self.texte[I[3][0]:I[3][1]]+':'+str(I[3]) if tailleChAnt < tailleChPost: #si la chaine antérieure est + petite, on privilégie une coupure dans cettte chaine if (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in sep): return I[0] if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or self.texte[I[1]] in sep): return I[1] else: # sinon dans l'autre if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or self.texte[I[1]] in sep): return I[1] if (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in sep): return I[0] if tailleChAnt <= tailleChPost: L = range(I[0], I[1] + 1) else: L = range(I[1], I[0]-1, -1) #L = range(I[0], I[1]+1) for x in L: if self.texte[x] == ' ': return x for x in L: if self.texte[x] in sep: return x return L[0] def add_bloc(self,debut,fin): chaine = self.texte[debut:fin] try: self.res[chaine].append(debut) except KeyError: self.res[chaine] = [debut] def eliminer_recouvrements(self): #logging.log(5,"debut eliminer_recouvrements") seq_repeat = self.blocs_texte #print seq_repeat[:100] self.res = {} nbFusion = 1 ; n=0 ; cut = False while nbFusion > 0 : #or (nbFusion == 0 and cut): nbFusion = 0 ; n += 1 #print n pos = old_debut = len(seq_repeat)-1 while pos >= 0: (debut,fin) = seq_repeat[pos] if debut == fin: pos -= 1 ; continue pos = debut pos -= 1 (debut_prec,fin_prec) = seq_repeat[pos] if pos == -1: (debut_prec,fin_prec) = (-1,-1) # cas d'arrêt if fin_prec >= fin: # le bloc courant est inclus dans le bloc précédent assert debut_prec <= debut, str(debut_prec)+' '+str(debut) for i in xrange(debut,fin): seq_repeat[i] = (debut_prec,fin_prec) nbFusion += 1 continue if fin_prec <= debut: # pas de chevauchement continue assert debut_prec <= debut < fin_prec <= fin # chevauchement #if cut: coupure = self.resoudre_recouvrement((debut,fin_prec,(debut_prec,fin_prec),(debut,fin))) #print 'coupure='+str(coupure) for i in xrange(coupure,fin): seq_repeat[i] = (coupure, fin) #seq_repeat[fin] = (coupure, fin) #seq_repeat[pos-1] = (coupure, fin) for i in xrange(debut_prec, coupure): seq_repeat[i] = (debut_prec, coupure) #seq_repeat[pos] = (debut_prec, coupure) # MAJ du bloc précédent coupé #seq_repeat[debut_prec] = (debut_prec, coupure) nbFusion += 1 #if nbFusion == 0 and not cut: cut = True #elif nbFusion == 0 and cut: cut = False pos = len(seq_repeat)-1 while pos >= 0: (debut,fin) = seq_repeat[pos] if fin-debut > 0: self.add_bloc(debut,fin) pos = debut - 1 #print n,seq_repeat[:100] return self.res def eliminer_recouvrementsww(self): #logging.debug("debut eliminer_recouvrements") seq_repeat = self.blocs_texte longueur_sequence = len(seq_repeat) #print seq_repeat[:100] self.res = {} nbFusion = 1 ; n=0 while nbFusion > 0: nbFusion = 0 ; n += 1 print n pos = old_debut = 0 while pos < longueur_sequence: (debut,fin) = seq_repeat[pos] pos = fin + 1 if debut == fin: continue if pos >= longueur_sequence: (debut_prec,fin_prec) = (longueur_sequence+1,longueur_sequence+1) # cas d'arrêt else: (debut_prec,fin_prec) = seq_repeat[pos] if fin >= fin_prec: # le bloc suivant est inclus dans le bloc courant assert debut <= debut_prec for i in xrange(debut_prec,fin_prec): seq_repeat[i] = (debut,fin) nbFusion += 1 continue if fin <= debut_prec: # pas de chevauchement continue if debut >= debut_prec: for i in xrange(debut,fin): seq_repeat[i] = (debut_prec,fin_prec) nbFusion += 1 continue # bloc courant inclus dans bloc suivant assert debut <= debut_prec < fin <= fin_prec, str(pos)+str((debut,fin))+str((debut_prec,fin_prec)) # chevauchement coupure = self.resoudre_recouvrement((debut_prec,fin,(debut,fin),(debut_prec,fin_prec))) for i in xrange(debut,coupure): seq_repeat[i] = (debut, coupure) #seq_repeat[fin] = (coupure, fin) #seq_repeat[pos-1] = (coupure, fin) for i in xrange(coupure, fin_prec): seq_repeat[i] = (coupure, fin_prec) nbFusion += 1 print nbFusion pos = 0 while pos < len(seq_repeat): (debut,fin) = seq_repeat[pos] self.add_bloc(debut,fin) pos = fin + 1 #print n,seq_repeat[:100] return self.res def eliminer_recouvrementsuu(self): logging.debug("debut eliminer_recouvrements") seq_repeat = self.blocs_texte self.res = {} pos = old_debut = len(seq_repeat)-1 #old_debut = len(seq_repeat)+1 (debut_av,fin_av) = (len(seq_repeat),len(seq_repeat)) while pos >= 0: #print pos (debut,fin) = seq_repeat[pos] pos = debut pos -= 1 if debut == fin: continue (debut_prec,fin_prec) = seq_repeat[pos] if pos == -1: (debut_prec,fin_prec) = (-1,-1) # cas d'arrêt if fin_prec >= fin: # le bloc courant est inclus dans le bloc précédent #print (debut_prec,fin_prec),(debut,fin) assert debut_prec <= debut continue if fin_prec <= debut: # pas de chevauchement self.add_bloc(debut,fin); continue assert debut_prec <= debut < fin_prec <= fin # chevauchement coupure = self.resoudre_recouvrement((debut,fin_prec,(debut_prec,fin_prec),(debut,fin))) self.add_bloc(coupure,fin) seq_repeat[pos] = (debut_prec, coupure) # MAJ du bloc précédent coupé return self.res def eliminer_recouvrementsMMM(self): logging.debug("debut eliminer_recouvrements") seq_repeat = self.blocs_texte longueur_sequence = len(seq_repeat) self.res = {} pos = old_debut = 0 #old_debut = len(seq_repeat)+1 #(debut_av,fin_av) = (len(seq_repeat),len(seq_repeat)) while pos < longueur_sequence: #print pos (debut,fin) = seq_repeat[pos] pos = fin pos += 1 if debut == fin: continue if pos >= longueur_sequence: (debut_prec,fin_prec) = (longueur_sequence+1,longueur_sequence+1) # cas d'arrêt else: (debut_prec,fin_prec) = seq_repeat[pos] if fin >= fin_prec: # le bloc suivant est inclus dans le bloc courant #print (debut_prec,fin_prec),(debut,fin) assert debut <= debut_prec self.add_bloc(debut,fin) continue if fin <= debut_prec: # pas de chevauchement self.add_bloc(debut,fin); continue if debut >= debut_prec: continue # bloc courant inclus dans bloc suivant assert debut <= debut_prec < fin <= fin_prec, str(pos)+str((debut,fin))+str((debut_prec,fin_prec)) # chevauchement coupure = self.resoudre_recouvrement((debut_prec,fin,(debut,fin),(debut_prec,fin_prec))) self.add_bloc(debut,coupure) seq_repeat[pos] = (coupure,fin_prec) # MAJ du bloc précédent coupé return self.res def eliminer_recouvrements__(self): logging.debug("debut eliminer_recouvrements") seq_repeat = self.blocs_texte res = {} pos = len(seq_repeat)-1 old_debut = len(seq_repeat)+1 (debut_av,fin_av) = (len(seq_repeat),len(seq_repeat)) while pos >= 0: #print 'pos=',pos pos_BU = pos (debut,fin) = seq_repeat[pos] #print (debut,fin),self.texte[debut:fin] assert debut <= fin if debut == fin: pos = debut-1 #(debut,fin) = seq_repeat[pos] else: pos = debut # remonte au début du bloc (debut_prec,fin_prec) = seq_repeat[pos-1] #print (debut_prec,fin_prec),self.texte[debut_prec:fin_prec] while pos-2 >= 0: (debut_prec2,fin_prec2) = seq_repeat[pos-2] if fin_prec2 >= fin_prec: assert debut_prec2 <= debut_prec,str(debut_prec2)+'/'+str(debut_prec) (debut_prec,fin_prec) = seq_repeat[pos-2] pos -= 1 else: break #print (debut_prec,fin_prec),self.texte[debut_prec:fin_prec] pos -= 1 # pos désigne maintenant le bloc précédent if fin_prec >= fin: # bloc courant inclus dans bloc precedent continue #= debut -1 ; continue #(debut_prec,fin_prec) = seq_repeat[pos-1] if fin_prec > debut: # chevauchement coupure = self.resoudre_recouvrement((debut,fin_prec,(debut_prec,fin_prec),(debut,fin))) debut = coupure seq_repeat[pos] = (debut_prec,coupure) #debut-1] = (debut_prec,coupure) #print 'coupure=',coupure # le bloc est overlap-free, on peut l'ajouter au dico résultat if fin > debut_av: coupure2 = debut_av fin = coupure2 #print 'coupure2=',coupure2 assert fin <= old_debut,str(fin)+'/'+str(old_debut) assert fin <= debut_av chaine = self.texte[debut:fin] try: res[chaine].append(debut) except KeyError: res[chaine] = [debut] (debut_av,fin_av) = (debut,fin) old_debut = debut #pos = debut-1 #assert pos < pos_BU, str(pos)+'/'+str(pos_BU) #print '------------------' logging.debug("fin eliminer_recouvrements") return res def eliminer_recouvrements_(self): logging.debug("debut eliminer_recouvrements") seq_repeat = self.blocs_texte res = {} pos = 0#len(seq_repeat)-1 old_fin = -1#len(seq_repeat)+1 (debut_av,fin_av) = (-1,-1)#(len(seq_repeat),len(seq_repeat)) while pos < len(seq_repeat)-1: #print 'pos=',pos pos_BU = pos (debut,fin) = seq_repeat[pos] #print (debut,fin),self.texte[debut:fin] assert debut <= fin if debut == fin: pos = fin+1 #(debut,fin) = seq_repeat[pos] else: pos = fin # remonte au début du bloc if pos >= len(seq_repeat)-1: try: chaine = self.texte[debut:fin] res[chaine].append(debut) except KeyError: res[chaine] = [debut] break (debut_prec,fin_prec) = seq_repeat[pos+1] #print (debut_prec,fin_prec),self.texte[debut_prec:fin_prec] while pos+2 = fin_prec): assert debut_prec2 >= debut_prec,str(debut_prec2)+'/'+str(debut_prec) (debut_prec,fin_prec) = seq_repeat[pos+2] pos += 1 else: break pos += 1 #print (debut_prec,fin_prec),self.texte[debut_prec:fin_prec] #if fin >= fin_prec: # bloc courant inclus dans bloc precedent # pos = debut+1 ; continue # (debut_prec,fin_prec) = seq_repeat[pos-1] if debut_prec < fin: # chevauchement coupure = self.resoudre_recouvrement((debut_prec,fin,(debut,fin),(debut_prec,fin_prec))) fin = coupure seq_repeat[pos] = (coupure,fin_prec) #fin+1] = (coupure,fin_prec) #print 'coupure=',coupure # le bloc est overlap-free, on peut l'ajouter au dico résultat if debut > fin_av: coupure2 = fin_av debut = coupure2 #print 'coupure2=',coupure2 assert fin >= old_fin,str(fin)+'/'+str(old_fin) #assert fin <= debut_av chaine = self.texte[debut:fin] try: res[chaine].append(debut) except KeyError: res[chaine] = [debut] (debut_av,fin_av) = (debut,fin) old_fin = fin #pos = fin+1 #assert pos < pos_BU, str(pos)+'/'+str(pos_BU) #print '------------------' logging.debug("fin eliminer_recouvrements") return res class Recouvrement3(Recouvrement2): """ Renvoie un dico indexé par un tuplet (cle,longueur) plutot que par chaine[debut:fin], ce qui évite de stocker les chaines dans le dico """ def add_bloc(self,debut,fin): cle = hash(self.texte[debut:fin]) longueur = fin-debut try: self.res[(cle,longueur)].append(debut) except KeyError: self.res[(cle,longueur)] = [debut] self.NOSMEM_nb_bloc += 1 class RecouvrementNaif(Recouvrement3): def __init__(self,texte,blocs_texte,lg_texte1,min_size): self.min_size = min_size Recouvrement3.__init__(self,texte,blocs_texte,lg_texte1) def transformListe(self): """ Transforme self.blocs_texte en une file de priorité indexé par la taille des blocs: les blocs les + grands sont prioritaires. Un bloc est constitué de son index, sa longueur, sa cle unique et sa liste d'occurrences""" liste1 = [] ; liste2 = [] ; liste = [] ; listet = [] nb_bloc = 0 ; tot=0 ; nb_occ = 0 for longueur, dicoOcc in self.blocs_texte.iteritems(): for cle_hash, lOcc in dicoOcc.iteritems(): for occ in lOcc: if occ < self.lg_texte1: bisect.insort_right(liste1, (occ,occ+longueur)) else: bisect.insort_right(liste2, (occ,occ+longueur)) bisect.insort_right(liste, (occ,occ+longueur)) lOcc.sort() bisect.insort_right(listet, [lOcc[0], longueur, cle_hash , lOcc]) nb_bloc += 1 nb_occ += len(lOcc) tot += len(lOcc) * longueur ###logging.debug( hq) assert len(liste) == nb_occ self.SMEM_nb_bloc = nb_bloc # nb SMEM à l'origine self.SMEM_nb_occ = nb_occ # nb d'occurences de SMEM à l'origine self.SMEM_tot_size = tot # taille totale des SMEM à l'origine ###logging.debug("debut eliminer_recouvrements len(chaines dic)=%d",tot) return listet def eliminer_recouvrements(self): listet = self.transformListe() longueur_totale = self.lg_texte1+self.lg_texte2+1 self.seq_repeat_deb = Numeric.zeros(longueur_totale,Numeric.Int) self.seq_repeat_fin = Numeric.zeros(longueur_totale,Numeric.Int) for i in xrange(longueur_totale): #self.seq_repeat.append((i,i)) self.seq_repeat_deb[i] = i self.seq_repeat_fin[i] = i self.totalAjout = self.totalRogneG = self.totalRogneD = self.nb_reinclusion = 0 bb= False i = 0 while i < len(listet)-1: [deb, longueur, cle_hash , lOcc] = listet[i] k = 0 while k < len(lOcc)-1: #auto-recouvrement, une merveille de la nature stringologique occ1 = lOcc[k] ; occ2 = lOcc[k+1] if occ1+longueur > occ2: pos = lOcc.index(occ2) lOcc.pop(pos) else: k+= 1 j = i + 1 while j < len(listet): (deb2, longueur2, cle_hash2 , lOcc2) = listet[j] dd1 = dd2 = dg1 = dg2 = 0 for occ in lOcc: for occ2 in lOcc2: #print self.texte[occ:occ+longueur],'vs.',self.texte[occ2:occ2+longueur2] if '&&é&éé.nous.' == self.texte[occ:occ+longueur] :# and '.la.place.gommant.sa.fla' == self.texte[occ2:occ2+longueur2]: print listet[i],listet[j] bb = True #print occ < occ2 < occ+longueur, occ+longueur < longueur_totale-1 #print occ2 < occ < occ2+longueur2, occ2+longueur2 < longueur_totale-1 if occ <= occ2 < occ2+longueur2 <= occ+longueur: pos = lOcc2.index(occ2) lOcc2.pop(pos) if occ2 <= occ < occ+longueur <= occ2+longueur2: pos = lOcc.index(occ) lOcc.pop(pos) if occ < occ2 < occ+longueur and occ+longueur < longueur_totale-1: if bb: print dd1,dg1 cd = self.resoudre_recouvrement([occ2, occ+longueur,[occ,occ+longueur], [occ2,occ2+longueur2]]) dd1 = max(dd1,occ+longueur-cd) dg1 = max(dg1, cd-occ2) if bb: print cd,dd1,dg1 if occ2 < occ < occ2+longueur2 and occ2+longueur2 < longueur_totale-1: if bb: print dd2,dg2 cg = self.resoudre_recouvrement([occ, occ2+longueur2,[occ2,occ2+longueur2], [occ,occ+longueur]]) dg2 = max(dg2, cg-occ) dd2 = max(dd2, occ2+longueur2-cg) if bb: print cg,dd2,dg2 if dd1 > 0 or dg1 > 0: longueur -= dd1 lOcc2 = [occ+dg1 for occ in lOcc2] longueur2 -= dg1 if dd2 > 0 or dg2 > 0: longueur2 -= dd2 lOcc = [occ+dg2 for occ in lOcc] longueur -= dg2 if len(lOcc2) == 0: listet[j] = [sys.maxint, longueur2, cle_hash2 , lOcc2] else: listet[j] = [lOcc2[0], longueur2, cle_hash2 , lOcc2] if bb: print listet[i],listet[j] j += 1 if bb: bb= False if len(lOcc) == 0: listet[i] = [sys.maxint, longueur, cle_hash , lOcc] else: listet[i] = [lOcc[0], longueur, cle_hash , lOcc] (deb, longueur, cle_hash , lOcc) = listet[i] i += 1 #HqOccBlocc vide, on a fini #logging.debug(self.seq_repeat) #i = 0 #while i < len(listet self.NOSMEM_nb_bloc = 0 # nb NOSMEM self.NOSMEM_nb_occ = 0 # nb d'occurences de NOSMEM self.NOSMEM_tot_size = 0 # taille totale des NOSMEM self.res = {} pos = 0#len(self.seq_repeat)-1 #while pos >= 0: for nosmem in listet: (deb, longueur, cle_hash , lOcc) = nosmem if longueur == 0: #print 'ZERO',nosmem continue if len(lOcc) == 1: #print 'UN LEN',lOcc continue prev = -1 for occ in lOcc: if occ > prev: self.add_bloc(occ,occ+longueur) self.NOSMEM_nb_occ += 1 self.NOSMEM_tot_size += longueur prev = occ + longueur #logging.debug('=========================') #logging.debug('fin recouv self.totalAjout=%d / self.totalRogneG=%d / self.totalRogneD=%d / self.nb_reinclusion=%d / len(self.res)=%d', # self.totalAjout,self.totalRogneG,self.totalRogneD,self.nb_reinclusion,len(self.res)) #logging.debug('self.res = '+str(self.res)) for cle,lOcc in self.res.iteritems(): lOcc.reverse() # on reverse car dans la suite dans l'algo c'est nécessaire return self.res def resoudre_recouvrement_random(self, I): """ part d'un intervalle qui correspond à un recouvrement et trouve une cesure judicieuse (par exemple un blanc) On coupera sur cette cesure I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] Attention !! pb dans BBL.extractDeplacements(), ne respecte plus l'assertion d'ordre si on utilise cette fonction""" sep = " .-,!?:;\r\n\t" tailleChAnt=I[2][1]-I[2][0] tailleChPost=I[3][1]-I[3][0] res = random.randint(I[0],I[1]) if res < 0: res = 0 elif res > self.lg_texte1 + self.lg_texte2: res = self.lg_texte1 + self.lg_texte2 assert 0 <= res <= self.lg_texte1 + self.lg_texte2 return res class Recouvrement4(Recouvrement3): def __init__(self,texte,blocs_texte,lg_texte1,min_size): self.min_size = min_size Recouvrement3.__init__(self,texte,blocs_texte,lg_texte1) def eliminer_recouvrements(self): #self.seq_repeat = [] ; self.dicoOccLiee = {} longueur_totale = self.lg_texte1+self.lg_texte2+1 self.seq_repeat_deb = Numeric.zeros(longueur_totale,Numeric.Int) self.seq_repeat_fin = Numeric.zeros(longueur_totale,Numeric.Int) for i in xrange(longueur_totale): #self.seq_repeat.append((i,i)) self.seq_repeat_deb[i] = i self.seq_repeat_fin[i] = i self.hqOccBloc = self.transformHeapQueue() self.old_len_add = 10000000 self.totalAjout = self.totalRogneG = self.totalRogneD = self.nb_reinclusion = 0 while len(self.hqOccBloc) > 0: # parcour de tous les blocs ###logging.debug(len(self.hqOccBloc)) (index,longueur,cle_hash,lOcc) = heapq.heappop(self.hqOccBloc) # bloc le + long ###logging.debug(len(self.hqOccBloc)) ###logging.debug(str((index,longueur,cle_hash,lOcc))+' / bloc: '+self.texte[lOcc[0]:lOcc[0]+longueur]) #if longueur >= self.min_size: if len(lOcc) > 1: #logging.debug('ajoutOccurences: '+self.texte[lOcc[0]:lOcc[0]+longueur]+' / '+str(longueur)+' / '+str(lOcc)) self.ajoutOccurences(longueur,lOcc) ###logging.debug(len(self.hqOccBloc)) #logging.debug('----------------------------') #HqOccBlocc vide, on a fini #logging.debug(self.seq_repeat) self.NOSMEM_nb_bloc = 0 # nb NOSMEM self.NOSMEM_nb_occ = 0 # nb d'occurences de NOSMEM self.NOSMEM_tot_size = 0 # taille totale des NOSMEM self.res = {} pos = 0#len(self.seq_repeat)-1 #while pos >= 0: while pos < len(self.seq_repeat_deb): debut = self.seq_repeat_deb[pos] fin = self.seq_repeat_fin[pos] if fin-debut > 0: self.add_bloc(debut,fin) pos = fin self.NOSMEM_nb_occ += 1 self.NOSMEM_tot_size += fin-debut else: pos += 1 #pos = debut - 1 #logging.debug('=========================') #logging.debug('fin recouv self.totalAjout=%d / self.totalRogneG=%d / self.totalRogneD=%d / self.nb_reinclusion=%d / len(self.res)=%d', # self.totalAjout,self.totalRogneG,self.totalRogneD,self.nb_reinclusion,len(self.res)) #logging.debug('self.res = '+str(self.res)) for cle,lOcc in self.res.iteritems(): lOcc.reverse() # on reverse car dans la suite dans l'algo c'est nécessaire return self.res def ajoutOccurences(self,longueur,lOcc): """ Ajoute la liste des occurrences lOcc à self.seq_repeat """ lNonOverlap, lOverlap = self.checkOverlap(longueur,lOcc) if len(lNonOverlap) == 1: # bloc non chevauchant unique, on l'ajoute aux blocs chevauchants # car il peut y en avoir plusieurs qui ont été césurés bisect.insort_right(lOverlap,lNonOverlap[0]) elif len(lNonOverlap) > 1: # si plusieurs non chevauchants, on les ajoute à self.seq_repeat cle = hash(self.texte[lNonOverlap[0][1]:lNonOverlap[0][2]]) longueur2 = lNonOverlap[0][2] - lNonOverlap[0][1] locc = [item[1] for item in lNonOverlap] try: # dico stockant les occurrences d'une chaine #self.dicoOccLiee[(cle,longueur2)].update(set(locc)) self.dicoOccLiee[(cle,longueur2)].extend(locc) except KeyError: self.dicoOccLiee[(cle,longueur2)] = locc self.addOccSeq(lNonOverlap) if len(lOverlap) > 1: # si plusieurs blocs ayant des chevauchements item_min = lOverlap[0] ; lOcc = [] for item in lOverlap: assert item_min[0] <= item[0] # le + petit max_decalageG = max_decalageD = 0 for item in lOverlap: # on cherche les + grands décalages G et D qui vont être # utilisés pour césurer l'ensemble des blocs chevauchants max_decalageG = max(max_decalageG, item[3]) max_decalageD = max(max_decalageD, item[4]) for item in lOverlap: # construction des nouvelles occurences des blocs, on enlève item[3] # qui est césure éventuellement déjà attachée à un bloc lOcc.append(item[1]-item[3]+max_decalageG) # calcul de la nouvelle longueur des blocs nouveau_debut_item_min = item_min[1]-item_min[3]+max_decalageG nouveau_fin_item_min = item_min[2]-item_min[4]+max_decalageD longueur2 = nouveau_fin_item_min - nouveau_debut_item_min if longueur2 > 0: # restockage du bloc dans la file de priotrité cle_hash = hash(self.texte[nouveau_debut_item_min:nouveau_fin_item_min]) item = (1.0/longueur2,longueur2,cle_hash,lOcc) #logging.debug('reinclusion de '+str(item)) self.nb_reinclusion += 1 heapq.heappush(self.hqOccBloc, item) def addOccSeq(self,lNonOverlap): """Ajout effectif des occurrences d'un bloc à self.seq_repeat """ #logging.debug('addOccSeq: lNonOverlap='+str(lNonOverlap)) cle_dic = hash(self.texte[lNonOverlap[0][1]:lNonOverlap[0][2]]) # cle du bloc longeur_dic = lNonOverlap[0][0] # longueur du bloc for longueur,debut,fin,decalageG,decalageD in lNonOverlap: # parcours des occurrences du bloc #logging.debug('ajout: '+self.texte[debut:debut+longueur]) self.totalAjout += longueur # si chevauchement à gauche #debut_prec,fin_prec = self.seq_repeat[debut] # bloc existant à gauche de l'occ à insérer debut_prec = self.seq_repeat_deb[debut] fin_prec = self.seq_repeat_fin[debut] if debut < fin_prec: #debut_prec < fin_prec and #logging.debug('addOccSeq: cesureG / '+str((debut_prec,fin_prec))) pos_cesure = debut - debut_prec # position de la césure dans le bloc longueur_prec = fin_prec - debut_prec # longueur bloc précédent cle_prec = hash(self.texte[debut_prec:fin_prec]) # clé bloc précédent if self.dicoOccLiee.has_key((cle_prec,longueur_prec)): locc_prec = list(self.dicoOccLiee[(cle_prec,longueur_prec)]) # liste des occ du bloc précédent else: locc_prec = [debut_prec] # si il n'y en a pas alors au moins debut_prec for debut_occ_prec in locc_prec:# pour chaque occ du bloc précédent, on va le césurer for i in xrange(debut_occ_prec,debut_occ_prec+longueur_prec):# chaque caractère du bloc est modifié dans self.seq_repeat if i < debut_occ_prec+pos_cesure: #self.seq_repeat[i] = (debut_occ_prec,debut_occ_prec+pos_cesure) self.seq_repeat_deb[i] = debut_occ_prec self.seq_repeat_fin[i] = debut_occ_prec+pos_cesure else: #self.seq_repeat[i] = (i,i) # partie césurée qui va être remodifiée par le nouveau bloc self.seq_repeat_deb[i] = i self.seq_repeat_fin[i] = i self.totalRogneG += 1 # suppression de l'ancienne chaine du bloc dans le dico et ajout du nouveau bloc précédent césuré if self.dicoOccLiee.has_key((cle_prec,longueur_prec)): del self.dicoOccLiee[(cle_prec,longueur_prec)] try: self.dicoOccLiee[hash(self.texte[locc_prec[0]:locc_prec[0]+pos_cesure]),pos_cesure].extend(locc_prec) except KeyError: self.dicoOccLiee[hash(self.texte[locc_prec[0]:locc_prec[0]+pos_cesure]),pos_cesure]=locc_prec # chevauchement à droite #debut_suiv,fin_suiv = self.seq_repeat[fin] # bloc suivant debut_suiv = self.seq_repeat_deb[fin] fin_suiv = self.seq_repeat_fin[fin] if debut_suiv < fin: #logging.debug('addOccSeq: cesureG / '+str((debut_suiv,fin_suiv))) pos_cesure = fin - debut_suiv # position de la césure dans le bloc suivant longueur_suiv = fin_suiv - debut_suiv # longueur du bloc suivant cle_suiv = hash(self.texte[debut_suiv:fin_suiv]) # cle du bloc suivant if self.dicoOccLiee.has_key((cle_suiv,longueur_suiv)): # occurrences du bloc suivant locc_suiv = list(self.dicoOccLiee[(cle_suiv,longueur_suiv)]) else: locc_suiv = [debut_suiv] # au minimum debut_suiv nouv_longueur_suiv = longueur_suiv - pos_cesure # nouvelle longueur du bloc après césure nouv_locc_suiv = [] # nouvelle liste des occurrences du bloc suivant après césure for debut_occ_suiv in locc_suiv: # pour chaque occurrence du bloc suivant for i in xrange(debut_occ_suiv,debut_occ_suiv+longueur_suiv): # chaque caractère du bloc suivant à césurer if i < debut_occ_suiv+pos_cesure: #self.seq_repeat[i] = (i,i) # partie à césurer self.seq_repeat_deb[i] = i ; self.seq_repeat_fin[i] = i else: #self.seq_repeat[i] = (debut_occ_suiv+pos_cesure,debut_occ_suiv+longueur_suiv) # partie conservée self.seq_repeat_deb[i] = debut_occ_suiv+pos_cesure self.seq_repeat_fin[i] = debut_occ_suiv+longueur_suiv nouv_locc_suiv.append(debut_occ_suiv+pos_cesure) # stockage du nouveau début du bloc suivant self.totalRogneD += 1 # suppression de l'ancienne chaine du bloc dans le dico et ajout du nouveau bloc suivant césuré if self.dicoOccLiee.has_key((cle_suiv,longueur_suiv)): del self.dicoOccLiee[(cle_suiv,longueur_suiv)] try: self.dicoOccLiee[hash(self.texte[nouv_locc_suiv[0]:nouv_locc_suiv[0]+nouv_longueur_suiv]),nouv_longueur_suiv].extend(nouv_locc_suiv) except KeyError: self.dicoOccLiee[hash(self.texte[nouv_locc_suiv[0]:nouv_locc_suiv[0]+nouv_longueur_suiv]),nouv_longueur_suiv]=nouv_locc_suiv # ajout effectif du bloc après le travail de mise à jour des blocs chevauchants #if debut < fin_prec: assert self.seq_repeat[debut] == (debut,debut), self.seq_repeat[debut-5:debut+5] #if debut_suiv < fin: assert self.seq_repeat[fin] == (fin,fin), self.seq_repeat[fin-5:fin+5] for i in xrange(debut,fin): #self.seq_repeat[i] = (debut,fin) self.seq_repeat_deb[i] = debut self.seq_repeat_fin[i] = fin def checkOverlap(self,longueur,lOcc): '''Recherche des chevauchements gauche et droits d'une liste d'occurrences d'un bloc. Les césures potentielles sont recherchées et stockées avec les blocs associés. lNonOverlap est une liste d'occurrences sans chevauchement et lOverlap avec. lOverlap est ordonée de façon croissante sur la longueur des blocs césurés. les overlap G et D sont résolus ensemble''' ###logging.debug(str(longueur)+'/'+str(lOcc)) lNonOverlap = [] ; lOverlap = [] ; discarded = 0 for occ in lOcc: debut = occ ; fin = occ+longueur try: #d1,f1 = self.seq_repeat[debut] # bloc existant au début du bloc à insérer d1 = self.seq_repeat_deb[debut] ; f1 = self.seq_repeat_fin[debut] #d2,f2 = self.seq_repeat[fin] # bloc existant à la fin du bloc à insérer d2 = self.seq_repeat_deb[fin] ; f2 = self.seq_repeat_fin[fin] except IndexError: # sale return lNonOverlap, lOverlap ###logging.debug((d1,f1)) if d1 <= debut < fin <= f1: # bloc courant inclus dans un autre bloc, on le discard discarded += 1 ###logging.debug(str(debut) + ' discarded') else: overlapG = d1 <= debut < f1 <= fin # chevauchement gauche ? overlapD = debut <= d2 < fin <= f2 # chevauchement droit ? # recherche des points de césure if overlapG: cesureG = self.resoudre_recouvrement([debut,f1,[d1,f1],[debut,fin]]) else: cesureG = debut if overlapD: cesureD = self.resoudre_recouvrement([d2,fin,[debut,fin],[d2,f2]]) else: cesureD = fin #logging.debug('checkOverlap: cesureG = '+str(cesureG)+' / cesureD = '+str(cesureD)) # calcul des décalages decalageG = cesureG - debut ; decalageD = fin - cesureD # ajout des blocs avec infos de césure dans les listes résultat if (not overlapG and not overlapD) or (decalageG == decalageD == 0): assert cesureG == debut and cesureD == fin lNonOverlap.append((longueur,debut,debut+longueur,0,0)) else: bisect.insort_right(lOverlap,(cesureD-cesureG,cesureG,cesureD,decalageG,decalageD)) assert len(lOcc) == discarded + len(lNonOverlap) + len(lOverlap) #logging.debug('discarded = '+str(discarded) +' / lNonOverlap = '+str(lNonOverlap)+' / lOverlap = '+str(lOverlap)) return lNonOverlap, lOverlap def transformHeapQueue(self): """ Transforme self.blocs_texte en une file de priorité indexé par la taille des blocs: les blocs les + grands sont prioritaires. Un bloc est constitué de son index, sa longueur, sa cle unique et sa liste d'occurrences""" hq = [] ; nb_bloc = 0 ; tot=0 ; nb_occ = 0 for longueur, dicoOcc in self.blocs_texte.iteritems(): for cle_hash, lOcc in dicoOcc.iteritems(): # item indexé par l'inverse de la longueur pour avoir les blocs # les plus longs au début du heapq item = (1.0/longueur,longueur,cle_hash,lOcc) heapq.heappush(hq, item) nb_bloc += 1 nb_occ += len(lOcc) tot += len(lOcc) * longueur ###logging.debug( hq) assert len(hq) == nb_bloc self.SMEM_nb_bloc = nb_bloc # nb SMEM à l'origine self.SMEM_nb_occ = nb_occ # nb d'occurences de SMEM à l'origine self.SMEM_tot_size = tot # taille totale des SMEM à l'origine ###logging.debug("debut eliminer_recouvrements len(chaines dic)=%d",tot) return hq def resoudre_recouvrement__(self, I): """ part d'un intervalle qui corresponds a un recouvrement et trouve une cesure judicieuse (par exemple un blanc) On coupera sur cette cesure I: [occ_debut, occ_fin, chaine_anterieure, chaine_posterieure] la chaine la + longue est favorisée""" #logging.debug('resoudre_recouvrement: I='+str(I)) taillech1=I[2][1]-I[2][0] taillech2=I[3][1]-I[3][0] sep = " .-,!?:;\r\n\t" if taillech1<=taillech2: if (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in sep): return I[0] if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or self.texte[I[1]] in sep): return I[1] else: if (I[1] == (self.lg_texte1 - 1) or I[1] == (self.lg_texte1 + self.lg_texte2 - 1) or self.texte[I[1]] in sep): return I[1] if (I[0] == 0 or I[0] == self.lg_texte1 or self.texte[I[0]-1] in sep): return I[0] if taillech1<=taillech2: L = range(I[0], I[1] + 1) else: L = range(I[1], I[0]-1, -1) #L = range(I[0], I[1]+1) for x in L: if self.texte[x] == ' ': return x for x in L: if self.texte[x] in sep: return x return L[0]