String Regex zwei Fehlanpassungen Python

Question

Wie kann ich den folgenden Code erweitern, damit ich alle Instanzen untersuchen kann, in denen ich 2 oder weniger Übereinstimmungen zwischen meiner Teilzeichenfolge und der übergeordneten Zeichenfolge habe?

Substring: SSQP

String-to-Match-to: SSPQQQQPSSSSQQQSSQPSPSQSSQPSSQPPSSSSQPSPSQSSQPSSSSQPSPSQSSQPSSSSQPSPSQ

Hier ist ein Beispiel, wo nur eine mögliche Diskrepanz eingebaut ist:

>>> 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'] 

Offensichtlich Einbeziehung der Möglichkeit von zwei Fehlanpassungen in dem obigen Code würde eine Vielzahl von Brute-Force-Typisierung aller möglichen Kombinationen erfordern.

Wie kann ich diesen Code erweitern (oder diesen Code umgestalten), um die Möglichkeit von zwei Fehlanpassungen zu untersuchen?

Darüber hinaus möchte ich meine Ausgabe so ändern, dass ich den numerischen Index zurückgegeben (nicht SSQQ oder SSQP) der genauen Position der Teilzeichenfolge die Zeichenfolge übereinstimmt.

Answer 1

Sie müssen hier nicht verwenden re Sie itertools Modul verwenden können, Stattdessen und speichern Sie eine Menge Speicher.

können Sie zuerst extrahieren alle Teilketten mit einer Länge von 4 dann vergleichen Sie sie mit Ihren substring und nur diejenigen auswählen, die weniger als 2 Unterschied mit Ihrer 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'] 

Wenn Sie die Indizes zurückgeben möchten, müssen Sie die Indizes in izip setzen, die Sie itertools.repeat() verwenden können, um den Index mit der Länge von substring zu wiederholen:

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

Die kombinatorische Explosion ist nicht , die schlecht für zwei Fehlpaarungen von vier ist.

Zuerst, beachten Sie, dass Sie SSQP selbst weglassen können, da es von all den milderen Fällen abgedeckt wird.

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

So ist die Zahl der Fälle ist

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

Für zwei Fehlpaarungen bis zu, die Zahl der Fälle ist

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

nämlich

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

(To vereinfache die Illustration, ich habe mir die Freiheit genommen . . statt [A-Z])

---

Schreiben Um die Positionen der Spiele anstelle des Textes der Spiele zu erhalten:

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