String regex due disallineamenti Python

Question

Come posso estendere il codice qui sotto per permettermi di esplorare tutte le istanze in cui ho 2 disallineamenti o meno tra la mia sottostringa e la stringa padre?

Substring: SSQP

String-a-match-a: SSPQQQQPSSSSQQQSSQPSPSQSSQPSSQPPSSSSQPSPSQSSQPSSSSQPSPSQSSQPSSSSQPSPSQ

Ecco un esempio in cui è incorporato un solo possibile disallineamento:

>>> s = 'SSPQQQQPSSSSQQQSSQPSPSQSSQPSSQPPSSSSQPSPSQSSQPSSSSQPSPSQSSQPSSSSQPSPSQ' 
>>> re.findall(r'(?=(SSQP|[A-Z]SQP|S[A-Z]QP|SS[A-Z]P|SSQ[A-Z]))', s) 
['SSQQ', 'SSQP', 'SSQP', 'SSQP', 'SSQP', 'SSQP', 'SSQP', 'SSQP', 'SSQP'] 

Ovviamente, incorporante il possibilità di due disallineamenti nel codice sopra richiederebbe un sacco di tipizzazione a forza bruta di tutte le combinazioni possibili.

Come posso estendere questo codice (o refactificare questo codice) per esplorare la possibilità di due disallineamenti?

Inoltre, desidero modificare l'output in modo da ottenere l'indice numerico restituito (non SSQQ o SSQP) della posizione esatta della sottostringa corrispondente alla stringa.

Answer 1

Non c'è bisogno di usare re qui è possibile utilizzare il modulo itertools invece e risparmia molta memoria.

È possibile prima di estrarre tutte le sotto-stringhe con lunghezza 4 poi confrontarli con il vostro substring e basta selezionare quelle che hanno meno di 2 differenza con il vostro substring:

from itertools import izip,islice,tee 

def sub_findre(s,substring,diffnumber): 
    sublen=len(substring) 
    zip_gen=(izip(substring,islice(s,i,i+sublen)) for i in xrange(len(s))) 
    for z in zip_gen: 
     l,z=tee(z) 
     if sum(1 for i,j in l if i==j)>=sublen-diffnumber: 
      new=izip(*z) 
      next(new) 
      yield ''.join(next(new)) 

Demo:

s='SSPQQQQPSSSSQQQSSQPSPSQSSQPSSQPPSSSSQPSPSQSSQPSSSSQPSPSQSSQPSSSSQPSPSQ' 

substring='SSQP' 
print list(sub_findre(s,substring,2)) 

['SSPQ', 'SPQQ', 'QQQP', 'SSSS', 'SSSQ', 'SSQQ', 'SQQQ', 'SSQP', 'PSQS', 'SSQP', 'SSQP', 'SQPP', 'SSSS', 'SSSQ', 'SSQP', 'PSQS', 'SSQP', 'SSSS', 'SSSQ', 'SSQP', 'PSQS', 'SSQP', 'SSSS', 'SSSQ', 'SSQP', 'PSQ'] 

Se si desidera restituire gli indici è necessario inserire gli indici in izip che è possibile utilizzare itertools.repeat() per ripetere l'indice con la lunghezza di substring:

from itertools import izip,islice,tee,repeat 

def sub_findre(s,substring,diffnumber): 
    sublen=len(substring) 
    zip_gen=(izip(substring,islice(s,i,i+sublen),repeat(i,sublen)) for i in xrange(len(s))) 
    for z in zip_gen: 
     l,z=tee(z) 
     if sum(1 for i,j,_ in l if i==j)>=sublen-diffnumber: 
      new=izip(*z) 
      next(new) 
      next(new) 
      yield next(new)[0] 

Demo:

print list(sub_findre(s,substring,2)) 
[0, 1, 4, 8, 9, 10, 11, 15, 20, 23, 27, 28, 32, 33, 34, 39, 42, 46, 47, 48, 53, 56, 60, 61, 62, 67] 

Answer 2

L'esplosione combinatoria non è quella negativa per due disallineamenti su quattro.

Innanzitutto, osserva che puoi omettere lo stesso SSQP, poiché è coperto da tutti i casi più clementi.

re.findall(r'(?=([A-Z]SQP|S[A-Z]QP|SS[A-Z]P|SSQ[A-Z]))', s) 

Così, il numero di casi è

   4! 
C(4, 1) = ––––––––––––– = 4 
      1! * (4 - 1)! 

Per un massimo di due disallineamenti, il numero di casi è

   4! 
C(4, 2) = ––––––––––––– = 6 
      2! * (4 - 2)! 

Vale a dire,

re.findall('(?=(SS..|S.Q.|S..P|.SQ.|.S.P|..QP))', s) 

(A semplificare l'illustrazione, mi sono preso la libertà di . Scrittura . invece di [A-Z])

---

Per ottenere le posizioni delle partite al posto del testo delle partite:

[match.start(0) for match in re.finditer('(?=(SS..|S.Q.|S..P|.SQ.|.S.P|..QP))', s)]