Python Sequence Matcher gibt unvollständige Übereinstimmung

Ich versuche, übereinstimmende Blöcke zwischen zwei Strings mit Pythons SequenceMatcher zu finden. Die Zeichenfolgen sind "ABCDPQRUVWXYZ" und "PQRABCDUVWXYZ". Wenn ich jedoch get_matching_blocks() anwende, wird die Zeichenfolge "PQR" nicht als ein übereinstimmender Block gefunden.Python Sequence Matcher gibt unvollständige Übereinstimmung

from difflib import SequenceMatcher 

str1 = "ABCDPQRUVWXYZ" 
str2 = "PQRABCDUVWXYZ" 

matchAll = SequenceMatcher(None, str1, str2, False).get_matching_blocks() 

for i in range(0, len(matchAll)): 
    print(str1[matchAll[i].a: matchAll[i].a + matchAll[i].size])

Quelle

2016-12-19 Faisal

Warum haben Sie erwartet, dass 'PQR' gefunden wird? Es klingt wie die Aufgabe, die Sie ausführen möchten, ist nicht die Aufgabe, für die 'difflib.SequenceMatcher' geschrieben wurde. – user2357112

verwendet "difflib.SequenceMatcher" eine Anforderung zum Markieren einer Antwort als richtig? Bist du verpflichtet, diese Bibliothek zu benutzen? – s2t2

docs: https://docs.python.org/2/library/difflib.html#difflib.SequenceMatcher.get_matching_blocks – innisfree

Dies könnte das tun, was Sie wollen - wird aber nicht überlappende Übereinstimmungen finden (revidiert String Standorte in s1 und s2 des Teils enthält):

str1 = "ABCDEPQRUVWXYZ" # added extra non-matching character 
str2 = "PQRABCDUVWXYZ" 

def find_subs(s1, s2): 
    subs = [] 
    loc = 0 
    while s1: 
     s1_copy = s1 
     while s1_copy: 
      while s1_copy and s1_copy not in s2: 
       s1_copy = s1_copy[:-1] 
      if s1_copy: 
       subs.append((loc, s2.index(s1_copy), s1_copy)) 
       loc += len(s1_copy) 
       s1 = s1[len(s1_copy):] 
      else: 
       s1 = s1[1:] 
       loc += 1 
      s1_copy = s1     
    return subs 

print(find_subs(str1, str2))

druckt:

[(0, 3, 'ABCD'), (5, 0, 'PQR'), (8, 7, 'UVWXYZ')]

Quelle

2016-12-19 06:14:50 PaulMcG

Dank für die Lösung, es funktioniert. – Faisal

Die docs Zustand, dass:

get_matching_blocks()

Rückkehrliste von Tripeln beschreibt passende Subsequenzen. Jedes Tripel hat die Form (i, j, n) und bedeutet, dass a [i: i + n] == b [j: j + n]. Die Tripel nehmen in i und j monoton zu.

Wenn die Funktion "PQR" in Ihrem Beispiel zurückgegeben, würde die j nicht monoton steigend sein, wie es aus dem "A" Index für das "ABCD" Spiel, zurück zum "P" Index für das "PQR" Spiel gehen würde.

Quelle

2016-12-19 05:35:09 innisfree

Versuchen Sie im Codefragment in der Frage: – Faisal

Sorry, in der Fortsetzung meines vorherigen Kommentars, versuchen Sie: s1 = "ABCPQRSTUVWX" und s2 = "PQRSTABCUVWX". Jetzt "ABC" ist die gemeinsame Teilzeichenfolge nicht gefunden, so glaube ich nicht, dass das Problem mit get_matching_blocks() zu monotonen Anstieg oder Abnahme von "i" und "j" verwandt ist. Tatsächlich glaube ich, dass der monotone Anstieg mit den Indizes innerhalb der gemeinsamen Teilkette zusammenhängt, nicht außerhalb davon. – Faisal

Richtig, weil pqrst zuerst gefunden wird, so dass der Index ich nicht monoton wäre, wenn es zurück in s1 ging – innisfree

Thank an alle Programmierer, die meinen Beitrag beantwortet haben.

Als Lösung I experimentiert und eine andere Lösung gefunden

SequenceMatcher's find_longest_match()

Methode. Dies besteht im Wesentlichen darin, die längste Übereinstimmung zwischen zwei Zeichenfolgen zu finden und dann die übereinstimmende längste Zeichenfolge jedes Mal durch fehlerhafte Zeichen zu ersetzen. Das funktioniert auch gut.

Quelle

2016-12-23 15:01:13 Faisal

Python Sequence Matcher gibt unvollständige Übereinstimmung

Antwort

Verwandte Themen