SequenceMatcher für mehrere Eingänge, nicht nur zwei?

Question

Gedanken über den besten Weg, um dieses besondere Problem zu nähern, und wenn keine Bibliotheken (Python bevorzugt, aber ich kann flexibel sein, wenn nötig).

habe ich eine Datei mit einer Zeichenfolge in jeder Zeile. Ich möchte die längste gemeinsame Muster und deren Standorte in jeder Zeile finden. Ich weiß, dass ich SequenceMatcher können Linie eins und zwei, eins und drei, usw. und dann korrelieren die Ergebnisse zu vergleichen, aber wenn es etwas, das tut es schon?

Im Idealfall würden erscheinen diese Begegnungen überall in jeder Zeile, aber für den Anfang kann ich in Ordnung sein mit ihnen in jeder Zeile versetzt auf dem gleichen bestehenden und von dort aus gehen. So etwas wie eine Kompressions-Bibliothek, die eine gute API hat seine String-Tabelle zugreifen könnte ideal sein, aber ich habe nichts so weit, dass passt diese Beschreibung.

gefunden

Zum Beispiel mit diesen Zeilen:

\x00\x00\x8c\x9e\x28\x28\x62\xf2\x97\x47\x81\x40\x3e\x4b\xa6\x0e\xfe\x8b
\x00\x00\xa8\x23\x2d\x28\x28\x0e\xb3\x47\x81\x40\x3e\x9c\xfa\x0b\x78\xed
\x00\x00\xb5\x30\xed\xe9\xac\x28\x28\x4b\x81\x40\x3e\xe7\xb2\x78\x7d\x3e

Ich möchte, dass die 0-1 zu sehen, und 10-12 Spiel in allen Linien in der gleichen Position und line1 [4,5] entspricht line2 [5,6] entspricht line3 [7,8].

Danke,

Answer 1

Wenn alles, was Sie wollen, ist gemeinsame Teil zu finden, die zur gleichen sind in jeder Zeile versetzt, alles, was Sie brauchen, ist etwas wie folgt aus:

matches = []
zipped_strings = zip(s1,s2,s3)
startpos = -1
for i in len(zipped_strings):
  c1,c2,c3 = zipped_strings[i]
  # if you're not inside a match, 
  #  look for matching characters and save the match start position
  if startpos==-1 and c1==c2==c3:
    startpos = i
  # if you are inside a match, 
  #  look for non-matching characters, save the match to matches, reset startpos
  elif startpos>-1 and not c1==c2==c3:
    matches.append((startpos,i,s1[startpos:i]))
    # matches will contain (startpos,endpos,matchstring) tuples
    startpos = -1
# if you're still inside a match when you run out of string, save that match too!
if startpos>-1:
  endpos = len(zipped_strings)
  matches.append((startpos,endpos,s1[startpos:endpos]))

Um die längsten gemeinsamen Muster unabhängig von ihrem Standort zu finden, tut SequenceMatcher klingen wie die beste Idee, sondern string1 string2 zu vergleichen und dann Zeichenfolge1 zu string3 und zu versuchen, die Ergebnisse zu verschmelzen, nur um all gängigen Teil von string1 und string2 ( mit get_matching_blocks), und dann jedes Ergebnis, das zu string3 vergleichen Einstimmungen zwischen allen drei Saiten zu erhalten.

Answer 2

Ist Ihr Problem Leistung?

Wie groß ist Ihre Eingabe?

die Zeichenfolgen mindestens 2 übereinstimmen?

Beachten Sie, dass Ihr Beispiel ist nicht korrekt ich, wie die Ergebnisse denken Sie nicht erwarten, das Beispiel Strings entsprechen, die Sie zur Verfügung gestellt.