SequenceMatcher для нескольких входов, а не только для двух?

Question

задаюсь вопросом, как лучше всего подойти к этой конкретной проблеме и есть ли какие-либо библиотеки (предпочтительно 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].

Спасибо,

Answer 1

Если все, что вам нужно, — это найти общие подстроки, находящиеся с одинаковым смещением в каждой строке, все, что вам нужно, это что-то вроде этого:

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, чтобы получить совпадения между всеми тремя строками.

Answer 2

Ваша проблема с производительностью?

Насколько велик ваш вклад?

Соответствует ли минимальная длина строк 2?

Обратите внимание, что ваш пример неверен, я думаю, поскольку ожидаемые вами результаты не соответствуют предоставленным вами образцам строк.