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

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

Спасибо,

Источник

2 ответа

Решение

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

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

Источник

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

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

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

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

Источник
Другие вопросы по тегам