# -*- 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 os, sys, re, bisect class Utile(object): # renvoie un nom de fichier, si celui-ci existe def nom_fichier(self, chaine) : drapeau = 0 if os.name == 'mac': dir_texte = 'textes:' else: dir_texte = '/textes/' while drapeau == 0 : drapeau = 1 fic = raw_input(chaine) nom = os.getcwd() + dir_texte + fic + '.txt' if os.path.isfile(nom): return fic else: ## print nom, " n'est pas un nom de fichier! Recommencez." # L = os.listdir(os.getcwd() + dir_texte) ## for D in L: ## if os.path.isfile(os.getcwd() + dir_texte + D): ## print " > ", D drapeau = 0 def ouvrir(self, fic, m): # ouvre le fichier fic (nom relatif) en mode m if os.name == 'mac' : if m == "r": dir_texte = 'textes:' else: dir_texte = 'sortie:' else: if m == "r": dir_texte = '/textes/' else: dir_texte = '/sortie/' abs_fic = os.getcwd() + dir_texte + fic + '.txt' return open(abs_fic, m) def lire_fic(self, fic): # lit le contenu du fichier et le renvoie sous forme d'une chaîne # fic est le nom relatif du fichier (sans l'extension '.txt') fichier_entree = self.ouvrir(fic, "r") return fichier_entree.read() def creer_fic(self, fic): if not 'sortie' in os.listdir(os.getcwd()): os.mkdir('sortie') return self.ouvrir(fic, "w") def ajout_fic(self, fic, T): fichier_sortie = self.ouvrir(fic, "a") fichier_sortie.write(T) def non_nul_keys(self, D) : # donne la liste des clefs non vides d'un dictionnaire D L = [ ] for Clef in D.keys() : if D[Clef] != { } and D[Clef] != [] : L.append(Clef) #if D[Clef] == [] : #print "Clef non nulle... '", Clef, "' dictionnaire: ", D return L def non_nul_values(self, D) : # donne la liste des clefs non vides d'un dictionnaire D L = [ ] if D.values != {} : for val in D.values() : if val != { } or val != [] : L.append(val) return L def dif_intervalles(self, L, C) : # enlève un intervalle de valeurs dans une liste d'intervalles # L est une liste d'intervalles, C, un intervalle NL = [ ] ncouple = [] nncouple = [] for couple in L : if couple[0] < C[0] : if couple[1] >= C[0] : ncouple.append(couple[0]) ncouple.append(C[0]) if couple[1] > C[1] : nncouple.append(C[1]) nncouple.append(couple[1]) elif couple[1] > C[1] and couple[0] <= C[1] : ncouple.append(C[1]) ncouple.append(couple[1]) if ncouple != [] : NL.append(ncouple) ncouple = [] if nncouple != [] : NL.append(nncouple) nncouple = [] if couple[0] > C[1] or couple[1] < C[0] : NL.append(couple) return NL def soustr_l_intervalles(self, P, L): # soustractrion de deux liste d'intervalles L = L[:] # on copie L pour pouvoir modifier la vairable locale sans toucher celle de l'appel while len(L) > 0: ##L <> []: P = self.dif_intervalles(P, L.pop(0)) #L[0]) #L = L[1:] #del L[0] #;L = L[1:] #L.pop(0) #L = L[1:] return P def miroir(self, locc, debut, fin): """Prends une liste d'intervalles définis sur l'intervalle [debut,fin] et retourne la différence entre [début,fin] et tous les elements de cette liste en temps linéaire(locc)""" LRes = [] pos = debut for (d,f) in locc: if pos < d : # intervalle non nul LRes.append((pos,d)) pos = f # passe à l'intervalle suivant if pos < fin: LRes.append((pos,fin)) # dernier element eventuel #if __debug__: # longueur1 = longueur2 = 0 # for d,f in locc: longueur1 += f-d # for d,f in LRes: longueur2 += f-d #print longueur1,longueur2 #assert longueur2 == fin-debut-longueur1 #marche pas à cause des chevauchements return LRes def ajout_intervalle(self, L, C) : # ajoute un intervalle de valeurs dans une liste d'intervalles # L est une liste d'intervalles, C un intervalle Q = [] while L <> [] and L[-1][-1] >= C[0] : if L[-1][0] > C[1]: Q = [L[-1]] + Q L.pop() #L = L[0:-1] else: C = [min(C[0], L[-1][0]), max(C[1], L[-1][-1])] L.pop() #L = L[0:-1] L.append(C) return L+Q def addition_l_intervalle(self,L, LC):#ajout liste intervalles sans fusion for x in LC: #L = self.addition_intervalle(L, x) bisect.insort_right(L, x) return L def addition_intervalle(self, L, C) : # ajoute un intervalle de valeurs, sans # fusionner les intervalles #print "Appel addition intervalle L:", L, "; C:", C bisect.insort_right(L, C) return L #i = 0 #l = len(L) #if (L == [] or L[0][0] >= C[0]): # return [C]+L #while i < l: # if L[i][0] >= C[0]: # return L[0:i] + [C] + L[i:] # else: i = i+1 #return L+[C] def inclusion(self, L1, L2) : # renvoie vrai si la liste L1 est incluse dans la liste L2 for elt in L1 : if not elt in L2 : return 0 return 1 def difference(self, L1,L2): # renvoie la difference entre L1 et L2 L=L1[:] for X in L2: if X in L: L.remove(X) return L def difference_sym(self, L1,L2): # renvoie la difference symétrique entre L1 et L2 L=[] for x in L1: if x not in L2: L.append(x) for x in L2: if x not in L1 and x not in L: L.append(x) return L def inclus(self, I, L): # renvoie vrai si l'intervalle I est inclus dans l'un des intervalles de L for elt in L: if (I[0]>= elt[0] and I[1] <= elt[1] ): return 1 return 0 def inclus_(self, I1, I2): # renvoie vrai si l'intervalle I1 est inclus dans I2 if (I1[0] >= I2[0] and I1[1] <= I2[1]): return 1 return 0 def int_inclus(self, I, L): # renvoie l'ensemble des intervalles de L inclus dans l'intervalle I` LL = [] while L <> []: if self.inclus_(L[-1], I): LL.append(L[-1]) #L = L[:-1] L.pop() return LL def longueur(self, L): # longueur d'une liste d'intervalles, c'est-à-dire longueur de la chaîne couverte par la liste n = 0 while L <> []: n = n + L[0][1] - L[0][0] #L = L[1:] L.pop(0) return n def union(self, L1, L2): # renvoie la réunion de deux listes d'intervalles for I in L1: L2 = self.ajout_intervalle(L2, I) return L2 def union2(self, L1, L2): # renvoie la réunion de deux listes d'intervalles for I in L1: L2 = self.addition_intervalle(L2, I) return L2 def nettoyer_dict(self, D): ND = {} for Clef,liste in D.iteritems(): #if D[Clef] != []: # ND[Clef] = D[Clef] if len(liste) > 0: ND[Clef] = liste return ND # Detection des remplacements # Ecrit par Jean-Gabriel Ganascia le 16 fevrier 2003 def rang_blocs(self, occs_blocs, occs_ts_blocs, occs_blocs_d): #print "Appel rang blocs: ", occs_blocs L = self.rang_blocs_(occs_blocs, occs_ts_blocs, occs_blocs_d, 0, [], [0, 0]) #print "valeur rang blocs: ", L return L def rang_blocs_(self, occs_blocs, occs_ts_blocs, occs_blocs_d, Rang, Acc, Der): #print 'appel rang blocs_ avec occs_blocs=', occs_blocs, ' occs_ts=', occs_ts_blocs, ' rang=', Rang, ' acc=', Acc, ' der=', Der while occs_blocs <> []: if occs_blocs[0] <= Der: occs_blocs = occs_blocs[1:] elif occs_ts_blocs == []: Acc.append([occs_blocs[0], Rang]) occs_blocs = occs_blocs[1:] elif ( occs_ts_blocs[0] in occs_blocs_d or occs_ts_blocs[0] in occs_blocs ): occs_ts_blocs = occs_ts_blocs[1:] elif occs_blocs[0] < occs_ts_blocs[0]: Acc.append([occs_blocs[0], Rang]) occs_blocs = occs_blocs[1:] else: Der = occs_ts_blocs[0] occs_ts_blocs = occs_ts_blocs[1:] Rang = Rang + 1 #print "Acc partiel: ", Acc #print "Valeur rang blocs: ", Acc return Acc def fusion(self, L): #print "Appel fusion: L= ", L if L == []: return L else: return self.fusion__(L[-1], L[:-1]) def fusion__(self, E, L): aux = [] while L <> []: if E[1] == L[-1][1]: E = [[L[-1][0][0], E[0][1]], L[-1][1]] L = L[:-1] else: aux = [E] + aux E = L[-1] L.pop() #L = L[:-1] aux = [E] + aux #print "Valeur fusion : ", aux return aux def correspondance(self, L1, L2, T, ratio_min_remplacement): aux0 = [] aux1 = [] while (L1 <> [] and L2 <> []): if L1[-1][1] == L2[-1][1]: if self.adequation_remplacement(L1[-1][0], L2[-1][0], T, ratio_min_remplacement): aux0.append(L1[-1]) aux1.append(L2[-1]) L1.pop() #L1 = L1[:-1] L2.pop() #L2 = L2[:-1] elif L1[-1][1] > L2[-1][1]: L1.pop() #L1 = L1[:-1] else: L2.pop() #L2 = L2[:-1] aux0.reverse() aux1.reverse() return [aux0, aux1] def correspondance_(self, L1, L2, T, ratio_min_remplacement): L = [] while (L1 <> [] and L2 <> []): if L1[-1][1] == L2[-1][1]: if self.adequation_remplacement(L1[-1][0], L2[-1][0], T, ratio_min_remplacement): L = self.addition_intervalle(L, L1[-1][0]) L = self.addition_intervalle(L, L2[-1][0]) L1.pop() #L1 = L1[:-1] L2.pop() #L2 = L2[:-1] elif L1[-1][1] > L2[-1][1]: L1.pop() #L1 = L1[:-1] else: L2.pop() #L2 = L2[:-1] return L def adequation_remplacement(self, texte1, texte2, ratio_min_remplacement): if self.chaine_blanche(texte1) or self.chaine_blanche(texte2): return 0 ratio = float(len(texte1))/float(len(texte2)) #print "test: t1:", T[I1[0]:I1[1]], "; t2", T[I2[0]:I2[1]], "; ratio: ", ratio if ratio > ratio_min_remplacement or ratio < 1/ratio_min_remplacement: return 0 return 1 def chaine_blanche(self, texte): for c in texte: if c not in ' \n\t\r': return 0 return 1 #return self.chaine_blanche_(T[I[0]:I[-1]]) def chaine_blanche_(self, chaine): """Renvoie vrai si la chaine ne contient que des séparateurs """ while chaine <> '': c = chaine[0] if c <> ' ' and c <> '\n' and c <> '\t' and c <> '\r': return 0 chaine = chaine[1:] return 1 def elimine_int_couverts(self, L, P): # prend deux listes d'intervalles en entree # renvoie la liste P dont on a enleve les intervalles # couverts par des intervalles de la liste L Q = [] while L <> [] and P <> []: # sys.stderr.write("Supp P[0]="+str(P[0])+" / Remp L[0]="+str(L[0])) # sys.stderr.write("supp="+t[P[0][0]:P[0][1]]+" / remp="+t[L[0][0]:L[0][1]]) if L[0][1] < P[0][0]: L.pop(0) #L = L[1:] # sys.stderr.write(" / 1 jette remp") elif L[0][0] > P[0][1]: Q = self.addition_intervalle(Q, P[0]) P.pop(0) #P = P[1:] # sys.stderr.write(" / 2 garde supp") elif L[0][1] >= P[0][1]: P.pop(0) #P = P[1:] # sys.stderr.write(" / 3 jette supp") else: L.pop(0) #L = L[1:] # sys.stderr.write(" / 4 jette remp 2") # sys.stderr.write("\n") # sys.stderr.write("Supp P="+str(P)+" / Remp L="+str(L)+"\n") while P <> []: Q = self.addition_intervalle(Q, P[0]) P.pop(0) #P = P[1:] return Q def elimine_int_couverts__(self, L, P): # prend deux listes d'intervalles en entree # renvoie la liste P dont on a enleve les intervalles # couverts par des intervalles de la liste L Q = [] while L <> [] and P <> []: # sys.stderr.write("Supp P[0]="+str(P[0])+" / Remp L[0]="+str(L[0])) # sys.stderr.write("supp="+t[P[0][0]:P[0][1]]+" / remp="+t[L[0][0]:L[0][1]]) if L[0][1] < P[0][0]: L.pop(0) #L = L[1:] # sys.stderr.write(" / 1 jette remp") elif L[0][0] > P[0][1]: Q = self.addition_intervalle(Q, P[0]) P.pop(0) #P = P[1:] # sys.stderr.write(" / 2 garde supp") elif L[0][0]<=P[0][0] and L[0][1] >= P[0][1]: P.pop(0) #P = P[1:] # sys.stderr.write(" / 3 jette supp") elif L[0][0]<=P[0][0] and L[0][1] <= P[0][1]: NP = [L[0][1], P[0][1]] L.pop(0) #L = L[1:] P = [NP]+P[1:] elif L[0][0]>P[0][0] and L[0][1] > P[0][1]: Q = self.addition_intervalle(Q, [P[0][0],L[0][0]]) P.pop(0) #P = P[1:] # sys.stderr.write(" / 4 jette remp 2") # sys.stderr.write("\n") # sys.stderr.write("Supp P="+str(P)+" / Remp L="+str(L)+"\n") while P <> []: Q = self.addition_intervalle(Q, P[0]) P.pop(0) #P = P[1:] return Q def comp(self, x, y): if x > y: return -1 else: return +1 def comp_longueur(self, x, y): if len(x) > len(y): return -1 else: return +1 def couverte(self, chaine, liste): for chaines in liste: if self.sous_motif(chaine, chaines): return 1 return 0 def sous_motif(self, motif, chaine): try: return re.search(motif, chaine) except: return 0 def adjacent(self, I1, I2): # Renvoie 1 si les deux intervalles I1 et I2 sont adjacents, 0 sinon return (((I1[0] <= I2[0]) and (I1[1] >= I2[0])) or ((I1[0] <= I2[1]) and (I1[1] >= I2[1]))) def adjacent_(self, I, L): # Renvoie 1 si I est adjacent à au moins un intervalle de L, 0 sinon for II in L: if self.adjacent(I, II): return 1 elif II[0] > I[1]: return 0 return 0 # Composition decalee # Ecrit par Jean-Gabriel Ganascia le 30 juillet 2004 pour optimiser # la construction de classes dequivalence def composition_decalee(self, L_occs_deb, L_occs_suite, dec): #print "Longueur deb: ", len(L_occs_deb), "; suite: ", len(L_occs_suite) L_deb = L_occs_deb L_suite = L_occs_suite res = [] while L_deb and L_suite: if L_deb[0]+dec < L_suite[0]: L_deb.pop(0) #L_deb = L_deb[1:] elif L_deb[0]+dec == L_suite[0]: res.append(L_deb[0]) L_deb.pop(0) #L_deb = L_deb[1:] L_suite.pop(0) #L_suite = L_suite[1:] else: L_suite.pop(0) #L_suite = L_suite[1:] return res # renvoie la liste des chaines de taille 2dec (ou 2a) # qui commencent dans L_occ_deb et dont la 2e moitié commence dans L_occs_suite def composition_decalee_(self, L_occs_deb, L_occs_suite, dec): res=[] for X in L_occs_deb: if X+dec in L_occs_suite: res.append(X) return res # même chose mais L_occs_suite n'est parcourue qu'une seule fois def composition_decalee_b(self, L_occs_deb, L_occs_suite, dec): res=[] j=0 l=len(L_occs_suite) for X in L_occs_deb: while L_occs_suite[j] < X+dec: if j < l-1: j = j+1 else: return res if L_occs_suite[j] == X+dec: res.append(X) return res def composition_decalee_mot(self, L_occs_deb, L_occs_suite, dec,texteMot): res=[] for X in L_occs_deb: if texteMot.posCarMot(X,dec) in L_occs_suite: res.append(X) return res class chaineMot: """ classe représentant une chaine de caractères à laquelle on peut accéder mot par mot ou caractère par caractère le choix se fait à la création avec le param carOuMot si processEnd alors on calcule toute la table de correspondance mot_car sinon on évite ce calcul et il sera fait à la demande avec testMotCar """ def __init__(self, texte, carOuMot, processEnd=False): self.chaine = texte self.carOuMot = carOuMot # mode caractère ou mode mot self.lgCar = len(self.chaine)# longueur en caractères if not self.carOuMot: # mode mot self.mot_car = {} # dico indexé par le nième mot et donnant sa place dans la chaine self.mot_car[0] = 0 self.car_mot = {} # dico indexé par caractère et retournant le mot auquel ce caractère appartient self.car_mot[0] = 0 self.max_mot = 0 cur_mot = 0 cur_car = 1 if processEnd: end = self.lgCar else: end = min(10,self.lgCar) while cur_car < end: if (self.chaine[cur_car-1]==' ' or self.chaine[cur_car-1]=='\r\n' or self.chaine[cur_car-1]=='\r' or self.chaine[cur_car-1]=='\n'): cur_mot = cur_mot + 1 self.mot_car[cur_mot] = cur_car self.max_mot = cur_mot self.car_mot[cur_car] = cur_mot cur_car = cur_car+1 self.lgMot = cur_mot+1 # longueur en mots def testeMotCar(self,pos): # sys.stderr.write("testMotCar "+str(pos)+"\n") # x"+self.chaine+"x /" if pos not in self.mot_car: # for i in self.mot_car: # sys.stderr.write(str(i)+", ") # sys.stderr.write("\n") cur_mot = self.max_mot cur_car = self.mot_car[self.max_mot]+1 # sys.stderr.write("cur_mot = "+str(cur_mot)+" / cur_car = "+str(cur_car)+"\n") while cur_mot != pos: # sys.stderr.write("cur_car-1 "+str(cur_car-1)+"\n") if (self.chaine[cur_car-1]==' ' or self.chaine[cur_car-1]=='\r\n' or self.chaine[cur_car-1]=='\r' or self.chaine[cur_car-1]=='\n'): cur_mot+=1 self.mot_car[cur_mot] = cur_car self.max_mot = cur_mot self.car_mot[cur_car] = cur_mot cur_car = cur_car+1 self.lgMot = cur_mot+1 # longueur en mots # else: # sys.stderr.write(str(pos)+" in str and is "+str(self.mot_car[pos])+"\n") # sys.stderr.write("\n") def printTab(self): for i in self.mot_car: sys.stderr.write(str(i)+":"+str(self.mot_car[i])+" / ") sys.stderr.write(" "+self.toStr()+"\n") sys.stderr.flush() def toStr(self): return self.chaine def slice(self,deb,fin): # slice en caractères ou en mots suivant le mode if (self.carOuMot): return self.chaine[deb:fin] else: # self.testeMotCar(deb) # self.testeMotCar(fin) return self.chaine[self.mot_car[deb]:self.mot_car[fin]] def sliceCar(self,deb,fin) : '''slice uniquement en caractères''' return self.chaine[deb:fin] def sliceM(self, motDeb, carDeb, motFin, carFin): """ si mode mot, slice en prenant le motDeb ième mot + carDeb caractères jusqu'au motFin ième mot + carFin caractères sinon les 2 param mot sont considérés comme exprimés en caractères """ if (self.carOuMot): return self.chaine[motDeb+carDeb:motFin+carFin] else: #self.printTab() # self.testeMotCar(motDeb) #self.printTab() # self.testeMotCar(motFin) #self.printTab() #sys.stderr.write("sliceM "+str(self.mot_car[motDeb]+carDeb)+":"+str(self.mot_car[motFin]+carFin)+"\n") return self.chaine[self.mot_car[motDeb]+carDeb:self.mot_car[motFin]+carFin] def sliceC(self, carDeb, motDeb, carFin, motFin): """ si mode mot, slice en prenant le mot qui correspond au carDeb ième caractère + motDeb mot jusqu'au mot qui correspond au carFin ième caractère + motFin mot sinon les 2 param mot sont considérés comme exprimés en caractères """ if (self.carOuMot): return self.chaine[carDeb+motDeb:carFin+motFin] else: # self.testeMotCar(self.car_mot[carDeb]+motDeb) # self.testeMotCar(self.car_mot[carFin]+motFin) # sys.stderr.write("lengthC = "+str(self.lengthC())+" / lengthM = "+str(self.lengthM())+"\n") # sys.stderr.write("carDeb "+str(carDeb)+" / motDeb "+str(motDeb)+" / carFin "+str(carFin)+" / motFin "+str(motFin)+"\n") # sys.stderr.write("self.car_mot[carDeb] "+str(self.car_mot[carDeb])+" / self.car_mot[carFin]"+str(self.car_mot[carFin])+"\n") # sys.stderr.write("self.mot_car[self.car_mot[carDeb]+motDeb "+str(self.mot_car[self.car_mot[carDeb]+motDeb])+" / self.mot_car[self.car_mot[carFin]+motFin]"+str(self.mot_car[self.car_mot[carFin]+motFin])+"\n") # sys.stderr.write("sliceC = "+self.chaine[self.mot_car[self.car_mot[carDeb]+motDeb]:self.mot_car[self.car_mot[carFin]+motFin]]) return self.chaine[self.mot_car[self.car_mot[carDeb]+motDeb]:self.mot_car[self.car_mot[carFin]+motFin]] # à vérifier def posCarMot(self, carDeb, motDeb): """ renvoie une position en nb de caractères en convertissant carDeb carac + motDeb mots """ if (self.carOuMot): # si mode car les 2 variables sont en caractères return carDeb+motDeb else: # self.testeMotCar(self.car_mot[carDeb]+motDeb) if ((carDeb in self.car_mot) and (self.car_mot[carDeb]+motDeb in self.mot_car)): return self.mot_car[self.car_mot[carDeb]+motDeb] else: return -1 def posMotCar(self,motDeb, carDeb): """ renvoie une position en nb de caractères en convertissant motDeb mots + carDeb carac """ if (self.carOuMot): # si mode car les 2 variables sont en caractères return motDeb+carDeb else: # self.testeMotCar(motDeb) return self.mot_car[motDeb]+carDeb def length(self): if (self.carOuMot): return self.lgCar else: return self.lgMot def lengthC(self): """ retourne la longueur en caractères """ return self.lgCar def lengthM(self): if (self.carOuMot): return self.lgCar else: return self.lgMot class dict_chaines: """ remplace le dictionnaire initial: hachage des chaines de facon à ne stocker que les l_hach premiers elements en mode mot, on indexe sur le nb de mots (et plus sur le nombre de car) et sur la chaine de maximum l_hach premiers cararctères (comme en mode normal) et on stocke comme valeurs les occurences en carctères (et pas en mots) """ def __init__(self, l_hachage, texteMot, lg_texte1, carOuMot): self.texteMot = texteMot self.lg_texte1 = lg_texte1 self.l_hachage = l_hachage self.carOuMot = carOuMot self.E = {} self.initialise() #print "Fin de l'initialisation du dictionnaire" def initialise(self): self.E[1]={} i=0 # parcours de tout le texte pout initialiser le dictionnaire # avec toutes les chaines de longueur 1 while i < self.texteMot.length()-1: self.ajout_occ(chaineMot(self.texteMot.slice(i,i+1),self.carOuMot, True), self.texteMot.posMotCar(i,0)) i=i+1 def ajout_occ(self, ch, i): """ ajoute une occurence i de ch au dictionnaire ch doit être de type chaineMot """ #sys.stderr.write("ajout_occ de _"+ch.toStr()+"_"+str(ch.length())+"\n") #sys.stderr.flush() #ln = len(ch) ln = ch.length() # crée un nouveau dict comme valeur de E[ln] if ln not in self.E: self.E[ln] = {} # crée un nouveau dict comme valeur de E[ln][ch[0:l_hachage]] #if ch[0:self.l_hachage] not in self.E[ln]: if ch.sliceCar(0,self.l_hachage) not in self.E[ln]: #if ch.toStr() not in self.E[ln]: #self.E[ln][ch[0:self.l_hachage]] = { } self.E[ln][ch.sliceCar(0,self.l_hachage)] = {} #self.E[ln][ch.toStr()] = { } occ = self.occ_chaine(ch) if occ == []: #self.E[ln][ch[0:self.l_hachage]][i]=[i] self.E[ln][ch.sliceCar(0,self.l_hachage)][i]=[i] #self.E[ln][ch.toStr()][i]=[i] else: #self.E[ln][ch[0:self.l_hachage]][occ].append(i) self.E[ln][ch.sliceCar(0,self.l_hachage)][occ].append(i) #sys.stderr.write(str(occ)+"\n") #self.E[ln][ch.toStr()][occ].append(i) def ajout_occs(self, ch, L_occs): """ajoute une liste d'occurences à ch ch doit être de type chaineMot """ #sys.stderr.write("ajout_occ de _"+ch.toStr()+"_"+str(ch.length())+"\n") #sys.stderr.flush() #ln = len(ch) ln = ch.length() if ln not in self.E: self.E[ln] = {} #if ch[0:self.l_hachage] not in self.E[ln]: # self.E[ln][ch[0:self.l_hachage]] = {} if ch.sliceCar(0,self.l_hachage) not in self.E[ln]: self.E[ln][ch.sliceCar(0,self.l_hachage)] = {} occ = self.occ_chaine(ch) if occ == []: occ = L_occs[0] #self.E[ln][ch[0:self.l_hachage]][occ] = [] self.E[ln][ch.sliceCar(0,self.l_hachage)][occ] = [] for i in L_occs: #self.E[ln][ch[0:self.l_hachage]][occ].append(i) self.E[ln][ch.sliceCar(0,self.l_hachage)][occ].append(i) def occ_chaine(self, ch): """ ch doit être de type chaineMot si la chaine ch se trouve dans le dictionnaire, renvoie sa première occurrence associee qui est la clé pour accéder à sa liste d'occurences sinon, renvoie [] """ #ln = len(ch) ln = ch.length() G = self.E.get(ln) if not G: return [] #H = G.get(ch[0:self.l_hachage]) H = G.get(ch.sliceCar(0,self.l_hachage)) if not H: return [] if (self.carOuMot and ln < self.l_hachage): #if (ln < self.l_hachage): return H.keys()[0] else: # recherche de ch parmi les chaines de taille ln indéxées avec ch[0:self.l_hachage] for occ in H: #if self.texte[occ:occ+ln] == ch: if self.texteMot.sliceC(occ,0,occ,ln) == ch.toStr(): return occ def occs_chaine(self, ch): """ renvoie la liste des occurences de la chaine associée à la chaine ch """ #k = len(ch) k = ch.length() #H = self.E.get(k).get(ch[0:self.l_hachage]) H = self.E.get(k).get(ch.sliceCar(0,self.l_hachage)) if not H: return [] if (self.carOuMot and k < self.l_hachage): return H.values()[0] else: #return self.E.get(k).get(ch[0:self.l_hachage]).get(self.occ_chaine(ch)) return self.E.get(k).get(ch.sliceCar(0,self.l_hachage)).get(self.occ_chaine(ch)) return [] def toutes_occ_chaines_it(self, k, radical): """ Retourne la liste des occurences de la chaine de longueur k d'index radical dans le texte. L'index a une taille inférieur à self.l_hachage qui peut etre inférieure à k """ G = self.E.get(k).get(radical) if G: return self.E.get(k).get(radical).iterkeys() else: return [] def tous_radicaux_iteration(self,k): """ Retourne la liste des index-chaines (ou radicaux) de longueur k """ G = self.E.get(k) if G: return self.E.get(k).iterkeys() else: return [] def nettoyer_radical(self, k, radical): """ Parcours les listes d'occurences associées à un radical Si parmi ces listes, une est vide ou ne possède pas de répétitions entre le texte1 et le texte2 alors supprimer cette liste d'occurences """ for occ in self.toutes_occ_chaines_it(k, radical): if not self.repetition(self.E.get(k).get(radical)[occ]): del self.E.get(k).get(radical)[occ] if self.E.get(k)[radical] == { }: del self.E.get(k)[radical] def repetition(self, Locc): """ Teste si la liste d'occurrences Locc mentionne des occurrences répétitives """ return (Locc <> [] and (Locc[0] < self.lg_texte1) and (Locc[-1] >= self.lg_texte1)) def eliminer_toutes_occurrences(self, ch): """ supprime la liste d'occurence d'une chaine ch ch est de type chaineMot """ #k = len(ch) k = ch.length() #G = self.E.get(k).get(ch[0:self.l_hachage]) G = self.E.get(k).get(ch.sliceCar(0,self.l_hachage)) if G: #del self.E.get(k).get(ch[0:self.l_hachage])[self.occ_chaine(ch)] del self.E.get(k).get(ch.sliceCar(0,self.l_hachage))[self.occ_chaine(ch)] #self.nettoyer_radical(k, ch[0:self.l_hachage]) self.nettoyer_radical(k, ch.sliceCar(0,self.l_hachage)) def etat_dict(self): sys.stderr.write( "Impression etat dictionnaire\n") for k in self.E: nbre = len(self.E[k]) if nbre != -1: sys.stderr.write("k = "+ str(k)+ " nombre chaines: "+ str(nbre) +"\n") # if k>1: # for x in self.E[k]: # sys.stderr.write("E("+str(k)+") = "+x+"\n") sys.stderr.flush() class stockage_chaines_optimales: """ C'est là  une classe qui contient, dans un dictionnaire toutes les chaînes optimales. Plus exactement, chaque chaine est repérée par son occurrence sur le texte (l'occurrence de rang inférieur pour être plus précis), et par l'occurrence de la fin de la chaîne. Cette classe est utilisée par la fonction "blocs_maximaux" """ def __init__(self, Dict, texte, lg_texte1, carOuMot, long_min_pivots): """ L'initialisation se fait à  l'aide du dictionnaire qui comprend l'ensemble des fragments répétés et de la longueur du premier texte. """ self.tool = Utile() # chaines_optimales: [0..lg] à chaque case i correspond la position du dernier caracctère # du bloc auquel appartient la position i self.chaines_optimales = { } # occs_optimales : [0..lg] à chaque case i correspond la liste des blocs identiques # au bloc auquel appartient cette case i self.occs_optimales = { } # 16 aout 2004 self.clefs = self.tool.non_nul_keys(Dict.E) self.clefs.sort() self.clefs.reverse() self.lg_texte1 = lg_texte1 self.lg = len(texte) self.texte = texte self.carOuMot = carOuMot self.long_min_pivots = long_min_pivots for i in range(0, self.lg): self.chaines_optimales[i] = i self.occs_optimales[i] = [] # sys.stderr.write("1 self.chaines_optimales = "+str(self.chaines_optimales)+"\n") # sys.stderr.write("1 self.occs_optimales = "+str(self.occs_optimales)+"\n") self.construire_chaines_optimales(Dict) #for clef in self.clefs: # Dict.E[clef]= {} #Dict = {} # sys.stderr.write("2 self.chaines_optimales = "+str(self.chaines_optimales)+"\n") # sys.stderr.write("2 self.occs_optimales = "+str(self.occs_optimales)+"\n") self.allonger_chaines_i(0) # sys.stderr.write("3 self.chaines_optimales = "+str(self.chaines_optimales)+"\n") # sys.stderr.write("3 self.occs_optimales = "+str(self.occs_optimales)+"\n") self.stockage_chaines(texte) #self.blocs_texte.sort() # for x in self.blocs_texte: # sys.stderr.write(x+" "+str(self.blocs_texte[x])+"\n") # A l'issue de l'initialisation, les chaînes optimales sont stockées # dans la variable "blocs_texte" def occ_sous_optimale(self, occ, chaine): return (self.chaines_optimales[occ] >= occ + len(chaine)) # Teste si l'occurrence "occ" de la chaîne "chaine" # est incluse dans l'une des chaînes optimales def repetition(self, Locc): # Teste si la liste d'occurrences Locc mentionne des occurrences répétitives return (Locc <> [] and (Locc[0] < self.lg_texte1) and (Locc[-1] >= self.lg_texte1)) def ajout_occs(self, Locc, ln): # Ajoute les occurrences de "chaine" de taille ln contenues dans "Locc" N=0 #sys.stderr.write( "Appel ajout_occs" +str(Locc)+ "; lg="+str(ln)+"\n") LLocc = Locc[:] while LLocc: O = LLocc[0] while O < LLocc[0]+ln and self.chaines_optimales[O] < LLocc[0]+ln: N=1 self.chaines_optimales[O] = LLocc[0] + ln self.occs_optimales[O] = Locc O = O+1 #self.allonger_chaines(LLocc[0]) LLocc = LLocc[1:] return N # Impression etat dictionnaire #k = 32 nombre chaines: 169 #k = 1 nombre chaines: 5 #k = 4 nombre chaines: 4 #k = 1024 nombre chaines: 2256 #k = 8 nombre chaines: 25 #k = 64 nombre chaines: 611 #k = 128 nombre chaines: 1060 #k = 256 nombre chaines: 1892 #k = 16 nombre chaines: 126 #k = 512 nombre chaines: 3539 def construire_chaines_optimales(self, Dict): clefs = self.clefs while clefs <> []: # sys.stderr.write("clef[0]= "+str(clefs[0])+"\n") # tous les radicaux de longueur clefs[0] for radical in Dict.tous_radicaux_iteration(clefs[0]): # toutes les occurences de ce radical for occ in Dict.toutes_occ_chaines_it(clefs[0], radical): Loccs = [] #Dict[clefs[0]][chaine][:] #chaine = Dict.texte[occ:occ+clefs[0]] # texte correspondant à cette occurence et de longueur clefs[0] chaine = chaineMot(Dict.texteMot.sliceC(occ,0,occ,clefs[0]), self.carOuMot,True) # sys.stderr.write("Chaine à  l'étude: "+ chaine.toStr()+"\n") # pour toutes les occurencs de chaine for occ_ch in Dict.occs_chaine(chaine): if not self.occ_sous_optimale(occ_ch, chaine.toStr()): Loccs.append(occ_ch) #Loccs.append(occ_ch) if self.repetition(Loccs): #self.ajout_occs(Loccs, len(chaine)) self.ajout_occs(Loccs, chaine.lengthC()) clefs = clefs[1:] #print "Fin de la transcription du dictionnaire" def allonger_chaines_i(self, Occ): #position du dernier carac du bloc auquel appartient Occ NOcc = self.chaines_optimales[Occ] if NOcc == Occ: NOcc = Occ + 1 i=0 while ((Occ < self.lg_texte1 and NOcc < self.lg_texte1) or (Occ >= self.lg_texte1 and NOcc < self.lg)): # sys.stderr.write("Appel allonger chaines sur '"+ self.texte[Occ:NOcc]+"'\n") while self.allonger_chaines_(Occ): #print self.chaines_optimales.values() pass Occ += 1 #NOcc # passage au bloc suivant NOcc = self.chaines_optimales[Occ] # denier car du boc if NOcc == Occ: NOcc = Occ + 1 i+=1 # sys.stderr.write("compt allonger_chaines_i = "+ str(i)+"\n") def allonger_chaines_(self, Occ): Occ_fin = self.chaines_optimales[Occ] NOcc = Occ while (NOcc < self.lg and self.repetition(self.occs_optimales[NOcc]) and not self.chaines_optimales[NOcc] > Occ_fin): NOcc = NOcc + 1 # sys.stderr.write("NOcc = "+str(NOcc)+" / ") if NOcc >= self.lg: NOcc = self.lg - 1 Occ_fin = self.lg else: Occ_fin = self.chaines_optimales[NOcc] LOcc = self.tool.composition_decalee_(self.occs_optimales[Occ], self.occs_optimales[NOcc], NOcc - Occ) # sys.stderr.write("allonger chaines; LOcc= " +str(LOcc)+" / Occ = "+str(Occ)+" / NOcc = "+str(NOcc)+" / Occ_fin = "+str(Occ_fin)+"\n") # sys.stderr.write("Occs gauche: "+str(self.occs_optimales[Occ])+"; chaine: '"+ self.texte[Occ:self.chaines_optimales[Occ]]+ "'\n") # sys.stderr.write("Occs droites: "+str(self.occs_optimales[NOcc])+"; chaine: '"+ self.texte[NOcc:self.chaines_optimales[NOcc]]+ "'\n") # sys.stderr.write("Decalage: "+str( NOcc - Occ)+"\n") if self.repetition(LOcc): # sys.stderr.write("ajout_occs:'"+ self.texte[Occ:Occ_fin]+ "' " +str(LOcc)+"\n\n") return self.ajout_occs(LOcc, Occ_fin - Occ) else: # sys.stderr.write("\n") return 0 # def sto(self): # self.stockage_chaines(e.texte, e.E) def stockage_chaines(self, texte): d = 0 f = 0 self.blocs_texte = {} # stockage des blocs optimaux dans un dictionnaire while d < len(self.chaines_optimales): if f <> self.chaines_optimales[d] : f = self.chaines_optimales[d] if (f-d >= self.long_min_pivots): #self.blocs_texte[texte[d:f]] = Dict[f-d][texte[d:f]] if self.blocs_texte.has_key(texte[d:f]): self.blocs_texte[texte[d:f]].append(d) else: self.blocs_texte[texte[d:f]] = [d] # sys.stderr.write( "chaine: "+ texte[d:f]+ "; rang:"+ str(d)+"\n") d = d+1 def test_miroir(): tool = Utile() locc = [(10,20),(40,45),(42,60)] LRes = tool.miroir(locc,0,100) if __name__ == '__main__': test_miroir()