SequenceMatcher Python Difflib не находит длинных общих подстрок - PullRequest
Новая
       18

SequenceMatcher Python Difflib не находит длинных общих подстрок

0 голосов
/ 27 июня 2018

Я хочу использовать difflib.SequenceMatcher для извлечения самых длинных общих подстрок из двух строк. Я не уверен, нашел ли я ошибку или неправильно понял документацию find_longest_match. Это пункт, который меня смущает:

Другими словами, из всех максимально совпадающих блоков вернуть тот, который начинается самый ранний в, и из всех тех максимальных совпадающих блоков, которые начинаются самое раннее в a, вернуть тот, который начинается самым ранним в b.

(https://docs.python.org/3.5/library/difflib.html#difflib.SequenceMatcher.find_longest_match)

Сравнивая строки X this is a test и this is a test X, подстрока X фактически является максимальным блоком: она не может быть расширена (то есть, она максимальна для включения). Кроме того, это первый такой максимальный блок в тексте А. Но это, конечно, не самая длинная общая подстрока. Я сильно подозреваю, что это не то, что find_longest_match должен найти.

Фактически, в этом примере find_longest_match находит самую длинную общую подстроку: 

>>> l = len("X this is a test")
>>> matcher = difflib.SequenceMatcher(None, "X this is a test", "this is a test X")
>>> matcher.find_longest_match(0, l, 0, l)
Match(a=2, b=0, size=14)

Однако, похоже, что с некоторыми другими строками я могу спровоцировать «найти первый максимальный блок», описанный выше (извините за длинные строки, если я их укорачиваю, пример как-то ломается): 

>>> s1 = "e-like graph visualization using a spanning tree-driven layout technique with constraints specified by layers and the ordering of groups of nodes within layers. We propose a new method of how the orde"
>>> s2 = "itree graph visualization using a spanning tree-driven layout technique with constraints speci ed by layers and the ordering of groups of nodes within layers. We propose a new method of how the drivin"
>>> matcher = difflib.SequenceMatcher(None, s1, s2)
>>> matcher.find_longest_match(1, 149, 5, 149)
Match(a=1, b=47, size=1)

В этом случае он соответствует первому - в s1[1] и - в s2[47], и все. Самая длинная общая подстрока, вероятно, будет иметь вид, начинающийся с graph visualization using…

Нашел ли я ошибку, или есть другая возможная интерпретация документации, которая описывает это поведение?

Я использую Python 3.5.2 в Ubuntu.

1 Ответ

0 голосов
/ 27 июня 2018

Хорошо, я понял это. В случае, если у кого-то есть такая же проблема: SequenceMatcher имеет параметр autojunk, который делает странные вещи:

Эвристика подсчитывает, сколько раз каждый отдельный элемент появляется в последовательность. Если дубликат (после первого) аккаунта для более чем 1% последовательности и последовательность составляет по меньшей мере 200 длинные элементы, этот элемент помечен как «популярный» и считается нежелательным с целью сопоставления последовательности.

Насколько я могу судить, совпадение никогда не найдет совпадений, содержащих "мусор". Не уверен, почему это полезно, но он включен по умолчанию. Это также объясняет, почему приведенный выше пример ломается, когда я укорачиваю строки. Однако это значительно ускоряет поиск LCS.

Итак, в заключение: вы, вероятно, хотите передать autojunk=False в конструктор.

...