SequenceMatcher per ingressi multipli, non solo due?
-
23-09-2019 - |
Domanda
chiedendo circa il modo migliore per affrontare questo problema particolare e se le librerie (pitone preferibilmente, ma può essere flessibile se necessario).
Ho un file con una stringa su ogni riga. Mi piacerebbe trovare i modelli comuni più lunghe e le loro posizioni in ogni riga. So che posso usare per confrontare SequenceMatcher una linea e due, uno e tre, così via e quindi correlare i risultati, ma se c'è qualcosa che già lo fa?
Idealmente queste partite sembrerebbe ovunque su ogni linea, ma per cominciare posso andare bene con loro esistente allo stesso di offset in ogni linea e passare da lì. Qualcosa di simile a una libreria di compressione che ha una buona API per accedere alla sua tabella di stringhe potrebbe essere l'ideale, ma non ho trovato finora tutto ciò che si adatta a questa descrizione.
Per esempio con queste righe:
\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
Vorrei vedere che 0-1 e 10-12 partite in tutte le linee nella stessa posizione e linea 1 [4,5] corrisponde line2 [5,6] corrisponde line3 [7,8].
Grazie,
Soluzione
Se invece si è interessati per trovare sottostringhe comuni che sono alla stessa di offset in ogni riga, tutto ciò che serve è qualcosa di simile:
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]))
Per trovare il modello comune più lungo indipendentemente dalla loro ubicazione, SequenceMatcher suona come l'idea migliore, ma invece di confrontare stringa1 a stringa2 e poi stringa1 a string3 e cercando di unire i risultati, basta avere tutte le sottostringhe comuni di stringa1 e stringa2 ( con get_matching_blocks), e quindi confrontare ogni risultato di quella per string3 per ottenere partite tra tutte e tre le corde.
Altri suggerimenti
è la vostra prestazione problema?
Quanto è grande il tuo contributo?
è la lunghezza minima stringhe per abbinare 2?
Si noti che il tuo esempio non è corretta Penso che i risultati previsti non corrispondono alle stringhe di esempio che hai fornito.