SequenceMatcher для нескольких входов, а не только для двух?
-
23-09-2019 - |
Вопрос
задаюсь вопросом, как лучше всего подойти к этой конкретной проблеме и есть ли какие-либо библиотеки (предпочтительно Python, но при необходимости я могу проявить гибкость).
У меня есть файл со строкой в каждой строке.Я хотел бы найти самые длинные общие шаблоны и их расположение в каждой строке.Я знаю, что могу использовать SequenceMatcher для сравнения первой и второй строк, первой и третьей и т. д., а затем сопоставить результаты, но есть ли что-то, что уже делает это?
В идеале эти совпадения должны появляться где угодно в каждой строке, но для начала я могу согласиться с тем, что они существуют с одинаковым смещением в каждой строке и двигаться дальше.Что-то вроде библиотеки сжатия с хорошим API для доступа к таблице строк могло бы быть идеальным, но я пока не нашел ничего, что соответствовало бы этому описанию.
Например, с этими строками:
\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
Я хотел бы видеть, что 0-1 и 10-12 совпадают во всех строках в одной и той же позиции, а строка 1[4,5] соответствует строке 2[5,6] соответствует строке 3[7,8].
Спасибо,
Решение
Если все, что вам нужно, — это найти общие подстроки, находящиеся с одинаковым смещением в каждой строке, все, что вам нужно, это что-то вроде этого:
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]))
Чтобы найти самый длинный общий шаблон независимо от местоположения, SequenceMatcher кажется лучшей идеей, но вместо того, чтобы сравнивать строку1 со строкой2, а затем строку1 со строкой3 и пытаться объединить результаты, просто получите все общие подстроки строк1 и строки2 (с помощью get_matching_blocks) , а затем сравните каждый результат со строкой string3, чтобы получить совпадения между всеми тремя строками.
Другие советы
Ваша проблема с производительностью?
Насколько велик ваш вклад?
Соответствует ли минимальная длина строк 2?
Обратите внимание, что ваш пример неверен, я думаю, поскольку ожидаемые вами результаты не соответствуют предоставленным вами образцам строк.