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

Question

задается вопросом о наилучшем способе решения этой конкретной проблемы и о том, есть ли какие-либо библиотеки (желательно на python, но я могу быть гибким в случае необходимости).

У меня есть файл со строкой в ​​каждой строке. Я хотел бы найти самые длинные общие образцы и их местоположения в каждой строке. Я знаю, что могу использовать SequenceMatcher для сравнения строки 1 и 2, 1 и 3 и т. Д., А затем сопоставить результаты, но есть ли что-то, что уже делает это?

В идеале эти совпадения должны появляться в любом месте на каждой строке, но для начала я могу согласиться с тем, что они существуют с одинаковым смещением в каждой строке и идут оттуда. Что-то вроде библиотеки сжатия, имеющей хороший 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 совпадают во всех строках в одной и той же позиции, а line1 [4,5] соответствует line2 [5,6] соответствует line3 [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), а затем сравните каждый результат с строкой3 сполучить совпадения между всеми тремя строками.

Answer 2

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

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

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

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